Lattice-Based DAPS and Generalizations: Self-enforcement in Signature Schemes

Suppose a web site such as facebook.com buys certificates for its domain from a certificate authority (CA) called xyz. These certificates enable web browsers to establish a (one-sided) authenticated session with facebook.com. Sometime later, a law enforcement agency or a nation state that has jurisdiction over the CA compels xyz to secretly issue a fresh certificate for facebook.com. The CA has no choice but to comply. The agency can then use this issued certificate in a man-in-the-middle attack on facebook.com. Web users have no way to detect that this is happening and that their traffic is being intercepted. We emphasize that the rogue certificate is issued by the same CA from which facebook.com normally buys its certificates. The only user-side signal is that a previously unseen public-key is being served in a facebook.com certificate, but this happens frequently under normal operation at a large site and would not generally look suspicious.

Some technologies, such as certificate transparency (CT) [LLK15] as well as CONIKS [MBB+15], are designed to detect situations where a CA such as xyz issues a fake certificate for a domain. These technologies empower an origin domain, facebook.com in this case, to detect that a fake certificate was issued for its domain.

Poettering and Stebila [PS14] proposed a very different defense against the scenario described above. Their idea, called double-authentication-preventing signatures, or DAPS for short, is as follows: suppose xyz signs all its certificates using a signature scheme where the signing algorithm uses the secret signing key \(\mathsf {sk}\) to sign a pair \((\mathsf {subj}, \mathsf {payload})\). Here \(\mathsf {subj}\) is the domain-name to which the certificate is issued and \(\mathsf {payload}\) is all other fields in the certificate. The resulting signature \(\sigma \) can be verified as a standard digital signature. The key property of DAPS is the following: suppose xyz publishes two valid signatures \(\sigma _1\) and \(\sigma _2\) for the same \(\mathsf {subj}\) but for different payloads, say one on \((\mathsf {subj}, \mathsf {payload}_1)\) and another on \((\mathsf {subj}, \mathsf {payload}_2)\). Then these two signatures enable anyone to expose xyz’s secret signing key \(\mathsf {sk}\). The point is that xyz can argue that it should not be forced to issue the rogue certificate for facebook.com because that would expose its signing key thereby causing massive collateral damage to all of xyz’s customers. Whether this argument is effective remains to be seen, but the idea itself is interesting and, as we show below, leads to interesting and challenging cryptographic questions.

How to Use DAPS. There are many practical holes in the basic DAPS proposal described above that prevent it from being used as is, but with a bit of thought they can be addressed. However, our goal here is not to argue that DAPS will be deployed in practice, but rather to motivate this as an interesting cryptographic question. Towards this goal, we examine broader applications of DAPS as well as an elegant generalization.

Other Applications for DAPS. Beyond certificates, DAPS can be a useful “self-enforcement” security mechanism. For example, suppose Eve owns a certain patent and wants to sell the rights to the patent. Bob wants to buy the patent from Eve, but he is worried that Eve will sell the patent to multiple people. Using DAPS, Eve can use the patent number as the subject and use “owned by Bob” as the payload. If she tries to sell the same patent to two different people she will end up signing two pairs of messages with the same subject, but different payload. The resulting two signatures can be combined to expose Eve’s private key. If this private key is of high value to Eve then this self-enforcement mechanism will prevent her from double-selling the same patent to two people. This way, Bob has some confidence in the exclusivity of the deal with Eve.

PAPS: DAPS for General Predicates. The previous paragraph motivates a more general elegant primitive which we call predicate-authentication-preventing signatures, or PAPS for short. Let \({{\mathcal {M}}}\) be a message space and let \(\phi : {{\mathcal {M}}}^k \rightarrow \{0,1\}\) be a predicate. A PAPS scheme for \(\phi \) lets the signer sign any message \(m \in {{\mathcal {M}}}\), just as in a regular signature scheme. However, if over the life of the secret key, the signer signs messages \(m_1, \ldots , m_k \in {{\mathcal {M}}}\) such that \(\phi (m_1,\ldots ,m_k) = 1\) then these k signatures can be combined to expose the signer’s secret signing key. This secret key extraction should work no matter how the k signatures are generated: as long as all k signatures are valid, it should be possible to extract the secret key. For security, as long as the predicate \(\phi \) is never satisfied, the signature scheme should be existentially unforgeable under a chosen message attack, as for regular signatures.

Notice that DAPS is a special case of PAPS: the key space \({{\mathcal {M}}}\) is a set of pairs \({{\mathcal {M}}} = {{{\mathcal {S}}}} \times {{{\mathcal {P}}}}\) and the predicate \(\phi _{\textsc {daps}}\) is simply the 2-ary predicate:

More general predicates come up naturally. For example, suppose a web site owns k machines and it wants to generate a different key-pair for each machine, necessitating a different certificate for each machine. The analogue of DAPS is a k-way DAPS where the message space \({{\mathcal {M}}}\) is again \({{\mathcal {M}}} = {{{\mathcal {S}}}} \times {{{\mathcal {P}}}}\), but now the predicate \(\phi \) is the \((k+1)\)-ary predicate

This lets the site use a different certificate for each of its k machines, but if another certificate is issued then the CA’s secret key is exposed. We give a construction for this predicate in Sect. 5 as well as for several other predicates.

Proving security of a PAPS construction is non trivial. For example, suppose the message space is \({{\mathcal {M}}} = {\mathbb {F}}_p\) for some prime p. Consider the 3-ary predicate \(\phi \) defined as \(\phi (x,y,z) = 1\) if and only if \(x+y+z = 0\). That is, the secret key should leak if the signer ever signs three messages whose sum is zero. However, if the signer never signs three messages satisfying this condition, the signature scheme should be existentially unforgeable. To prove existential unforgeability, the simulator must interact with the adversary, answering all the adversary’s adaptive signature queries, and using the adversary’s existential forgery to solve a challenge problem. The problem is that, because the adversary’s first two queries can be for arbitrary messages, the simulator must be prepared to provide a signature for all messages \(m \in {{\mathcal {M}}}\). In particular, the simulator will know the signature on three messages x, y, z satisfying \(x\,+\,y\,+\,z=0\). But then the simulator can extract the secret signing key, and can produce any forgery by itself, meaning that the adversary is not helping the simulator. Nevertheless, in Sect. 5 we are able to prove security for several generalized predicates, though not for the 3-way summation predicate.

A Further Generalization: Multi-signer PAPS. We can further generalize the notion of PAPS to the setting of k signers where each signer has its own signing/public key-pair. As before, let \(\phi \) be a k-ary predicate \(\phi : {{\mathcal {M}}}^k \rightarrow \{0,1\}\). Suppose that for \(i=1,\ldots ,k\) signer number i signs message \(m_i \in {{\mathcal {M}}}\). Then, if \(\phi (m_1,\ldots ,m_j) = 1\), then these k signatures (along with the k messages and k public keys) can be used to expose some secret s chosen at setup time.

Multi-signer PAPS come up naturally when considering certificates. Suppose that the agency, instead of asking xyz to issue the rogue certificate for facebook.com, it asks a different CA to provide a certificate for facebook.com. We are now in a 2-signer scenario. If the predicate \(\phi _{\textsc {daps}}\) can be made to work on the two signatures, despite them being from different CAs, then going to a different CA will not help the agency. We define multi-signer PAPS in Sect. 6 where we also give several constructions.

1.1 Contributions

In this work we build a lattice-based DAPS construction based on Short Integer Solutions (SIS) problem and the Learning with Errors (LWE) problem. Our construction builds upon the structure of the fully homomorphic signature scheme of Gorbunov et al. [GVW15]. In their construction, a signature consists of a preimage of a specially formed target matrix of a lattice trapdoor function. To make key leakage a feature rather than a form of insecurity, we carefully hash the messages to derive the target matrix such that two different message of the same subject leads to two matrices for which two preimage matrices leak a trapdoor. As in [PS14], we prove security in the random oracle model.

Also, as we discuss above, we extend DAPS to a more general primitive that we call predicate authentication preventing signatures (PAPS). In this setting, signatures of any messages that satisfy a certain predicate defined on these messages leak a signer’s secret key. To motivate the notion, we show that for certain simple, but useful predicates, PAPS can already be constructed from DAPS.

Finally, we further extend PAPS to a multi-authority settings where signatures from different signers can also leak some shared private information. We give formal definitions in this setting and show that our lattice DAPS construction can be extended to this setting as well using the property that two short preimages of a specifically formed target matrix of lattice trapdoor functions can be merged to give a trapdoor of an extended lattice.

1.2 Related Work

Previous Works on DAPS. The notion of double-authentication-preventing signatures was introduced by Poettering and Stabila [PS14]. They provide a construction based on extractable trapdoor functions that can be constructed using the group of quadratic residues modulo a Blum integer. Subsequently, Bellare, Poettering, and Stebila [BPS15] gave a generic construction based on trapdoor identification schemes where the private randomness committed by the prover can be extracted using a trapdoor. We note that although lattice-based identification schemes have appeared in the literature [Lyu08, Lyu12], the construction from [PS14] does not directly give a lattice-based DAPS construction since lattice trapdoors are randomized with multiple preimages. Constructing DAPS from lattice-based assumptions is an interesting and important goal since they provide hardness even against quantum computers, a setting for which the previous two works do not provide security.

