Verifiably Encrypted Signatures: Security Revisited and a New Construction
- First Online:
Abstract
In structure-preserving signatures on equivalence classes (SPS-EQ-\(\mathcal {R}\)), introduced at \(\textsc {Asiacrypt}\) 2014, each message M in \((\mathbb {G}^*)^\ell \) is associated to its projective equivalence class, and a signature commits to the equivalence class: anybody can transfer the signature to a new, scaled, representative.
In this work, we give the first black-box construction of a public-key encryption scheme from any SPS-EQ-\(\mathcal {R}\) satisfying a simple new property which we call perfect composition. The construction does notinvolve any non-black-box technique and the implication is that such SPS-EQ-\(\mathcal {R}\) cannot be constructed from one-way functions in a black-box way. The main idea of our scheme is to build a verifiable encrypted signature (VES) first and then apply the general transformation suggested by Calderon et al. (CT-RSA 2014).
The original definition of VES requires that the underlying signature scheme be correct and secure in addition to other security properties. The latter have been extended in subsequent literature, but the former requirements have sometimes been neglected, leaving a hole in the security notion. We show that Calderon et al.’s notion of resolution independence fills this gap.
Keywords
Structure preserving signatures Verifiably encrypted signatures Resolution independence Public-key encryption1 Introduction
Structure-preserving signatures on equivalence classes (SPS-EQ-\(\mathcal {R}\)s) have been introduced at Asiacrypt 2014, and a corrected instantiation was given in a joint work with Fuchsbauer [9]. In an SPS-EQ-\(\mathcal {R}\), each message M is a vector of group elements from a group of prime order p, and a signature commits the signer only to its projective equivalence class \([M]_\mathcal {R}= \{\lambda M : \lambda \in \mathbb {Z}_p^*\}\): anybody can transfer the signature to a new representative, scaling the message by an arbitrary factor and obtaining a new signature for the scaled message. SPS-EQ-\(\mathcal {R}\)s have many applications such as anonymous credentials [6] and have appealing properties, such as being compatible with Groth-Sahai zero-knowledge proofs [15]. In this work, we show how to construct verifiably encrypted signatures and public-key encryption from an SPS-EQ-\(\mathcal {R}\).
Verifiably Encrypted Signatures. Bob wants to buy a theater ticket with an electronic check. That is, he wants to exchange one document, signed by himself, for another document, signed by the theater. If he sends the check before receiving the ticket, he worries that the theater will cash his check without issuing the ticket. On the other hand, the theater is not willing to issue the ticket without receiving a check.
A verifiably encrypted signature scheme (VES), introduced by Boneh et al. [3], can be used to resolve this impasse. A VES has two forms of signatures: plain and encrypted. Both forms of signature can be verified, and if the signer refuses to reveal the plain signature at the end of negotiations, the other party can appeal to a trusted third party (called the arbiter), who can recreate a plain signature given the corresponding encrypted signature.
Thus, in our example, the theater can provisionally send Bob a ticket with an encrypted signature, and once they receive Bob’s signed check they can reveal the corresponding plain signature, and thus validate the provisional ticket. If they fail to do so, Bob can take the encrypted signature to the arbiter. The arbiter’s investigation will reveal that Bob has indeed upheld his side of the deal, and so recreate the corresponding plain signature, giving Bob the ticket he has paid for. This protocol has the advantage that the arbiter need not participate unless there is a dispute.
VES from SPS-EQ-\(\mathcal {R}\). We introduce a simple new property for SPS-EQ-\(\mathcal {R}\) schemes, called perfect composition, which is satisfied by an existing construction in the generic group model, and show how to construct VESes from such schemes. In particular, this is the first VES construction from any kind of structure-preserving signature scheme, underlining the versatility of SPS-EQ-\(\mathcal {R}\)s. In our construction, each message is associated to a projective equivalence class. To create a plain signature, the signer signs one representative; to create an encrypted signature, she signs another. The scaling factor between these two representatives depends on the arbiter’s key, allowing the arbiter to recover the plain signature from the encrypted one using the SPS-EQ-\(\mathcal {R}\)’s change representative algorithm.
Public-Key Encryption from SPS-EQ-\(\mathcal {R}\). If the SPS-EQ-\(\mathcal {R}\) allows perfect composition, then our VES construction satisfies resolution duplication, a property introduced very recently by Calderon et al. [5], which requires that a signature extracted by the arbiter is identical to that which would have been created by the signer. Not only does this prevent discrimination between arbiter-issued and signer-issued signatures, but VESes satisfying this property imply public-key encryption. This is particularly interesting because it is not possible to construct PKE from ordinary signatures (or equivalently, from one-way functions) in a black-box way. Looking at this from the other side, it means that such an SPS-EQ-\(\mathcal {R}\) cannot be constructed (black-box) from one-way functions.
1.1 Our Contribution
Our main contribution is twofold:
Verifiably Encrypted Signatures. We propose the first black-box construction of verifiably encrypted signature scheme from any structure-preserving signature scheme on equivalence classes satisfying a simple property. This construction does not combine an encryption scheme with an SPS-EQ-\(\mathcal {R}\). Furthermore, all our security proofs hold in the standard model, under the Diffie-Hellman Inversion assumption.
We also revisit the security definitions of VES. The original definition of VES [3] requires that the underlying (ordinary) signature scheme be correct and secure in addition to other security properties. The latter properties have been extended in subsequent literature [18, 27] but the requirements on the underlying scheme are sometimes neglected. We show that with this omission, resolution independence is absolutely essential not only to the unforgeability, but even to the correctness, of the underlying signature scheme. From the alternative viewpoint, we show that security including resolution independence is sufficient for the correctness and security of the underlying signature scheme.
Public-Key Encryption. We propose the first black-box construction of a CPA-secure public-key encryption scheme from any structure-preserving signature scheme on equivalence classes allowing perfect composition. The construction follows the idea of Calderon et. al [5]; it is black-box and does not involve known non-black-box techniques such as zero-knowledge. Given the well-known impossibility results, this shows that SPS-EQ-\(\mathcal {R}\)s allowing perfect composition cannot be constructed from one-way functions in a black-box way.
1.2 Related Work
Verifiably encrypted signatures and a first instantiation in the random oracle model were proposed by Boneh et al. [3]. After their invention, several instantiations were suggested in the RO model [26, 29] and in the standard model [8, 22, 27]. The security model is treated in [3, 5, 18, 27].
Impagliazzo and Rudich [20] show in their seminal work that cryptographic primitives can be classified as lying in one of two “worlds”. The “Minicrypt” world contains those primitives that are equivalent to the weakest known assumption, the existence of one-way functions (OWFs), such as digital signatures [14, 17, 19, 21, 24]. The second world, “Cryptomania”, includes primitives that require stronger assumptions such as public-key encryption (PKE), key-agreement (KA), oblivious transfer (OT) [4, 11, 12, 25, 28] and now SPS-EQ-\(\mathcal {R}\).
1.3 Outline
In Sect. 2 we state the preliminaries. In Sect. 3 we discuss the relationship between resolution independence and the correctness and unforgeability of the underlying signature scheme of a VES. Then, in Sect. 4, we show how to generically build a VES from an SPS-EQ-\(\mathcal {R}\) scheme. In Sect. 5, we then discuss the implication of PKE by certain SPS-EQ-\(\mathcal {R}\). Finally, we conclude this paper in Sect. 6.
2 Preliminaries
A function \(\epsilon : \mathbb {N}\rightarrow \mathbb {R}^+\) is called negligible if for all \(c > 0\) there is a \(k_0\) such that \(\epsilon (k) < 1/k^c\) for all \(k > k_0\). In the remainder of this paper, we use \(\epsilon \) to denote such a negligible function. By \(a \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}A\), we denote that a is chosen uniformly at random from the set A. We use the notation \(A(a_1,\dots ,a_n; r)\) if we make the randomness r used by a probabilistic algorithm \(A(a_1,\dots ,a_n)\) explicit.
Definition 1
Bilinearity:\(e(aP, b\hat{P}) = e(P,\hat{P})^{ab} ~~ \forall \, a,b\in \mathbb {Z}_p .\)
Non-degeneracy:\(e(P,\hat{P}) \ne 1_{\mathbb {G}_T}\), i.e., \(e(P,\hat{P})\) generates \(\mathbb {G}_T .\)
If \(\mathbb {G}_1 = \mathbb {G}_2\), then e is symmetric (Type-1) and asymmetric (Type-2 or 3) otherwise. For Type-2 pairings there is an efficiently computable isomorphism \(\varPsi :\mathbb {G}_2 \rightarrow \mathbb {G}_1\); for Type-3 pairings no such isomorphism is known. Type-3 pairings are currently the optimal choice in terms of efficiency and security trade-off [7].
Definition 2
(Bilinear Group Generator). A polynomial-time algorithm \(\mathsf{BGGen}\) is a bilinear-group generator if it takes as input a security parameter \(1^{{\kappa }}\) and outputs \(\mathsf{BG}=(p,\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T,e,P,\hat{P})\) where the common group order p of the groups \(\mathbb {G}_1, \mathbb {G}_2\) and \(\mathbb {G}_T\) is a prime of bit-length \({\kappa }\), e is a pairing, and P and \(\hat{P}\) are generators of \(\mathbb {G}_1\) and \(\mathbb {G}_2\), respectively.
In this work we assume \(\mathsf{BGGen}\) to be deterministic.1
Definition 3
(Diffie-Hellman Inversion Assumption (DHI) [23]). Let \(\mathbb {G}\) be a group of prime order p with \(\log _2 p = \kappa \) and let \(a \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}\mathbb {Z}_p^*\). Then, for every PPT adversary \({\mathcal {A}}\) there is a negligible function \(\epsilon (\cdot )\) such that \( \Pr \left[ \frac{1}{a}P \leftarrow {\mathcal {A}}(P,aP)\right] \le \epsilon (\kappa )\).
2.1 Digital Signatures
Definition 4
\(\mathsf {KeyGen}(1^{\kappa })\): A probabilistic algorithm that takes input a security parameter \(\kappa \in \mathbb {N}\) and outputs a key pair \((\mathsf{sk}, \mathsf{pk})\) for message space \(\mathcal {M}\).
\(\mathsf {Sign}(m,\mathsf{sk})\): A probabilistic algorithm that takes input a message \(m\in \mathcal {M}\), a secret key \(\mathsf{sk}\) and outputs a signature \(\sigma \).
\(\mathsf {Verify}(m,\sigma ,\mathsf{pk})\): A deterministic algorithm that takes input a message \(m\in \mathcal {M}\), a signature \(\sigma \), a public key \(\mathsf{pk}\) and outputs \(1\) if \(\sigma \) is a valid signature for M under \(\mathsf{pk}\) and \(0\) otherwise.
A digital signature scheme is secure if it is correct and existentially unforgeable under adaptively chosen-message attacks. We define the properties below:
Definition 5
Definition 6
2.2 Structure-Preserving Signatures on Equivalence Classes
In a structure-preserving signature scheme [1], public keys, messages and signatures consist only of group elements of a bilinear group. The verification algorithm verifies a signature solely through group membership tests and by evaluating pairing-product equations.
An SPS-EQ-\(\mathcal {R}\) scheme is a structure-preserving signature scheme that is defined either on the message space \((\mathbb {G}_1^*)^\ell \) or \((\mathbb {G}_2^*)^\ell \), where \(\ell > 1\) and \(|\mathbb {G}_1|=|\mathbb {G}_2|=p\) is prime. Since \(\mathbb {Z}_p^\ell \) is a vector space, it is possible to define—in analogy to the projective space—a projective equivalence relation \(\sim _\mathcal {R}\) that partitions \(\mathbb {Z}_p^\ell \) into projective equivalence classes. This equivalence relation then further propagates onto \((\mathbb {G}_i^*)^\ell \) for \(i \in \{1,2\}\).
Now, an SPS-EQ-\(\mathcal {R}\) scheme signs such equivalence classes by signing arbitrary representatives of such classes. When given a message-signature pair, anyone can derive a valid message-signature pair for every other representative of this class. This is done by multiplying each message vector component by the same scalar and by consistently updating the corresponding signature. Clearly, this requires unforgeability to be defined with respect to equivalence classes. This means that after querying signatures for messages \(M_i\), no adversary should be able to output a forgery for a message \(M^*\) belonging to a class different from the classes \([M_i]_\mathcal {R}\).
We restate the syntax and the security properties of structure-preserving signatures on equivalence classes from [9, 10, 16]:
Definition 7
\(\mathsf{BGGen}_\mathcal {R}(1^{\kappa })\): A deterministic bilinear-group generation algorithm, which on input a security parameter \({\kappa }\) outputs a bilinear group \(\mathsf{BG}\).
\(\mathsf{KeyGen_\mathcal {R}}(\mathsf{BG},\ell )\): A probabilistic algorithm, which on input a bilinear group \(\mathsf{BG}\) and a vector length \(\ell >1\) outputs a key pair \((\mathsf{sk},\mathsf{pk})\).
\(\mathsf{Sign_\mathcal {R}}(M,\mathsf{sk})\): A probabilistic algorithm, which on input a representative \(M \in (\mathbb {G}_i^*)^\ell \) of an equivalence class \([M]_\mathcal {R}\) and a secret key \(\mathsf{sk}\) outputs a signature \(\sigma \) for the representative M of equivalence class \([M]_\mathcal {R}\).
\(\mathsf{ChgRep_\mathcal {R}}(M, \sigma , \lambda , \mathsf{pk})\): A probabilistic algorithm, which on input a representative \(M \in (\mathbb {G}_i^*)^\ell \) of an equivalence class \([M]_\mathcal {R}\), a signature \(\sigma \) for M, a scalar \(\lambda \) and a public key \(\mathsf{pk}\) returns an updated message-signature pair \((M', \sigma ')\), where \(M'=\lambda M\) is the new representative and \(\sigma '\) its updated signature.
\(\mathsf{Verify_\mathcal {R}}(M,\sigma ,\mathsf{pk})\): A deterministic algorithm, which given a representative \(M \in (\mathbb {G}_i^*)^\ell \), a signature \(\sigma \) and a public key \(\mathsf{pk}\) outputs \(1\) if \(\sigma \) is valid for M under \(\mathsf{pk}\) and \(0\) otherwise.
\(\mathsf{VKey_\mathcal {R}}(\mathsf{sk},\mathsf{pk})\): A deterministic algorithm, which given a secret key \(\mathsf{sk}\) and a public key \(\mathsf{pk}\) checks both keys for consistency and returns \(1\) on success and \(0\) otherwise.
Definition 8
Definition 9
We now introduce the following new property:
Definition 10
Intuitively, this requires that \(\mathsf{ChgRep}_\mathcal {R}\) executed with random coins fixed to 1 updates only the parts of a signature that are affected by updating the representative from M to \(\lambda M\), not changing the randomness of \(\mathsf{Sign}_\mathcal {R}\).
In [10], a standard model SPS-EQ-\(\mathcal {R}\) construction is presented. Unfortunately, it does not satisfy the above definition, but the scheme in [9], which is secure in the generic group model, does.
2.3 Verifiably Encrypted Signatures
Below, we give the abstract model of verifiably encrypted signatures, adapted from [3].
Definition 11
\({\mathsf {AKeyGen}}(1^{\kappa })\): Given a security parameter \({\kappa }\), this probabilistic algorithm outputs a key pair \((\mathsf{ask},\mathsf{apk})\), where \(\mathsf{ask}\) is the private key and \(\mathsf{apk}\) the corresponding public key of the arbiter.
\({\mathsf {KeyGen}}(1^{\kappa })\): Given a security parameter \({\kappa }\), this probabilistic algorithm outputs a private signing key \(\mathsf{sk}\) and a public verification key \(\mathsf{pk}\) for message space \(\mathcal {M}\).
\(\mathsf {Sign}(m, \mathsf{sk})\): Given a message \(m \in \mathcal {M}\) and a signing key \(\mathsf{sk}\), this probabilistic algorithm outputs a signature \(\sigma \) under \(\mathsf{sk}\) on m.
\(\mathsf {Verify}(m, \sigma , \mathsf{pk})\): Given a message \(m \in \mathcal {M}\) and a public key \(\mathsf{pk}\), this deterministic algorithm outputs \(1\) iff \(\sigma \) is a valid signature on m under \(\mathsf{pk}\) and \(0\) otherwise.
\({\mathsf {VESign}}(m, \mathsf{sk}, \mathsf{apk})\): Given a message \(m \in \mathcal {M}\), a signing key \(\mathsf{sk}\) and an arbiter public key \(\mathsf{apk}\), this probabilistic algorithm outputs an encrypted signature \(\omega \) under \(\mathsf{sk}\) on message m.
\({\mathsf {VEVerify}}(m, \omega , \mathsf{pk}, \mathsf{apk})\): Given a message \(m \in \mathcal {M}\), an encrypted signature \(\omega \), a public key \(\mathsf{pk}\) and an arbiter public key \(\mathsf{apk}\), this deterministic algorithm outputs \(1\) if \(\omega \) is a valid encrypted signature on m under \(\mathsf{pk}\) and \(0\) otherwise.
\({\mathsf {Resolve}}(m, \omega , \mathsf{ask}, \mathsf{pk})\): Given a message \(m \in \mathcal {M}\), an encrypted signature \(\omega \), an arbiter secret key \(\mathsf{ask}\) and a public key \(\mathsf{pk}\), this (probabilistic) algorithm outputs a valid signature \(\sigma \) on m under \(\mathsf{pk}\).
We call a VES secure if it is complete, unforgeable, opaque, extractable, abuse free and resolution independent. We define these properties below.
Completeness says that any honestly computed VES always verifies and that moreover the arbiter can always extract a valid signature.
Definition 12
Unforgeability says that it should be infeasible to produce a valid encrypted signature for an unknown secret key.
Definition 13
Opacity basically requires that only the arbiter should be able to pull out the underlying signature.
Definition 14
In addition to the above property, we have to guarantee that it is indeed possible for the arbiter to extract the underlying signature, which is covered by the following property.
Definition 15
Abuse freeness guarantees that even if an adversary is colluding with the arbiter, it is unable to forge a valid encrypted signature.
Definition 16
Extractability and abuse freeness were introduced by Rückert and Schröder in [27].
Additionally, Calderon et al. [5] have identified another property that is called resolution independence. This property is crucial for a VES to be secure, as we will discuss in Sect. 3.
Definition 17
(Resolution Independence). A VES \(\mathsf{VES}\) is resolution independent if for all \(\kappa > 0\), all \((\mathsf{ask}, \mathsf{apk}) \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}{\mathsf {AKeyGen}}(1^{\kappa })\), \((\mathsf{sk}, \mathsf{pk}) \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}{\mathsf {KeyGen}}(1^{\kappa })\), and all messages m, the outputs of \(\mathsf {Sign}(m,\mathsf{sk})\) and \({\mathsf {Resolve}}(m, {\mathsf {VESign}}(m, \mathsf{sk}, \mathsf{apk}),\mathsf{ask}, \mathsf{pk})\) are distributed identically.
In [5], the authors showed that VES constructions imply public key encryption if they additionally satisfy a property called resolution duplication. Loosely speaking, a VES is resolution duplicate if the signatures returned by the signer and the arbiter are identical.
Definition 18
Deterministic Resolution: The algorithm \({\mathsf {Resolve}}\) is deterministic.
- Extraction: There exists an additional PPT algorithm \(\mathsf {Extract}(\cdot ,\cdot ,\cdot )\), such that for all \(\kappa > 0\), all \((\mathsf{ask}, \mathsf{apk}) \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}{\mathsf {AKeyGen}}(1^{\kappa })\), \((\mathsf{sk},\mathsf{pk})\mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}{\mathsf {KeyGen}}(1^{\kappa }), m \in \mathcal {M}\), and random tapes \(r \in \{0,1\}^*\), it is the case that$$\mathsf {Extract}(m, \mathsf{sk},r)={\mathsf {Resolve}}(m,{\mathsf {VESign}}(m,\mathsf{sk},\mathsf{apk}; r),\mathsf{ask},\mathsf{pk}).$$
Up to now numerous standard-model VES constructions have been proposed, but not all constructions so far are resolution-duplicate; in particular not the ones with a randomized \(\mathsf{Resolve}\) algorithm [5].
3 The Importance of Resolution Independence
In Boneh et al.’s original definition of a VES [3], the underlying signature scheme is required to be secure, in addition to the security properties of the encrypted signatures: completeness, unforgeability and opacity. Rückert and Schröder [27] added the properties of extractability and abuse freeness, and Calderon et al. [5] added the properties of resolution independence, but both omit (or are at least unclear about) the requirement that the underlying signature scheme be secure. Indeed, the latter paper says that they “additionally provide the adversary with access to the \(\mathsf {Sign}\) oracle, as otherwise the underlying signature scheme could be completely broken and the VES would still be considered unforgeable.” In fact, it can be completely broken anyway.
We will show that, with this omission, resolution independence is absolutely essential to not only the unforgeability, but even the correctness, of the underlying scheme. Resolution independence supplies the necessary glue to connect the security properties of the encrypted scheme to the underlying scheme. Contrapositively, we show that security including resolution independence is sufficient for the correctness and security of the underlying signature scheme, so that does not need to be proven separately. To be clear, we formally define what is meant by the underlying signature scheme.
Definition 19
Let \(\mathsf {VES}\) be a VES. Then we call \(\mathsf{Sig} = (\mathsf {SKeyGen}, \mathsf {Sign}, \mathsf {Verify})\) the underlying signature scheme of \(\mathsf {VES}\), where \(\mathsf {SKeyGen}(1^{\kappa })\) outputs \((\mathsf{sk}, \mathsf{pk}) \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}{\mathsf {KeyGen}}(1^{\kappa })\).
3.1 Counterexample
We now show that completeness, unforgeability, opacity, extractability and abuse freeness together do not imply the correctness or security of the underlying scheme.
Let \(\mathsf {VES}= (\mathsf {\mathsf {AKeyGen}}, {\mathsf {KeyGen}}, \mathsf {Sign}, \mathsf {Verify}, {\mathsf {VESign}},{\mathsf {VEVerify}},{\mathsf {Resolve}})\) be a VES with messages of length n, and let \(\mathsf {VES}' = (\mathsf {\mathsf {AKeyGen}}, {\mathsf {KeyGen}}, \mathsf {Sign}',\mathsf {Verify}, {\mathsf {VESign}},{\mathsf {VEVerify}},{\mathsf {Resolve}})\) where \(\mathsf {Sign}'(m,\mathsf{sk})\) computes and outputs \(\mathsf {Sign}(0^n, \mathsf{sk})\).
Theorem 1
If \(\mathsf {VES}\) is complete, unforgeable, opaque, extractable and abuse free, then so is \(\mathsf {VES}'\).
Proof
The adversary in the unforgeability game must output a valid encrypted signature, but the set of valid encrypted signatures in \(\mathsf {VES}\) and \(\mathsf {VES}'\) are the same, and we have only weakened the oracles (by making \(\mathsf {Sign}\) provide signatures only on \(0^n\)), so unforgeability is preserved. The other properties do not mention the \(\mathsf {Sign}\) algorithm at all, so they are unaffected. \(\quad \square \)
This scheme is intuitively both incorrect (as the signatures produced by \(\mathsf {Sign}'\) cannot be verified) and insecure (as it gives away a forgery as soon as it is called on a message other than \(0^n\). Nevertheless, \(\mathsf {VES}'\) is secure as defined in [27], since their definition does not include the security of the underlying signature scheme. It is also much more catastrophically insecure than the separating example in [5, Sect. 3], which motivated the definition of resolution independence.
Theorem 2
The underlying signature scheme \(\mathsf{Sig}\) of \(\mathsf {VES}'\) is neither correct nor secure.
3.2 Filling the Gap
Lemma 1
If \(\mathsf {VES}\) is a complete and resolution independent VES, then its underlying signature scheme \(\mathsf{Sig}\) is correct.
Proof
\(\quad \square \)
Lemma 2
If \(\mathsf {VES}\) is an opaque and resolution independent VES, then its underlying signature scheme \(\mathsf{Sig}\) is EUF-CMA-secure.
Proof
Let \(\mathsf {VES}\) be a resolution independent VES, and let \(\mathsf {Sig}\) be the underlying signature scheme. We assume that there is an efficient adversary \({\mathcal {A}}\) breaking the EUF-CMA security of \(\mathsf {Sig}\) with non-negligible probability, and construct an adversary \(\mathcal {B}\) that uses \({\mathcal {A}}\) to break the opacity of \(\mathsf {VES}\).
\(\mathcal {B}\) takes as input an arbiter’s public key \(\mathsf{apk}\) and a signer’s public key \(\mathsf{pk}\) (with unknown corresponding private keys \(\mathsf{ask}\) and \(\mathsf{sk}\)), and passes \(\mathsf{pk}\) as input to \({\mathcal {A}}\). Whenever \({\mathcal {A}}\) tries to query the \(\mathsf {Sign}\) oracle on message m, \(\mathcal {B}\) forwards m to its \({\mathsf {VESign}}\) oracle, obtaining \(\omega = {\mathsf {VESign}}(m, \mathsf{sk}, \mathsf{apk})\); \(\mathcal {B}\) then queries \((m, \omega )\) to its \({\mathsf {Resolve}}\) oracle, obtaining \(\sigma = {\mathsf {Resolve}}(m, {\mathsf {VESign}}(m, \mathsf{sk}, \mathsf{apk}), \mathsf{ask}, \mathsf{pk})\), which it returns to \({\mathcal {A}}\). When \({\mathcal {A}}\) outputs \((m^*, \sigma ^*)\), \(\mathcal {B}\) outputs the same.
By resolution independence, \(\mathsf {Sign}(m, \mathsf{sk})\) and \({\mathsf {Resolve}}(m, {\mathsf {VESign}}(m, \mathsf{sk}, \mathsf{apk}),\mathsf{ask}, \mathsf{pk})\) are identically distributed, so we perfectly simulate \({\mathcal {A}}\)’s \(\mathsf {Sign}\) oracle.
If \({\mathcal {A}}\) never queried \(m^*\) to \(\mathsf {Sign}\), then \(\mathcal {B}\) never queried \(m^*\) to \({\mathsf {Resolve}}\), and so \(\mathcal {B}\) has the same non-negligible success probability as \({\mathcal {A}}\). \(\quad \square \)
Theorem 3
If a VES is complete, opaque and resolution independent, then its underlying signature scheme \(\mathsf{Sig}\) is correct and secure.
4 Verifiably Encrypted Signatures from SPS-EQ-\(\mathcal {R}\)
Note 1
Observe that, independently of the instantiation of Scheme 1 with a concrete SPS-EQ-\(\mathcal {R}\), the efficiency of the \(\mathsf {Verify}\) resp. \({\mathsf {VEVerify}}\) can be improved by precomputing parts of the pairing product equations that solely depend on P and \(\mathsf{pk}\) resp. A and \(\mathsf{pk}\), and including the resulting \(\mathbb {G}_T\) elements into (the updated) user public key \(\mathsf{pk}\).
In the following, we are going to analyze the security of Scheme 1 and prove completeness, unforgeability, opacity and abuse freeness as well as resolution duplication.
Theorem 4
The VES in Scheme 1 is complete.
Proof
The completeness proof of Scheme 1 is straight-forward and therefore omitted here. \(\quad \square \)
Theorem 5
The VES in Scheme 1 is unforgeable given that the underlying SPS-EQ-\(\mathcal {R}\) scheme is unforgeable.
Proof
We assume that there is an efficient adversary \({\mathcal {A}}\) winning the unforgeability game with non-negligible probability; then we are able to construct an adversary \(\mathcal {B}\) that uses \({\mathcal {A}}\) to break the EUF-CMA security of the underlying SPS-EQ-\(\mathcal {R}\) scheme with non-negligible probability.
\(\mathsf{Sign}(\cdot , \mathsf{sk})\): If \({\mathcal {A}}\) submits a query for \(m \in \mathbb {Z}_p^*\), \(\mathcal {B}\) queries \(\mathcal {C}\)’s signing oracle for the message (msP, sP, P) for \(s \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}\mathbb {Z}_p^*\), gets in return a corresponding signature \(\sigma '\), sets \(L[m] \leftarrow L[m] \cup \{(m sA, sA, A)\}\) and gives \(\sigma \leftarrow (\sigma ', sP)\) to \({\mathcal {A}}\).
\(\mathsf{VESign}(\cdot , \mathsf{sk}, \mathsf{apk})\): If \({\mathcal {A}}\) submits a query for \(m \in \mathbb {Z}_p^*\), \(\mathcal {B}\) queries \(\mathcal {C}\)’s signing oracle for the message (msA, sA, A) for \(s \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}\mathbb {Z}_p^*\), gets in return a corresponding signature \(\omega '\), sets \(L[m] \leftarrow L[m] \cup \{(m sA, sA, A)\}\) and gives \(\omega \leftarrow (\omega ', sA)\) as encrypted signature to \({\mathcal {A}}\).
If at some point \({\mathcal {A}}\) outputs a valid encrypted message-signature pair \((m^*, \omega ^* = ( \omega '^*, W^*))\), such that it has not previously queried \(m^*\) to any of the oracles, then \(\mathcal {B}\) will output \(((m^* W^*, W^*, A), \omega '^*)\) to \(\mathcal {C}\).
Note that the distribution of all values returned to \({\mathcal {A}}\) during the simulation is identical to the distribution of these values during a real game.
By construction, \(((m^* W^*, W^*, A), \omega '^*)\) constitutes a valid SPS-EQ-\(\mathcal {R}\) message-signature pair. It remains to show that for \(M^* = (m^* W^*, W^*, A)\), the class \([M^*]_\mathcal {R}\) is different from all classes represented by elements in L, if \(m^*\) is different from all messages queried to the oracles. \(\mathsf{VEVerify}\) demands that the third vector component of \(M^*\) be A, which uniquely determines the representative for each class and allows for comparison. Now, if there is some \(M_i = (m_i W_i, W_i, A) \in L\) queried to the \(\mathsf{VESign}\) or the \(\mathsf{Sign}\) oracle coinciding with \(M^*\) in the second component, then both vectors still differ in the first component for \(m^* \ne m_i\). Likewise, if they coincide in the first component for \(m^* \ne m_i\), then they cannot have equal second components. Hence, \(M^* \ne M_i\) for any \(M_i\) in L. \(\square \)
Theorem 6
The VES in Scheme 1 is opaque given that the DHI assumption holds in \(\mathbb {G}_1\) and that the underlying SPS-EQ-\(\mathcal {R}\) is unforgeable.
Proof
We assume that there is an efficient adversary \({\mathcal {A}}\) winning the opacity game with non-negligible probability. Then we are able to construct an adversary \(\mathcal {B}\) that uses \({\mathcal {A}}\) either to break with non-negligible probability the EUF-CMA security of the underlying SPS-EQ-\(\mathcal {R}\) scheme (Type-1 adversary) if \({\mathcal {A}}\) has neither queried the \(\mathsf{VESign}\) nor the \(\mathsf{Resolve}\) oracle for \(m^*\); or the DHI assumption (Type-2 adversary) if \({\mathcal {A}}\) has only queried the \(\mathsf{VESign}\) but not the \(\mathsf{Resolve}\) oracle for \(m^*\).
In the following, \(\mathcal {B}\) guesses \({\mathcal {A}}\)’s strategy, i.e., the type of forgery \({\mathcal {A}}\) will conduct. We are now going to describe the setup, the initialization of the environment, the reduction and the abort conditions for each type.
\(\mathsf{VESign}(\cdot , \mathsf{sk}, \mathsf{apk})\): If \({\mathcal {A}}\) submits a query for \(m \in \mathbb {Z}_p^*\), \(\mathcal {B}\) queries \(\mathcal {C}\)’s signing oracle for the message (msA, sA, A) for \(s \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}\mathbb {Z}_p^*\), then \(\mathcal {B}\) gets in return a signature \(\omega '\) and outputs \((\omega ', s A)\).
If at some point \({\mathcal {A}}\) outputs a valid message-signature pair \((m^*, \sigma ^*)\) with \(\sigma ^* = (\sigma '^*, S^*)\), and neither has queried to the \(\mathsf{VESign}\) nor to the \(\mathsf{Resolve}\) oracle for \(m^*\), then \(\mathcal {B}\) will output \(((m^* S^*, S^*, P), \sigma '^*)\) to \(\mathcal {C}\). In case that \({\mathcal {A}}\) has queried the \(\mathsf{VESign}\) oracle for \(m^*\), \(\mathcal {B}\) will abort.
Note that the distribution of all values returned to \({\mathcal {A}}\) during the simulation is identical to the distribution of these values during a real game, which makes the simulation perfect.
By construction, \(((m^* S^*, S^*, P), \sigma '^*)\) constitutes a valid SPS-EQ-\(\mathcal {R}\) message-signature pair. It remains to show that for \(M^* = (m^* S^*, S^*, P)\), the class \([M^*]_\mathcal {R}\) is different from all classes queried to \(\mathcal {C}\), if \(m^*\) is different from all messages queried to the \(\mathsf{VESign}\) oracle. \(\mathsf{Verify}\) demands that the third vector component of \(M^*\) be P, which uniquely determines the representative for each class and allows for comparison. Now, if there is some \(M_i = (m_i S_i, S_i, P)\) coinciding with \(M^*\) in the second component, then both vectors still differ in the first component for \(m^* \ne m_i\). Likewise, if they coincide in the first component for \(m^* \ne m_i\), then they cannot have equal second components. Hence, \(M^* \ne M_i\) for any \(M_i\) queried to \(\mathcal {C}\).
- \(\mathsf{VESign}(\cdot , \mathsf{sk}, \mathsf{apk})\): If \({\mathcal {A}}\) submits a query for \(m \in \mathbb {Z}_p^*\), \(\mathcal {B}\) picks \(s \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}\mathbb {Z}_p^*\) and random coins \(r_2\), setsruns \(\omega ' \leftarrow \mathsf{Sign_\mathcal {R}}((m W, W, A), \mathsf{sk}; r_2)\). Then, it sets \(\omega \leftarrow (\omega ', W)\), stores \(L[m] \leftarrow (s, r_2, \omega )\) and returns \(\omega \).
\(-\)\(W \leftarrow sA\) with probability \(\mathbf p\), or
\(-\)\(W \leftarrow s(P + A)\) with probability \(1-\mathbf p\), and
\(\mathsf{Resolve}(\cdot , \cdot , \mathsf{ask}, \mathsf{pk})\): If \({\mathcal {A}}\) submits a query for \(m \in \mathbb {Z}_p^*\) and \(\omega \), then \(\mathcal {B}\) checks whether Open image in new window and returns \(\bot \) if this is not the case. Otherwise, it retrieves the entry \((s, r_2, \omega = ( \omega ', W)) \leftarrow L[m]\). If Open image in new window, then \(\mathcal {B}\) aborts. Otherwise, \(\mathcal {B}\) computes \(\sigma ' \leftarrow \mathsf{Sign_\mathcal {R}}((msP, sP, P), \mathsf{sk}; r_2)\) and returns \(\sigma \leftarrow (\sigma ', sP)\).
If at some point \({\mathcal {A}}\) outputs a valid message-signature pair \((m^*, \sigma ^* = (\sigma '^*, S^*))\) and has queried the \(\mathsf{VESign}\) oracle for \(m^*\), but not the \(\mathsf{Resolve}\) oracle, then \(\mathcal {B}\) retrieves \((s^*, r_2^*, \omega ^*) \leftarrow L[m^*]\). If \(S^* = s^*P\), then \(\mathcal {B}\) aborts. Otherwise, we have \(S^* = s^* (\frac{1}{a} P + P)\) and \(\mathcal {B}\) outputs \(\frac{1}{a} P \leftarrow \frac{1}{s^*} S^* - P\) as a solution to the DHI problem.
Note that the distribution of all values returned to \({\mathcal {A}}\) during the simulation is identical to the distribution of these values during a real game, which makes the simulation perfect.
Let \(q_R\) be the number of resolve queries. Then, with probability \(\mathbf{p}^{q_R}\), \(\mathcal {B}\) does not abort during the simulation. Given that the simulation works out, \({\mathcal {A}}\) outputs a “useful” forgery with probability \(1-\mathbf p\). In total, \(\mathcal {B}\) is able to return a solution to the DHI problem with probability \(\mathbf{p}^{q_R}(1-\mathbf{p})\). The function \(f(\mathbf{p}) = \mathbf{p}^{q_R}(1-\mathbf{p})\) reaches its maximum for \(\frac{q_R}{q_R+1}\) and after few calculations we obtain \(f(\mathbf{p}) = O(\frac{1}{q_R})\). Therefore, if \({\mathcal {A}}\) is able to break the opacity of the scheme with non-negligible probability \(\epsilon (\kappa )\), then \(\mathcal {B}\) is able to break the DHI assumption with non-negligible probability \(O(\frac{\epsilon (\kappa )}{q_R})\). \(\quad \square \)
Theorem 7
The VES in Scheme 1 is unconditionally extractable.
Theorem 8
The VES in Scheme 1 is abuse free given that the underlying SPS-EQ-\(\mathcal {R}\) scheme is unforgeable.
The following theorem states that Scheme 1 is resolution duplication. In particular, it is resolution independent, the importance of which was established in Sect. 3. It will allow also us to derive a PKE scheme (cf. Sect. 5).
Theorem 9
The VES in Scheme 1 is resolution duplicate given that the underlying SPS-EQ-\(\mathcal {R}\) scheme allows perfect composition.
5 Public-Key Encryption from SPS-EQ-\(\mathcal {R}\)
In this section, we show how to convert any SPS-EQ-\(\mathcal {R}\) satisfying perfect composition (Definition 10) into a public-key encryption scheme. This connection is somewhat surprising, as it is well known that regular signature schemes do not imply public-key encryption (in a black-box way). However, there is no contradiction as SPS-EQ-\(\mathcal {R}\) have more structure than a regular signature scheme.
The basic idea is to instantiate the transformation of Calderon et al. [5]. This transformation turns any secure, resolution duplicate VES scheme into a public-key encryption scheme, in a black-box way. We have already shown how to construct a secure VES scheme, and that it is resolution duplicate, in Sect. 4. The basic idea of the transformation is an application of the Goldreich-Levin trick [14] to the setting of VES. That is, we view \(\langle \sigma ,r \rangle \) as the hard-core predicate for \({\mathsf {VESign}}\), i.e., given \(\omega \) and r it should be hard to predict the value of \(\langle \sigma ,r \rangle \). This intuition is formally shown in the following lemma.
Lemma 3
Let \(\mathsf{VES}\) be a VES and let \(b(x,r):=\langle x ,r \rangle \mod 2\) for any x and r such that \(|x| = |r|\). Then, if the VES is opaque for all messages \(m \in \mathcal {M}\), all \((\mathsf{ask},\mathsf{apk})\mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}{\mathsf {AKeyGen}}(1^{\kappa })\) and \((\mathsf{sk},\mathsf{pk})\mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}{\mathsf {KeyGen}}(1^{\kappa })\), it is hard to compute \(b(\sigma ,r)\) given \(m, \mathsf{apk}, \mathsf{pk}, \omega \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}{\mathsf {VESign}}(m,\mathsf{sk},\mathsf{apk})\), and \(r \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}\{0,1\}^{| \sigma |}\), where \(\sigma :={\mathsf {Resolve}}(\omega ,\mathsf{ask},\mathsf{pk})\).
\({\mathsf {EKeyGen}(1^{\kappa })}\mathbf{:}\) Output \((\mathsf{apk},\mathsf{ask})\mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}{\mathsf {AKeyGen}}(1^{\kappa })\).
\(\mathsf {Enc}(m,\mathsf{apk}):\) Generate signing keys \((\mathsf{sk},\mathsf{pk})\mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}{\mathsf {KeyGen}}(1^{\kappa })\) and pick a random tape r and \(r_\sigma \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}\{0,1\}^{|\sigma |}\). Now, compute \(\omega :={\mathsf {VESign}}(0,\mathsf{sk},\mathsf{apk};r)\), \(\sigma \mathop {\leftarrow }\limits ^{\scriptscriptstyle \$}\mathsf {Extract}(m,\mathsf{sk},r )\), and set \(c_0 := m \oplus \langle \sigma , r_\sigma \rangle \). Output \(c=(\mathsf{pk},\omega ,r_{\sigma },c_0)\).
\(\mathsf {Dec}(c,\mathsf{ask}):\) Parse \(c=(\mathsf{pk},\omega ,r_{\sigma },c_0)\) and return \(\bot \) if \({\mathsf {VEVerify}}(0,\omega ,\mathsf{pk},\mathsf{apk})=0.\) Otherwise, compute \(\sigma := {\mathsf {Resolve}}(0,\mathsf{pk},\omega ,\mathsf{ask},\mathsf{pk})\) and output \(m:= c_0 \oplus \langle \sigma , r_{\sigma } \rangle \).
Regarding security, it was shown that the above construction is CPA secure [5]:
Theorem 10
If the verifiably encrypted signature is resolution duplicate (according to Definition 18) and opaque, then the above scheme is IND-CPA secure.
6 Conclusion
We have shown that the property of resolution independence is crucial, not only for constructing public-key encryption from verifiably encrypted signatures, but even for the correctness and security of the VES.
We gave for the first time a construction of resolution duplicate (and in particular resolution independent) VES from SPS-EQ-\(\mathcal {R}\). Our VES has short keys and signatures. This result demonstrates further applications of SPS, and SPS-EQ-\(\mathcal {R}\) in particular. Using our VES, we constructed public-key encryption. Since the construction is generic, it proves that SPS-EQ-\(\mathcal {R}\)s allowing perfect composition cannot be constructed from one-way functions.