Delegating Restricted Signing Keys. A number of works in the literature have focused on schemes that allow an authority to delegate signing keys with some restricted functionalities (with function privacy). These include attribute-based signatures [MPR11], functional signatures [BGI14] and policy-based signature [BF14]. In these schemes, a signer is restricted to sign only certain messages that satisfy a predicate requirement. One difference between these notions and DAPS/PAPS is that in the former, the restriction is done by a central authority to restrict other signers, while in the latter, the authority restricts itself as a self-enforcement mechanism. Another major difference is that in the former, the restriction is determined with respect to each individual message while in the latter, the restriction is determined by all of the past messages that the signer signs, which is what makes DAPS and PAPS an interesting theoretical notion.

Ring/Group Signatures. A similar notion of double-signing preventing mechanism exists in the setting of group signatures [TX03] and ring signatures [RST01, BKM06] called Revocable-iff-Linked (RiffL) signatures [ALSY06]. In this setting, a signer can sign on behalf of a group; however, if it signs twice or more, then the identity of the signer is leaked. As in the discussion of the previous paragraph, one difference in the DAPS setting compared to RiffL is that DAPS is a self-enforcing mechanism, which means that the linkability is not enforced by another trusted authority of the system, but by itself. However, the more fundamental difference is that in DAPS, the act of double-signing immediately gives away the signing key or private data rather than simply leaking the information that it double signed. As was discussed in [PS14], there are instances where simply leaking the fact that a CA double signed may not be enough of a penalty (i.e. the 2011 Comodo incident^{Footnote 1}) and DAPS is designed to cope with these type of situations.

Basic Notation. For an integer N, we write [N] to denote the set \(\left\{ 1,...,N \right\} \). We use bold lowercase letters (e.g., \({\mathbf {x}}, {\mathbf {w}}\)) to denote vectors and bold uppercase letters (e.g., \({\mathbf {A}}, {\mathbf {G}}\)) to denote matrices. For a matrix \({\mathbf {A}}\), we use \({\mathbf {A}}^T\) to denote the trasnpose of \({\mathbf {A}}\) and for a vector \({\mathbf {x}}\), we use \(\Vert {\mathbf {x}} \Vert \) to denote its Euclidean norm. In general, we write \(\lambda \) for the security parameters. We say a function \(\epsilon (\lambda )\) is negligible in \(\lambda \), if \(\epsilon (\lambda ) = o(1/\lambda ^c)\) for every \(c \in {\mathbb {N}}\), and we write \(\mathsf {negl}(\lambda )\) to denote a negligible function in \(\lambda \). We say that an event occurs with negligible probability if the probabilty of the event is \(\mathsf {negl}(\lambda )\), and an event occurs with overwhelming probability if its complement occurs with negligible probability.

Entropy and Statistical Distance. The statistical distance between two random variables X and Y over a finite domain \(\varOmega \) is defined as

We say that two distribution ensembles \(X = \left\{ X_\lambda \right\} _{\lambda \in {\mathbb {N}}}\) and \(Y = \left\{ Y_\lambda \right\} _{\lambda \in {\mathbb {N}}}\) are statistically indistinguishable, denoted \(\overset{\mathrm {stat}}{\approx }\), if it holds that \(\mathsf {SD}(X_\lambda , Y_\lambda )\) is negligible in \(\lambda \). The min-entropy of a random variable X, denoted \({\mathbf {H}}_{\infty }(X|Y)\), is defined as

The optimal probability of an unbounded adversary guessing X given the correlated value Y is \(2^{-{\mathbf {H}}_{\infty }(X|Y)}\).

2.1 Circular Security

In this section we briefly recall the notion of circular security. A public key encryption (PKE) consists of three algorithms \(\varPi _\mathsf{pke}= (\mathsf{PKE}.\mathsf {KeyGen}, \mathsf{PKE}.\mathsf {Encrypt}, \mathsf{PKE}.\mathsf {Decrypt})\) where \(\mathsf{PKE}.\mathsf {KeyGen}\) takes in a unary representation of the security parameter \(\lambda \) and outputs a public and secret key pair \((\mathsf {pk}, \mathsf {sk})\). The encryption algorithm takes in a public key \(\mathsf {pk}\) and a message m and generates a ciphertext \(\mathsf {ct}\). The decryption algorithm takes in a secret key \(\mathsf {sk}\) and a ciphertext \(\mathsf {ct}\) and outputs a message m. For correctness, we require that for all \(\lambda \in {\mathbb {N}}\), \((\mathsf {pk}, \mathsf {sk}) \leftarrow \mathsf{PKE}.\mathsf {KeyGen}(1^\lambda )\), we have that \(\mathsf{PKE}.\mathsf {Decrypt}(\mathsf {sk}, \mathsf{PKE}.\mathsf {KeyGen}(\mathsf {pk}, m)) = m\) with overwhelming probability.

Definition 1

(Circular Security [CL01, BRS02]). A public-key encryption scheme \(\varPi _\mathsf{pke}\) is circular secure if for all efficient adversaries \({{\mathcal {A}}}\), there is a negligible function \(\mathsf {negl}(\lambda )\) such that

where for each \(b \in \{0,1\}\), and \(\lambda \in {\mathbb {N}}\), the experient \(\mathsf {Expt}_\mathsf{PKE, {{\mathcal {A}}}}^{(b)}(\lambda )\) is defined as follows:

1. 1.

   \((\mathsf {pk}, \mathsf {sk}) \leftarrow \mathsf{PKE}.\mathsf {KeyGen}(1^\lambda )\).

2. 2.

   \(\mathsf {ct}_0 \leftarrow \mathsf{PKE}.\mathsf {Encrypt}(\mathsf {pk}, 0^{|\mathsf {sk}|})\).

3. 3.

   \(\mathsf {ct}_1 \leftarrow \mathsf{PKE}.\mathsf {Encrypt}(\mathsf {pk}, \mathsf {sk})\).

4. 4.

   \(b' \leftarrow {{\mathcal {A}}}(\mathsf {pk}, \mathsf {ct}_b)\).

5. 5.

   Output \(b' \in \{0,1\}\).

Circular security assumption on lattice-based cryptosystems have been used extensively throughout the literature [Gen09, BV11, BV14, BGV12, GSW13] with some positive results showing that some common forms of lattice-based encryption schemes can be shown to be circular secure [ACPS09, ASP12].

2.2 Broadcast Encryption

A broadcast encryption scheme \(\mathsf BE\) [FN93] consists of a tuple of algorithms \(\varPi _\mathsf{be}= (\mathsf{BE}.\mathsf {KeyGen}, \mathsf{BE}.\mathsf {Encrypt}, \mathsf{BE}.\mathsf {Decrypt})\) defined as follows:

1. 1.

   \(\mathsf{BE}.\mathsf {KeyGen}(1^\lambda , N) \rightarrow (\left\{ \mathsf {sk}_i \right\} _{i \in [N]}, \mathsf {pk})\): On input the security parameter \(\lambda \) and a positive integer \(N \in {\mathbb {N}}\), the key generation algorithm outputs a set of secret keys \(\left\{ \mathsf {sk}_i \right\} _{i \in [N]}\) and a public key \(\mathsf {pk}\).

2. 2.

   \(\mathsf{BE}.\mathsf {Encrypt}(\mathsf {pk}, \mathsf {msg}, T) \rightarrow \mathsf {ct}_T\): On input a public key \(\mathsf {pk}\), a message m, and a set of intended recipients \(T \subseteq [N]\), the encryption algorithm outputs a ciphertext \(\mathsf {ct}_T\).

3. 3.

   \(\mathsf{BE}.\mathsf {Decrypt}(\mathsf {sk}_i, \mathsf {ct}) \rightarrow m'\): On input a secret key \(\mathsf {sk}_i\) and a ciphertext \(\mathsf {ct}\), the decryption algorithm outputs a message \(m'\).

Correctness. For correctness we require that for all \(\lambda \in {\mathbb {N}}\), \(N \in {\mathbb {N}}\), \(T \subseteq [N]\), \((\left\{ \mathsf {sk}_i \right\} _{i \in [N]}, \mathsf {pk}) \leftarrow \mathsf{BE}.\mathsf {KeyGen}(1^\lambda , N)\), we have \(\mathsf{BE}.\mathsf {Decrypt}(\mathsf {sk}_i, \mathsf{BE}.\mathsf {Encrypt}(\mathsf {pk}, \mathsf {ct}, T)) = m\) for all \(i \in T\).

Security. For broadcast encryption scheme, we define the following security notion.

Definition 2

A broadcast encryption scheme \(\varPi _\mathsf{be}\) is secure if for all efficient adversaries \({{\mathcal {A}}}\), there is a negligible function \(\mathsf {negl}(\lambda )\) such that

where for each \(b \in \{0,1\}\), and \(\lambda \in {\mathbb {N}}\), the experiment \(\mathsf {Expt}_\mathsf{BE, {{\mathcal {A}}}}^{(b)}\) is defined as follows:

• \((\left\{ \mathsf {sk}_i \right\} _{i \in [N]}, \mathsf {pk}) \leftarrow \mathsf{BE}.\mathsf {KeyGen}(1^\lambda , N)\).

• \((T, m_0, m_1) \leftarrow {{\mathcal {A}}}_0(\mathsf {pk})\).

• \(\mathsf {ct}_b \leftarrow \mathsf{BE}.\mathsf {Encrypt}(\mathsf {pk}, m_b)\).

• \(b' \leftarrow {{\mathcal {A}}}_1(\left\{ \mathsf {sk}_i \right\} _{i \in [N] \backslash T}, \mathsf {ct}_b)\).

• Output \(b' \in \{0,1\}\).

A number of constructions for broadcast encryption schemes have been proposed in the literature  [FN93, BGW05, BWZ14] with short ciphertext where the length of the ciphertext scales sublinearly in the number of users in the system. For linear length ciphertext, a broadcast encryption scheme can be constructed generically from a regular public key encryption scheme by concatenating the N instances of the public key encryption schemes.

2.3 Background on Lattices

In this section, we describe some of the results and notations for lattice-based cryptography that are used throughout the paper.

Lattice and Gaussians. Let n, q, m be positive integers. For a matrix \({\mathbf {A}}\in {\mathbb {Z}}_q^{n \times m}\), we let \(\varLambda _q^{\bot }({\mathbf {A}})\) denote the lattice \(\left\{ {\mathbf {x}}\in {\mathbb {Z}}^m : {\mathbf {A}}\cdot {\mathbf {x}}= {\mathbf {0}}\mod q \right\} \). More generally, for \({\mathbf {u}}\in {\mathbb {Z}}_q^n\), we let \(\varLambda _q^{{\mathbf {u}}}({\mathbf {A}})\) denote the shifted lattice \(\left\{ {\mathbf {x}}\in {\mathbb {Z}}^m : {\mathbf {A}}\cdot {\mathbf {x}}= {\mathbf {u}}\mod q \right\} \).

Regev [Reg09] defined a natural distribution on \(\varLambda _q^{{\mathbf {u}}}({\mathbf {A}})\) called a discrete Gaussian parameterized by a scalar \(s > 0\). We use \({{\mathcal {D}}}_s(\varLambda _q^{{\mathbf {u}}}({\mathbf {A}}))\) to denote this distribution. For a random matrix \({\mathbf {A}}\in {\mathbb {Z}}_q^{n \times m}\) and \(s > {\widetilde{O}}(\sqrt{n})\), a vector \({\mathbf {x}}\) sampled from \({{\mathcal {D}}}_s(\varLambda _q^{{\mathbf {u}}}({\mathbf {A}}))\) has Euclidean norm less than \(s \sqrt{m}\) with overwhelming probability. For a matrix \({\mathbf {U}}= ({\mathbf {u}}_1 | \ldots | {\mathbf {u}}_k) \in {\mathbb {Z}}_q^{n \times k}\), we let \({{\mathcal {D}}}_s(\varLambda _q^{{\mathbf {U}}}({\mathbf {A}}))\) be a distribution on matrices in \({\mathbb {Z}}^{m \times k}\) where the i-th column is sampled from \({{\mathcal {D}}}_s(\varLambda _q^{{\mathbf {u}}_i}({\mathbf {A}}))\) for \(i=1, ..., k\).

The SIS Problem. Let \(n, m, q, \beta \) be positive integers. In the \(\mathrm {SIS}(n,m,q,\beta )\) problem, the adversary is given a uniformly random matrix \({\mathbf {A}}\in {\mathbb {Z}}_q^{n \times m}\) and its goal is to find a vector \({\mathbf {u}}\in {\mathbb {Z}}_q^m\) with \({\mathbf {u}}\ne {\mathbf {0}}\) and \(\Vert {\mathbf {u}} \Vert \le \beta \) such that \({\mathbf {A}}\cdot {\mathbf {u}}= {\mathbf {0}}\).

The SIS problem is known to be as hard as certain worst-case lattice problems. In particular, for any \(m = \mathsf {poly}(n)\), any \(\beta > 0\), and any sufficiently large \(q \ge \beta \cdot \mathsf {poly}(n)\), solving \(\mathrm {SIS}(n,m,q,\beta )\) is at least as hard as approximating certain worst-case lattice problems such as the Shortest Vector Problem (GapSVP) and the Short Independent Vectors Problem (SIVP) on n-dimensional lattices to within \(\beta \cdot \mathsf {poly}(n)\) factor [Ajt96, Mic04, MR07, MP13]. The hardness of \(\mathrm {SIS}\) is also implied by the \(\mathrm {LWE}\) problem.

The LWE Problem. Let n, m, q be positive integers and \(\chi \) a noise distribution over \({\mathbb {Z}}_q\). In the \(\mathrm {LWE}(n,m,q,\chi )\) problem, the adversary’s goal is to distinguish between the two distributions:

where \({\mathbf {A}}\overset{\$}{\leftarrow }{\mathbb {Z}}_q^{n \times m}\), \({\mathbf {s}}\overset{\$}{\leftarrow }{\mathbb {Z}}_q^{n}\), \({\mathbf {e}}\leftarrow \chi ^m\), and \({\mathbf {u}}\overset{\$}{\leftarrow }{\mathbb {Z}}_q^{m}\) are uniformly sampled.

We say that a noise distribution \(\chi \) is B-bounded if its support is in \([-B, B]\). For any fixed \(d>0\), and sufficiently large q, taking \(\chi \) as a certain \(q/n^d\)-bounded distribution, the \(\mathrm {LWE}(n, m, q, \chi )\) problem is as hard as approximating certain worst-case lattice problems such as GapSVP and SIVP on n-dimensional lattices to within \(\mathsf {poly}(n)\) factor [Reg09, Pei09, ACPS09, MM11, MP12, BLP+13].

Matrix Norms. For a matrix \({\mathbf {R}}\in {\mathbb {Z}}^{k \times m}\), we define the matrix norms:

• \(\Vert {\mathbf {R}} \Vert \) denotes the \(\ell _2\) length of the longest column of \({\mathbf {R}}\).

• \(\Vert {\mathbf {R}} \Vert _2\) is the operator norm of \({\mathbf {R}}\) defined as \(\Vert {\mathbf {R}} \Vert _2 = \sup _{\Vert {\mathbf {x}} \Vert =1} \Vert {\mathbf {R}}{\mathbf {x}} \Vert \).

Note that always \(\Vert {\mathbf {R}} \Vert \le \Vert {\mathbf {R}} \Vert _2 \le \sqrt{k} \Vert {\mathbf {R}} \Vert \) and that \(\Vert {\mathbf {R}}\cdot {\mathbf {S}} \Vert _2 \le \Vert {\mathbf {R}} \Vert _2 \cdot \Vert {\mathbf {S}} \Vert _2\).

Lattice Trapdoors. Here, we review the known results about lattice trapdoors which make the SIS and LWE problems easy to solve with knowledge such trapdoor. For this work, it is convenient to work with the notion of “gadget” based trapdoors as formalized in [MP12]. In such setting, there is a structured public gadget matrix \({\mathbf {G}}\in {\mathbb {Z}}_q^{n \times n \ell }\) for \(\ell = \lceil \log q \rceil \). A trapdoor for a matrix \({\mathbf {A}}\in {\mathbb {Z}}_q^{n \times m}\) is an integer matrix \({\mathbf {R}}\in {\mathbb {Z}}_q^{n \times n \ell }\) such that \({\mathbf {A}}{\mathbf {R}}= {\mathbf {H}}{\mathbf {G}}\) for some invertible matrix \({\mathbf {H}}\in {\mathbb {Z}}_q^{n \times n}\). The quality of a trapdoor is measured by the operator norm of \({\mathbf {R}}\) where the smaller norm \(\Vert {\mathbf {R}} \Vert _2\) means higher quality. We will often use the symbol \(\mathsf {{\mathbf {T}}_{\mathbf {A}}}\) to denote the trapdoor matrix \({\mathbf {R}}\).

Since the exact constructions and algorithm details of such trapdoors are not needed for this work, we abstract out these details and summarize the relevant results in the lemma below.

Lemma 1

([Ajt96, GPV08, AP11, MP12]). There exist polynomial time algorithms \(\mathsf {TrapGen}, \mathsf {SamPre}, \mathsf {Sam}, \mathsf {Invert}\) such that the following holds. Given positive integers \(n \ge 1, q \ge 2\), there exists \(m^* = O(n \log q)\) such that for \(k = \mathsf {poly}(n)\), we have:

• \(\mathsf {TrapGen}(1^n, 1^m, q) \rightarrow ({\mathbf {A}}, \mathsf {{\mathbf {T}}_{\mathbf {A}}})\): A randomized algorithm that when \(m \ge m^*\), outputs a full-rank matrix \({\mathbf {A}}\in {\mathbb {Z}}_q^{n \times m}\) and a trapdoor \(\mathsf {{\mathbf {T}}_{\mathbf {A}}}\in {\mathbb {Z}}^{m \times n \ell }\) such that \({\mathbf {A}}\) is statistically close to uniform and \(\Vert {\mathbf {R}} \Vert _2 = O(\sqrt{m})\).

• \(\mathsf {SamPre}({\mathbf {A}}, \mathsf {{\mathbf {T}}_{\mathbf {A}}}, {\mathbf {V}}, s) \rightarrow {\mathbf {U}}\): A randomized algorithm that on input \({\mathbf {A}}\in {\mathbb {Z}}_q^{n \times m}\), a trapdoor \(\mathsf {{\mathbf {T}}_{\mathbf {A}}}\) of \({\mathbf {A}}\), a matrix \({\mathbf {V}}\in {\mathbb {Z}}_q^{m \times k}\), and \(s = {\widetilde{O}}(\Vert \mathsf {{\mathbf {T}}_{\mathbf {A}}} \Vert _2)\), outputs a random sample \({\mathbf {U}}\in {\mathbb {Z}}^{m \times k}\) from the distribution \({{\mathcal {D}}}_{s}(\varLambda _q^{{\mathbf {V}}}({\mathbf {A}}))\).

• \(\mathsf {Sam}(1^m, 1^k, q, s) \rightarrow {\mathbf {U}}\): A randomized algorithm that samples a matrix \({\mathbf {U}}\in {\mathbb {Z}}^{m \times k}\) such that each of its column is sampled from \({{\mathcal {D}}}_{{\mathbb {Z}}^m, s}\). We have that for \(s \ge \omega (\sqrt{\log m})\) the matrix \({\mathbf {V}}= {\mathbf {A}}\cdot {\mathbf {U}}\) is statistically close to a uniform matrix in \({\mathbb {Z}}_q^{n \times k}\) and furthermore, the distribution of \({\mathbf {U}}\) given \({\mathbf {V}}\) is \({{\mathcal {D}}}_{s}(\varLambda _q^{{\mathbf {V}}}({\mathbf {A}}))\).

• \(\mathsf {Invert}({\mathbf {A}}, \mathsf {{\mathbf {T}}_{\mathbf {A}}}, {\mathbf {b}}) \rightarrow {\mathbf {s}}\): A deterministic algorithm that on input \({\mathbf {A}}\in {\mathbb {Z}}_q^{n \times m}\), a trapdoor \(\mathsf {{\mathbf {T}}_{\mathbf {A}}}\) of \({\mathbf {A}}\), and an LWE vector \({\mathbf {b}}= {\mathbf {A}}^T {\mathbf {s}}+ {\mathbf {e}}\) for \(\Vert {\mathbf {e}} \Vert \le q/O(\Vert \mathsf {{\mathbf {T}}_{\mathbf {A}}} \Vert _2)\), outputs the unique secret vector \({\mathbf {s}}\).

To simplify the notation, thoughout the paper, we will always assume that the gadget matrix \({\mathbf {G}}\) has the same width m as the matrix \({\mathbf {A}}\) output by the algorithm \(\mathsf {TrapGen}\).

2.4 FRD Encoding

In this section, we review an encoding function \(H: {\mathbb {Z}}_q^n \rightarrow {\mathbb {Z}}_q^{n \times n}\) that maps vectors in \({\mathbb {Z}}_q^n\) to invertible matrices in \({\mathbb {Z}}_q^{ n \times n}\) with the property that for any two distinct vectors \({\mathbf {u}}\) and \({\mathbf {v}}\), the difference between the outputs \(H({\mathbf {u}})\) and \(H({\mathbf {v}})\) is never singular, i.e., \(\det (H({\mathbf {u}}) - H({\mathbf {v}})) \ne 0\).

Definition 3

Let q be a prime and n a positive integer. We say that an efficiently computable function \(H: {\mathbb {Z}}_q^n \rightarrow {\mathbb {Z}}_q^{n \times n}\) is a full-rank difference (FRD) encoding scheme if for all distinct \({\mathbf {u}}, {\mathbf {v}}\in {\mathbb {Z}}_q^n\), the matrix \(H({\mathbf {u}}) - H({\mathbf {v}}) \in {\mathbb {Z}}_q^{n \times n}\) is full rank.

This notion was formalized in [ABB10] and an injective encoding function satisfying the definition was explicitly constructed by generating an additive subgroup \({{\mathcal {G}}}_{\mathrm {FRD}}\) of full-rank matrices by embedding ring multiplications into matrices (similar techniques were used in [CD09, PR06, LM06]). We do not explicitly provide the construction here and mainly use the result as a black box throughout this work.

In this section, we formally define the notion of predicate authentication preventing signatures (\(\mathsf{PAPS}\)) which generalizes the notion of double authentication preventing signatures (\(\mathsf{DAPS}\)) that was introduced in [PS14].

3.1 PAPS Framework

The syntax for predicate-authentication-preventing signatures largely coincides with the syntax for standard signature schemes with an additional extraction algorithm that can extract some private information of the signer (i.e. the signing key) given the signatures of messages that satisfy a particular predicate.

Definition 4

(PAPS). A predicate-authentication-preventing signature (PAPS) on a corresponding message space \({{\mathcal {M}}}\), and a predicate \(f: {{\mathcal {M}}}^k \rightarrow \{0,1\}\) is a tuple of efficient algorithms \(\varPi _\mathsf{paps}= (\mathsf{PAPS}.\mathsf {KeyGen}, \mathsf{PAPS}.\mathsf {Sign}, \mathsf{PAPS}.\mathsf {Verify}, \mathsf{PAPS}.\mathsf {Extract})\) defined as follows:

• \(\mathsf{PAPS}.\mathsf {KeyGen}(1^\lambda ) \rightarrow (\mathsf {sk}, \mathsf {vk})\): On input a security parameter \(1^\lambda \), the key generation algorithm \(\mathsf{PAPS}.\mathsf {KeyGen}\) outputs a signing key \(\mathsf {sk}\) and a verification key \(\mathsf {vk}\).

• \(\mathsf{PAPS}.\mathsf {Sign}(\mathsf {sk}, \mathsf {msg}) \rightarrow \sigma \): On input a signing key \(\mathsf {sk}\) and a message \(\mathsf {msg}\in {{\mathcal {M}}}\), the signing algorithm \(\mathsf{PAPS}.\mathsf {Sign}\) outputs a signature \(\sigma \).

• \(\mathsf{PAPS}.\mathsf {Verify}(\mathsf {vk}, \mathsf {msg}, \sigma )\): On input a verification key \(\mathsf {vk}\), a message \(\mathsf {msg}\in {{\mathcal {M}}}\), and a signature \(\sigma \), the verification algorithm \(\mathsf{PAPS}.\mathsf {Verify}\) accepts/rejects.

• \(\mathsf{PAPS}.\mathsf {Extract}(\mathsf {vk}, \left\{ (\mathsf {msg}_i, \sigma _i) \right\} _{i \in [k]}) \rightarrow \mathsf {sk}'\): On input a verification key \(\mathsf {vk}\), and a set of message and signature pairs, the extraction algorithm \(\mathsf{PAPS}.\mathsf {Extract}\) outputs the secret key \(\mathsf {sk}'\).

Correctness. We say that a PAPS scheme is correct if, for all \(\lambda \in {\mathbb {N}}\), \(\mathsf {msg}\in {{\mathcal {M}}}\), and \(\sigma \leftarrow \mathsf{PAPS}.\mathsf {Sign}(\mathsf {sk}, \mathsf {msg})\), we have that \(\mathsf{PAPS}.\mathsf {Verify}(\mathsf {vk}, \mathsf {msg}, \sigma ) = 1\).

3.2 Extraction

As in the case of [PS14], we can consider two notions of key extractability depending on whether the signer generates its keys at setup honestly or adversarially. We call the scenario for which the keys are always generated honestly as the \(trusted setup model \) and the scenario for which the keys can potentially be generated adversarially as the \(untrusted setup model \). Before defining these two notions formally, we first define the notion of a compromising set of signatures.

Definition 5

(Compromising set of signatures). Let \(f: {{\mathcal {M}}}^k \rightarrow \left\{ 0,1 \right\} \) be a predicate defined on k messages. Then, for a fixed verification key \(\mathsf {vk}\), a set of k message/signature pairs \(\left\{ (\mathsf {msg}_i, \sigma _i) \right\} _{i \in [k]}\) is f-compromising if each signature \(\sigma _i\) is a valid signature of \(\mathsf {msg}_i\) and the k messages satisfy the predicate f; that is, if \(\mathsf{PAPS}.\mathsf {Verify}(\mathsf {vk}, \mathsf {msg}_i, \sigma _i)=1\) for all \(i=1,...,k\) and \(f(\mathsf {msg}_1, ..., \mathsf {msg}_k) = 1\).

We now define formally the two notions of key extractability.

Definition 6

(Extractability in trusted setup). Fix a predicate \(f: {{\mathcal {M}}}^k \rightarrow \{0,1\}\). We say that a \(\mathsf{PAPS}\) scheme on a message space \({{\mathcal {M}}}\) is f-extractable in the trusted setup model if for all \(\lambda \in {\mathbb {N}}\), \(\mathsf {secret}\in {{\mathcal {S}}}\), for all key pairs \((\mathsf {sk}, \mathsf {vk}) \leftarrow \mathsf{PAPS}.\mathsf {KeyGen}(1^\lambda )\), and for all compromising set of signatures \(S = \left\{ (\mathsf {msg}_i, \sigma _i) \right\} _{i \in [k]}\), we have that \(\mathsf{PAPS}.\mathsf {Extract}(\mathsf {vk},S) = \mathsf {sk}\) with overwhelming probability.

For the untrusted setup model, instead of running the honest key generation algorithm, we allow an adversary to generate the keys along with a set of compromising set of signatures and require that the extraction algorithm succeeds on recovering the signing key from these set of signatures. Formally, we define extractability in the untrusted setup as follows.

Definition 7

(Extractability in untrusted setup). Fix a predicate \(f: {{\mathcal {M}}}^k \rightarrow \{0,1\}\). We say that a \(\mathsf{PAPS}\) scheme on a message space \({{\mathcal {M}}}\) is f-extractable if for all efficient adversary \({{\mathcal {A}}}\), we have that

Double-Authentication-Preventing Signatures. The notion of double-authentication-preventing signatures is a special case of \(\mathsf{PAPS}\). Specifically, in \(\mathsf{DAPS}\), the data to be signed \({{\mathcal {M}}}_{\mathsf{DAPS}}\) is split into two parts: a subject and a payload. Then, we consider the following 2-ary predicate in this message space

The predicate is designed specifically for the certificate authority setting where a CA that signs two different messages pertaining to the same subject is penalized by leaking the CA’s signing key. In this work, we will mainly focus on constructing \(\mathsf{PAPS}\) for this particular predicate function.

Remark. An alternative formulation of extractability is allowing some private information of the signer to be extracted instead of the signing key. In this case, the key generation algorithm can take in some secret information to be leaked by a compromising set of signatures and generate the keys accordingly. This formulation generalizes the notion above where extraction always leaks the signing key and can be more befitting for certain applications (see Sect. 7).

3.3 Unforgeability

The security game for the unforgeability notion for \(\mathsf{PAPS}\) is similar to the standard unforgeability notion for digital signatures where the adversary has access to a signing oracle and wins if it forges a new signature. However, since PAPS is designed precisely to leak the signing key on a compromising set of signatures, we require that the adversary’s queries to the signing oracle is limited to non-compromising sets of signatures.

Definition 8

(Unforgeability). An f-extractable \(\mathsf{PAPS}\) scheme \(\varPi _\mathsf{paps}= (\mathsf{PAPS}.\mathsf {KeyGen}, \mathsf{PAPS}.\mathsf {Sign}, \mathsf{PAPS}.\mathsf {Verify}, \mathsf{PAPS}.\mathsf {Extract})\) is unforgeable if for all efficient adversary \({{\mathcal {A}}}\), we have that

where the experiment \(\mathsf {Expt}_{\varPi _\mathsf{paps}, {{\mathcal {A}}}, \mathsf {uf}}\) is defined as follows:

1. 1.

   \((\mathsf {sk}, \mathsf {vk}) \leftarrow \mathsf{PAPS}.\mathsf {KeyGen}(1^\lambda )\).

2. 2.

   \((\mathsf {msg}^*, \sigma ^*) \leftarrow {{\mathcal {A}}}_1^{{{\mathcal {O}}}_{\mathsf {Sign}}(\cdot )}(\mathsf {vk})\).

3. 3.

   \({{\mathcal {A}}}\) wins if \(\mathsf {Verify^*}(\mathsf {msg}^*, \sigma ^*)\) accepts.

where the signing oracle \({{\mathcal {O}}}_{\mathsf {Sign}}(\cdot )\) and \(\mathsf {Verify^*}(\cdot , \cdot )\) are defined as follows:

• Oracle \({{\mathcal {O}}}_{\mathsf {Sign}}(\cdot )\) maintains a list \(\mathrm {SignedList}\) of all the previous valid queries made by \({{\mathcal {A}}}\). For a query \(\mathsf {msg}\), that the adversary makes, \({{\mathcal {O}}}_{\mathsf {Sign}}(\cdot )\) checks whether there exists a compromising set of signatures in \(\mathrm {SignedList}\cup \left\{ \mathsf {msg} \right\} \). If this is the case, then \({{\mathcal {O}}}_{\mathsf {Sign}}(\cdot )\) outputs \(\bot \). Otherwise, it outputs \(\mathsf{PAPS}.\mathsf {Sign}(\mathsf {sk}, \mathsf {msg})\).

• Verifier \(\mathsf {Verify^*}(\mathsf {msg}, \sigma )\) accepts if \(\mathsf {msg}\notin \mathrm {SignedList}\) and \(\mathsf{PAPS}.\mathsf {Verify}(\mathsf {vk}, \mathsf {msg}, \sigma )\) accepts.

In this section, we describe our DAPS construction. For clarity of exposition, we first describe a variant of the dual-Regev encryption scheme [GPV08] which we will use in our construction as a blackbox. This way, we can abstract out the details of the encryption component and present our \(\mathsf{DAPS}\) construction in a simpler and more intuitive way. After presenting our \(\mathsf{DAPS}\) construction, we prove its extractable properties and also show that its security can be based on the security of the encryption scheme and the SIS hardness assumption.

4.1 Trapdoor Dual-Regev Encryption

In this section, we describe a simple variant of the dual-Regev encryption scheme [GPV08] that we will use as a blackbox for our \(\mathsf{DAPS}\) construction. We present the encryption scheme here mainly for clarity of exposition and the only difference between the encryption scheme presented here and the original dual-Regev encryption scheme is the use of full trapdoors as the secret key of the scheme as opposed to a short preimage vector as is the case in [GPV08].

We use n as the security parameter \(\lambda \). Let m, q be the trapdoor parameters dependent on n (Lemma 1). Let \(\chi \) be a B-bounded noise distribution where \(B = O(q/m)\). We construct a public key encryption scheme \(\varPi _\mathsf{pke}= (\mathsf{PKE}.\mathsf {KeyGen}, \mathsf{PKE}.\mathsf {Encrypt}, \mathsf{PKE}.\mathsf {Decrypt})\) as follows:

• \(\mathsf{PKE}.\mathsf {KeyGen}(1^n)\): On input the security parameters \(1^n\), the key generation algorithm generates trapdoor \(({\mathbf {A}}, \mathsf {{\mathbf {T}}_{\mathbf {A}}}) \leftarrow \mathsf {TrapGen}(1^n, 1^m, q)\) where \({\mathbf {A}}\in {\mathbb {Z}}_q^{n \times m}\). It sets the public key \(\mathsf {pk}= {\mathbf {A}}\) and \(\mathsf {sk}= \mathsf {{\mathbf {T}}_{\mathbf {A}}}\).

• \(\mathsf{PKE}.\mathsf {Encrypt}(\mathsf {pk}, m)\): On input the public key \(\mathsf {pk}\) and a message \(m \in \{0,1\}\), the encryption algorithm samples uniformly random vectors \({\mathbf {d}}, {\mathbf {s}}\overset{\$}{\leftarrow }{\mathbb {Z}}_q^n\), and an error vector from the noise distribution \({\mathbf {e}}\leftarrow \chi ^{m+1}\). It computes the vector

  $$\begin{aligned} {\mathbf {b}}= [{\mathbf {A}} | {\mathbf {d}}]^T {\mathbf {s}}+ {\mathbf {e}}+ [{\mathbf {0}} | \lceil q/2 \rceil \cdot m]. \end{aligned}$$

  It outputs the ciphertext \(\mathsf {ct}= ({\mathbf {d}}, {\mathbf {b}}) \in {\mathbb {Z}}_q^n \times {\mathbb {Z}}_q^{m+1}\).

• \(\mathsf{PKE}.\mathsf {Decrypt}(\mathsf {sk}, \mathsf {ct})\): On input the secret key \(\mathsf {sk}\) and a ciphertext \(\mathsf {ct}= ({\mathbf {d}}, {\mathbf {b}})\), the decryption algorithm parses \({\mathbf {b}}= ({\mathbf {b}}_0, b_1)\). It then computes \({\mathbf {s}}\leftarrow \mathsf {Invert}({\mathbf {A}}, \mathsf {{\mathbf {T}}_{\mathbf {A}}}, {\mathbf {b}})\) and \(m' = b_1 - {\mathbf {d}}^T {\mathbf {s}}\). It outputs \(m \in \{0,1\}\) such that \(m'\) is close to \(\lceil q/2 \rceil \cdot m\).

Correctness. Let \({\mathbf {b}}= ({\mathbf {b}}_0 = {\mathbf {A}}^T {\mathbf {s}}+ {\mathbf {e}}_0, b_1 = {\mathbf {d}}^T {\mathbf {s}}+ e_1)\). The \(\mathsf {TrapGen}\) algorithm outputs a trapdoor \(\mathsf {{\mathbf {T}}_{\mathbf {A}}}\) such that \(\Vert \mathsf {{\mathbf {T}}_{\mathbf {A}}} \Vert _2 = O(\sqrt{m})\). This means that for \(B = O(q/\Vert \mathsf {{\mathbf {T}}_{\mathbf {A}}} \Vert \sqrt{m}) = O(q/m)\), the algorithm \(\mathsf {Invert}({\mathbf {A}}, \mathsf {{\mathbf {T}}_{\mathbf {A}}}, {\mathbf {b}})\) for \({\mathbf {b}}= {\mathbf {A}}^T {\mathbf {s}}+ {\mathbf {e}}\) correctly outputs the secret vector \({\mathbf {s}}\). Then, \(b_1 - {\mathbf {d}}^T {\mathbf {s}}= ({\mathbf {d}}^T {\mathbf {s}}+ e_1 + \lceil q/2 \rceil \cdot m) - {\mathbf {d}}^T {\mathbf {s}}= \lceil q/2 \rceil \cdot m + \cdot e_1\) which is correctly decoded for given bound on the error distribution \(\chi \).

Remark. We note that the correctness still holds with a different trapdoor \(\mathsf {{\mathbf {T}}_{\mathbf {A}}}'\) for which \(\mathsf {{\mathbf {T}}_{\mathbf {A}}}\ne \mathsf {{\mathbf {T}}_{\mathbf {A}}}'\) as long as \(\mathsf {{\mathbf {T}}_{\mathbf {A}}}'\) is of sufficient quality. In fact, we can flexibly adjust the parameter B for the noise distribution \(\chi \) of the scheme to allow for correct decryption by a slightly lower quality trapdoor. For instance, if we take the parameter to be \(B = O(q/m^{3/2})\), then a trapdoor \(\mathsf {{\mathbf {T}}_{\mathbf {A}}}'\) of quality \(\Vert \mathsf {{\mathbf {T}}_{\mathbf {A}}}' \Vert _2 \le O(m)\) can correctly decrypt the ciphertext. This property will be used for the extractability of our \(\mathsf{DAPS}\) construction.

Security. The security reduction easily follows from the security proof of the original dual-Regev encryption scheme and we do not reproduce it here.

Theorem 1

The PKE scheme above is IND-CPA secure assuming that the \(LWE(n,m,q,\chi )\) problem is hard.

For our \(\mathsf{DAPS}\) construction, we will also assume that the dual-Regev PKE scheme above is circular secure.

4.2 DAPS Construction

We present our construction for DAPS from lattices. Fix a security parameter \(n \in {\mathbb {N}}\) and let m, q, s be the corresponding trapdoor parameters. We use a hash function \(\mathsf{H}_{\mathsf {msg}}: \{0,1\}^* \times \{0,1\}^* \rightarrow {\mathbb {Z}}_q^{n \times n}\) that maps arbitrary messages to a full rank matrix in \({{\mathcal {G}}}_{\mathrm {FRD}}\) and a hash function \(\mathsf{H}_{\mathsf {subj}}: \{0,1\}^* \rightarrow {\mathbb {Z}}_q^{n \times m}\) that maps a subject to an SIS matrix for the scheme. We also use the dual-Regev public key encryption scheme \(\varPi _\mathsf{pke}= (\mathsf{PKE}.\mathsf {KeyGen}, \mathsf{PKE}.\mathsf {Encrypt}, \mathsf{PKE}.\mathsf {Decrypt})\) as decribed in Sect. 4.1 with a B-bounded noise distribution where \(B = O(q/m^{3/2})\). We construct \(\varPi _\mathsf{daps}= (\mathsf{DAPS}.\mathsf {KeyGen}, \mathsf{DAPS}.\mathsf {Sign}, \mathsf{DAPS}.\mathsf {Verify}, \mathsf{DAPS}.\mathsf {Extract})\) as follows:

• \(\mathsf{DAPS}.\mathsf {KeyGen}(1^n)\): On the security parameter \(1^n\), the key generation algorithm first runs \(({\mathbf {A}}, \mathsf {{\mathbf {T}}_{\mathbf {A}}}) \leftarrow \mathsf{PKE}.\mathsf {KeyGen}(1^n)\). It then encrypts \(\mathsf {ct}\leftarrow \mathsf{PKE}.\mathsf {Encrypt}({\mathbf {A}}, \mathsf {{\mathbf {T}}_{\mathbf {A}}})\) and set \(\mathsf {sk}= \mathsf {{\mathbf {T}}_{\mathbf {A}}}\) and \(\mathsf {vk}= ({\mathbf {A}}, \mathsf {ct})\).

• \(\mathsf{DAPS}.\mathsf {Sign}(\mathsf {sk}, \mathsf {subj}, \mathsf {payload})\): On input the signing key \(\mathsf {sk}\), a subject \(\mathsf {subj}\), and a message \(\mathsf {payload}\), the signing algorithm hashes the message \({\mathbf {H}}_{\mathsf {msg}} \leftarrow \mathsf{H}_{\mathsf {msg}}(\mathsf {subj}, \mathsf {payload})\) and also hashes the subject \({\mathbf {B}}_\mathsf {subj}\leftarrow \mathsf{H}_{\mathsf {subj}}(\mathsf {subj})\). Then, it computes

  $$\begin{aligned} {\mathbf {U}}\leftarrow \mathsf {SamPre}({\mathbf {A}}, \mathsf {{\mathbf {T}}_{\mathbf {A}}}, {\mathbf {B}}_\mathsf {subj}+ {\mathbf {H}}_\mathsf {msg}\cdot {\mathbf {G}}, s) \end{aligned}$$

  where \({\mathbf {G}}\) is the publicly known gadget matrix. Finally, it outputs \({\mathbf {U}}\) as the signature.

• \(\mathsf{DAPS}.\mathsf {Verify}(\mathsf {vk}, \mathsf {subj}, \mathsf {payload}, \sigma )\): On input the verification key \(\mathsf {vk}\), a subject \(\mathsf {subj}\), a message \(\mathsf {payload}\), and a signature \(\sigma = {\mathbf {U}}\), the algorithm hashes the message \({\mathbf {H}}_\mathsf {msg}\leftarrow \mathsf{H}_{\mathsf {msg}}(\mathsf {subj}, \mathsf {payload})\) and also derives the matrix \({\mathbf {B}}_\mathsf {subj}\leftarrow \mathsf{H}_{\mathsf {subj}}(\mathsf {subj})\). Then, the algorithm verifies that

  $$\begin{aligned} {\mathbf {A}}\cdot {\mathbf {U}}= {\mathbf {B}}_\mathsf {subj}+ {\mathbf {H}}_\mathsf {msg}\cdot {\mathbf {G}}\end{aligned}$$

  and that \(\Vert {\mathbf {U}} \Vert \le s \cdot \sqrt{m}\).

• \(\mathsf{DAPS}.\mathsf {Extract}(\mathsf {vk}, (\mathsf {subj}_1, \mathsf {payload}_1, \sigma _1), (\mathsf {subj}_2, \mathsf {payload}_2, \sigma _2))\): On input a verification key \(\mathsf {vk}= ({\mathbf {A}}, \mathsf {ct})\), and two subject/message pairs \((\mathsf {subj}_1, \mathsf {payload}_1)\), \((\mathsf {subj}_2, \mathsf {payload}_2)\) and their signatures \(\sigma _1 = {\mathbf {U}}_1, \sigma _2 = {\mathbf {U}}_2\), the extraction algorithm runs \(\mathsf {sk}' \leftarrow \mathsf{PKE}.\mathsf {Decrypt}({\mathbf {U}}_1 - {\mathbf {U}}_2)\) and outputs \(\mathsf {sk}'\).

Signing Correctness. The correctness follows easily from the correctness of the trapdoor algorithm \(\mathsf {SamPre}\) (Lemma 1) and the tail bounds of discrete Gaussian.

Security and Extrability. We now state the security and extractability of the construction above.

Theorem 2

The \(\mathsf{DAPS}\) construction above is unforgeable assuming the hardness of \(\mathrm {SIS}(n, m, q, \beta )\) for \(\beta = O(s)\) and circular security of \(\varPi _\mathsf{pke}\) modeling the hash functions \(\mathsf{H}_{\mathsf {msg}}\) and \(\mathsf{H}_{\mathsf {subj}}\) as random oracles.

Theorem 3

Assuming \(\mathsf{H}_{\mathsf {msg}}\) as a collision-resistant hash function, the \(\mathsf{DAPS}\) construction above is \(F_{\mathsf{DAPS}}\)-extractable.

In this work, we provide sample \(\mathsf{PAPS}\) constructions for a number of simple predicates. Due to space limitations, we describe and prove our constructions in the full version.

For many practical situations, there is not a single authority signer, but multiple authorities who sign messages. For these type of situations, it is useful to extend the \(\mathsf{PAPS}\) framework to the multi-authority setting where any compromising set of signatures by the different authorities reveals some private information of the signers.

We note that in this scenario, allowing a compromising set of signatures to reveal a secret key of a signer is not well-formulated in that any signer can compute a compromising set of signatures itself using its own signing key and extract another signer’s secret key. Therefore, for the multi-authority setting, we let the extraction algorithm to reveal some predefined private data and define an additional algorithm \(\mathsf{PAPS}.\mathsf {CommGen}\) that takes in this private information that we denote by \(\mathsf {secret}\) of a subset of the signers and generates a commitment \(\mathsf {comm}\) pertaining to \(\mathsf {secret}\). For correctness, we require that a compromising set of signatures from these subset of signers along with the commitment \(\mathsf {comm}\) allow anyone to reveal the private information \(\mathsf {secret}\).

Definition 9

(Multi-authority PAPS). A multi-authority predicate-authentication-preventing signature (MAPAPS) on a corresponding message space \({{\mathcal {M}}}\), secret space \({{\mathcal {S}}}\), and a predicate \(f:{{\mathcal {M}}}^k \rightarrow \{0,1\}\) is a tuple of efficient algorithms consisting of the \(\mathsf{PAPS}\) algorithms \(\varPi _\mathsf{paps}= (\mathsf{PAPS}.\mathsf {KeyGen}, \mathsf{PAPS}.\mathsf {Sign}, \mathsf{PAPS}.\mathsf {Verify},\) \(\mathsf{PAPS}.\mathsf {Extract})\) with two additional algorithms \((\mathsf{PAPS}.\mathsf {CommGen}, \mathsf{PAPS}.\mathsf {CommExtract})\) defined as follows:

• \(\mathsf{PAPS}.\mathsf {CommGen}(\left\{ \mathsf {vk}_i \right\} , \mathsf {secret}) \rightarrow \mathsf {comm}_T\): On input a set of verification keys \(T = \left\{ \mathsf {vk}_i \right\} \) and some private data \(\mathsf {secret}\in {{\mathcal {S}}}\), the commitment generation algorithm generates a public commitment \(\mathsf {comm}_T\).

• \(\mathsf{PAPS}.\mathsf {CommExtract}(\mathsf {comm}_T, \left\{ (\mathsf {msg}_i, \sigma _i) \right\} _{i \in [k]}) \rightarrow \mathsf {secret}'\): On input a public commitment \(\mathsf {comm}_T\), and a set of message and signature pairs, the extraction algorithm outputs private date \(\mathsf {secret}'\).

Informally speaking, the \(\mathsf{PAPS}.\mathsf {CommGen}\) takes in a set of verification keys of the signers and generates a hiding commitment of some private data that belongs to these signers. On a compromising set of signatures produced by any of these signers allows anyone to extract this private information using the \(\mathsf{PAPS}.\mathsf {CommExtract}\) algorithm.

Correctness. As in the regular \(\mathsf{PAPS}\) setting, we require that the algorithms \(\mathsf{PAPS}.\mathsf {KeyGen}, \mathsf{PAPS}.\mathsf {Sign}, \mathsf{PAPS}.\mathsf {Verify}\) satisfies the signing correctness requirement as in Sect. 3.

6.1 Extractability

In addition to the extractability property of \(\mathsf{PAPS}.\mathsf {Extract}\) in the single authority setting as in Sect. 3, we require an additional extractability in the multi-authority case where it is required that \(\mathsf{PAPS}.\mathsf {CommExtract}\) extract private information from the public commitment \(\mathsf {comm}\).

Definition 10

Let \(f: {{\mathcal {M}}}^k \rightarrow \{0,1\}\) be a predicate defined on k messages and \(T = \left\{ \mathsf {vk}_i \right\} \) be a set of verification keys. Then, a set of k message/signature pairs \(\left\{ (\mathsf {msg}_j, \sigma _j) \right\} _{j \in [k]}\) is f-compromising with respect to T if each signature \(\sigma _j\) is a valid signature of \(\mathsf {msg}_j\) by some verification key \(\mathsf {vk}_i \in T\), and the k messages satisfy the predicate f; that is, if for all \(j \in [k]\), \(\mathsf{PAPS}.\mathsf {Verify}(\mathsf {vk}_i, \mathsf {msg}_j, \sigma _j) = 1\) for some \(\mathsf {vk}_i \in T\) and \(f(\mathsf {msg}_1, ..., \mathsf {msg}_k) = 1\).

We define the standard extractability condition as follows.

Definition 11

Fix a predicate \(f:{{\mathcal {M}}}^k \rightarrow \{0,1\}\). We say that a \(\mathsf{MAPAPS}\) scheme on a message space \({{\mathcal {M}}}\) is f-commitment-extractable if for all \(\lambda \in N\), \(\mathsf {secret}\in {{\mathcal {S}}}\), a set of verification keys \(T = \left\{ \mathsf {vk}_i \right\} \), \(\mathsf {comm}_T \leftarrow \mathsf{PAPS}.\mathsf {CommGen}(T, \mathsf {secret})\) and for all compromising set of signatures \(S = \left\{ (\mathsf {msg}_j, \sigma _j) \right\} _{j \in [k]}\) with respect to T, we have that \(\mathsf{PAPS}.\mathsf {CommExtract}(\mathsf {comm}_T, S) = \mathsf {secret}\) with overwhelming probability.

6.2 Security

Commitment Privacy. To prevent the extractability notion above from being satisfied trivially, we require a privacy requirement on the secret data of \(\mathsf{PAPS}\). Specifically, we require that an adversary with access limited to non-compromising sets of signatures do not learn information about the secret data. Let N be the number of authorities in the system.

Definition 12

(Privacy). An f-extractable \(\mathsf{PAPS}\) scheme \(\varPi _\mathsf{paps}= (\mathsf{PAPS}.\mathsf {KeyGen},\) \(\mathsf{PAPS}.\mathsf {CommGen}, \mathsf{PAPS}.\mathsf {Sign}, \mathsf{PAPS}.\mathsf {Verify}, \mathsf{PAPS}.\mathsf {CommExtract})\) is data-hiding if for any efficient adversary \({{\mathcal {A}}}\), we have that

where \(\mathsf {Expt}_{\varPi _\mathsf{paps}, {{\mathcal {A}}}, \mathsf {dh}}^{(b)}\) is defined as follows:

1. 1.

   \((\mathsf {sk}_i, \mathsf {vk}_i) \leftarrow \mathsf{PAPS}.\mathsf {KeyGen}(1^\lambda )\) for \(i = 1, ..., N\).

2. 2.

   \((T, \mathsf {secret}_0, \mathsf {secret}_1) \leftarrow {{\mathcal {A}}}_0(\left\{ \mathsf {vk} \right\} _{i \in [N]})\).

3. 3.

   \(\mathsf {comm}_b \leftarrow \mathsf{PAPS}.\mathsf {CommGen}(\left\{ \mathsf {vk}_i \right\} _{t \in T}, \mathsf {secret}_b)\).

4. 4.

   Output \({{\mathcal {A}}}_1^{{{\mathcal {O}}}_{\mathsf {Sign}}(\cdot , \cdot )}(\left\{ \mathsf {sk}_i \right\} _{i \in [N] \backslash T}, \mathsf {comm}_b)\).

where the signing oracle \({{\mathcal {O}}}_{\mathsf {Sign}}(\cdot , \cdot )\) is defined as follows:

• Oracle \({{\mathcal {O}}}_{\mathsf {Sign}}(\cdot , \cdot )\) maintains a list \(\mathrm {SignedList}\) of all the previous valid queries made by \({{\mathcal {A}}}\). For a query \(\mathsf {msg}\) and an index \(i \in T\), that the adversary makes \({{\mathcal {O}}}_{\mathsf {Sign}}(\cdot , \cdot )\) checks whether there exists a compromising set of signatures with respect to T in \(\mathrm {SignedList}\cup \left\{ \mathsf {msg} \right\} \). If this is the case, the \({{\mathcal {O}}}_{\mathsf {Sign}}(\cdot , \cdot )\) outputs \(\bot \). Otherwise, it outputs \(\mathsf{PAPS}.\mathsf {Sign}(\mathsf {sk}, \mathsf {msg})\).

In this section we describe our construction of \(\mathsf{DAPS}\) in the setting of multi-authority. We describe the scheme for the \(\mathsf{DAPS}\) predicate, but the extensions in Sect. 5 translate directly to the multi authority setting since it uses the \(\mathsf{DAPS}\) predicate as a black box. As in Sect. 4, we first describe a broadcast encryption scheme from the variant of the dual-Regev encryption scheme and then present our \(\mathsf{MADAPS}\) construction using the broadcast encryption scheme. We prove that our scheme satisfies both the extractability and security requirements.

7.1 Broadcast Encryption

In this section, we present the broadcast encryption scheme. For clarity, we slightly alter the syntax of broadcast encryption where the global public key \(\mathsf {pk}\) is divided into a number of public keys \(\mathsf {pk}_i\) for each user in the system and the encryption algorithm takes in a subset of these public keys. Fix a security parameter n and let m, q, and \(\chi \) be the corresponding parameter as in Sect. 4.1. We construct \(\varPi _\mathsf{be}= (\mathsf{BE}.\mathsf {KeyGen}, \mathsf{BE}.\mathsf {Encrypt}, \mathsf{BE}.\mathsf {Decrypt})\) as follows:

• \(\mathsf{BE}.\mathsf {KeyGen}(1^n, N)\): On input the security parameter \(1^n\), the key generation algorithm generates trapdoors \(({\mathbf {A}}_i, \mathsf {{\mathbf {T}}_{\mathbf {A}}}_i) \leftarrow \mathsf {TrapGen}(1^n, 1^m, q)\) for \(i=1, ..., N\). It outputs \(\left\{ ({\mathbf {A}}_i, \mathsf {{\mathbf {T}}_{\mathbf {A}}}_i) \right\} _{i \in [N]}\).

• \(\mathsf{BE}.\mathsf {Encrypt}(\left\{ \mathsf {pk}_i \right\} _{i \in T}, m)\): On input a set of public keys \(\left\{ \mathsf {pk}_i \right\} _{i \in T} = \left\{ {\mathbf {A}}_i \right\} _{i \in T}\) and a message \(m \in \{0,1\}\), the encryption algorithm first samples uniformly random vectors \({\mathbf {d}}, {\mathbf {s}}\overset{\$}{\leftarrow }{\mathbb {Z}}_q^n\) and error vector \({\mathbf {e}}_0 \leftarrow \chi ^m\) and then computes

  $$\begin{aligned} \mathsf {ct}_0 = {\mathbf {d}}^T {\mathbf {s}}+ {\mathbf {e}}_0 + \lceil q/2 \rceil \cdot m \end{aligned}$$

  Then for \(t \in T\), it generates a fresh error vector from the noise distribution \({\mathbf {e}}_t \leftarrow \chi ^{m}\) and computes

  $$\begin{aligned} \mathsf {ct}_t = {\mathbf {A}}_t ^T {\mathbf {s}}+ {\mathbf {e}}_t \end{aligned}$$

  It outputs \(\mathsf {ct}_T = (\mathsf {ct}_0, \left\{ \mathsf {ct}_t \right\} _{t \in T})\).

• \(\mathsf{BE}.\mathsf {Decrypt}(\mathsf {sk}_i, \mathsf {ct}_T)\): On input the secret key \(\mathsf {sk}_i\) for \(i \in T\) and a ciphertext \(\mathsf {ct}_T = (\mathsf {ct}_0, \left\{ \mathsf {ct}_t \right\} _{t \in T})\), the decryption algorithm computes \({\mathbf {s}}\leftarrow \mathsf {Invert}({\mathbf {A}}, \mathsf {{\mathbf {T}}_{\mathbf {A}}}, \mathsf {ct}_i)\). It then computes \(m' = \mathsf {ct}_0 - {\mathbf {d}}^T {\mathbf {s}}\) and output \(m \in \{0,1\}\) such that \(m'\) is closest to \(\lceil q/2 \rceil \cdot m\).

We note that each ciphertext component \((\mathsf {ct}_0, \mathsf {ct}_i)\) makes up a regular ciphertext of the dual-Regev encryption scheme. Therefore, the correctness of the \(\mathsf BE\) scheme above follows directly from the correctness of the dual-Regev scheme. Also, the construction of the scheme above is a generic concatenation of the regular public key encryption scheme and therefore, the security follows directly from the security of the public key encryption scheme.

As in the case of the dual-Regev public key encryption scheme, one can correctly decrypt the ciphertext even with a different trapdoor for the public matrices \({\mathbf {A}}_i\) as long as it is of sufficient quality. Furthermore, any trapdoor of a concatenated matrix \([{\mathbf {A}}_i | {\mathbf {A}}_j]\) is sufficient to recover the encryption randomness used in the encryption and therefore decrypt a ciphertext intended for users i and j. More formally, there exists a decryption algorithm as follows:

• \(\mathsf{BE}.\mathsf {Decrypt}'(\mathsf {sk}_{i,j}, \mathsf {ct}_T)\): On input a trapdoor \(\mathsf {sk}_{i,j} = {\mathbf {T}}_{[{\mathbf {A}}_i | {\mathbf {A}}_j]}\) for \(i,j \in T\), and a ciphertext \(\mathsf {ct}_T = (\mathsf {ct}_0, \left\{ \mathsf {ct}_t \right\} _{t \in T})\), the decryption algorithm computes \({\mathbf {s}}\leftarrow \mathsf {Invert}([{\mathbf {A}}_i | {\mathbf {A}}_j], \mathsf {{\mathbf {T}}_{\mathbf {A}}}, [\mathsf {ct}_i | \mathsf {ct}_j])\). It then computes \(m' = \mathsf {ct}_0 - {\mathbf {d}}^T {\mathbf {s}}\) and outputs \(m \in \{0,1\}\) such that \(m'\) is closest to \(\lceil q/2 \rceil \cdot m\).

7.2 Multi-authority DAPS Construction

In this section, we extend the \(\mathsf{DAPS}\) construction from Sect. 4.2 to the multi-authority setting (\(\mathsf{MADAPS}\)). In addition to the algorithms in \(\varPi _\mathsf{daps}\), we define two additional algorithms \(\mathsf{DAPS}.\mathsf {CommGen}\) and \(\mathsf{DAPS}.\mathsf {CommExtract}\) as defined in Sect. 6. Let \(\varPi _\mathsf{be}= (\mathsf{BE}.\mathsf {KeyGen}, \mathsf{BE}.\mathsf {Encrypt}, \mathsf{BE}.\mathsf {Decrypt})\) be the broadcast encryption scheme as defined above with B-bounded noise distribution \(\chi \) where \(B = O(q/m^{3/2})\). Fix a security parameter \(n \in {\mathbb {N}}\) and let m, q, s be the corresponding trapdoor parameters. We define the algorithms \(\mathsf{DAPS}.\mathsf {CommGen}\) and \(\mathsf{DAPS}.\mathsf {CommExtract}\) as follows:

• \(\mathsf{DAPS}.\mathsf {CommGen}(\left\{ \mathsf {vk}_i \right\} , \mathsf {secret})\): On input a set of verification keys \(T = \left\{ \mathsf {vk}_i \right\} = \left\{ {\mathbf {A}}_i \right\} \) and some private data \(\mathsf {secret}\in {{\mathcal {S}}}\), the commitment generation algorithm computes \(\mathsf {ct}_T \leftarrow \mathsf{BE}.\mathsf {Encrypt}(T, \mathsf {secret})\) and sets \(\mathsf {comm}= \mathsf {ct}_T\).

• \(\mathsf{DAPS}.\mathsf {CommExtract}(\mathsf {comm}_T, (\mathsf {subj}_0, \mathsf {payload}_0, \sigma _0), (\mathsf {subj}_1, \mathsf {payload}_1, \sigma _1))\): On input the parameters \(\mathsf {comm}_T\) and a pair of compromising pair of signatures \(\sigma _0 = {\mathbf {U}}_i\) and \(\sigma _1 = {\mathbf {U}}_j\) corresponding to \(\mathsf {vk}_i\) and \(\mathsf {vk}_j\) respectively, the extraction algorithm concatenates the keys \({\tilde{{\mathbf {U}}}} = \left[ \begin{array}{c} {\mathbf {U}}_i \\ -{\mathbf {U}}_j \end{array} \right] \). It runs \(\mathsf {secret}' \leftarrow \mathsf{BE}.\mathsf {Decrypt}'({\tilde{{\mathbf {U}}}}, \mathsf {comm}_T)\) and outputs the private data \(\mathsf {secret}'\).

Extractability and Privacy. We now state the extractability and privacy properties of the \(\mathsf{MADAPS}\) construction above. We provide the proofs of the following theorems in the full version.

Theorem 4

Assuming \(\mathsf{H}_{\mathsf {msg}}\) is a collision-resistant hash function, the \(\mathsf{MADAPS}\) construction above is \(F_{\mathsf{DAPS}}\)-extractable.

Theorem 5

The \(\mathsf{MADAPS}\) construction above is data-hiding assuming that the broadcast encryption scheme \(\varPi _\mathsf{be}\) is secure.