Short Structure-Preserving Signatures

Abstract

We construct a new structure-preserving signature scheme in the efficient Type-III asymmetric bilinear group setting with signatures shorter than all existing schemes. Our signatures consist of 3 group elements from the first source group and therefore they are shorter than those of existing schemes as existing ones have at least one component in the second source group whose elements bit size is at least double that of their first group counterparts.

Besides enjoying short signatures, our scheme is fully re-randomizable which is a useful property for many applications. Our result also constitutes a proof that the impossibility of unilateral structure-preserving signatures in the Type-III setting result of Abe et al. (Crypto 2011) does not apply to constructions in which the message space is dual in both source groups. Besides checking the well-formedness of the message, verifying a signature in our scheme requires checking 2 Pairing Product Equations (PPE) and require the evaluation of only 5 pairings in total which matches the best existing scheme and outperforms many other existing ones. We give some examples of how using our scheme instead of existing ones improves the efficiency of some existing cryptographic protocols such as direct anonymous attestation and group signature related constructions.

The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007–2013) / ERC Grant Agreement no. 307937 and EPSRC grant EP/J009520/1.

1 Introduction

Structure-Preserving Signatures (SPS) [3] are digital signature schemes defined over bilinear groups ($e: \mathbb {G}\times \tilde{\mathbb {G}}\rightarrow \mathbb {T}$). Their messages, verification key and signatures are all group elements and signature verification involves evaluating Pairing Product Equations (PPE). They are a useful tool for the design of modular cryptographic protocols since they compose nicely with existing popular tools such as Groth-Sahai proofs [31] and ElGamal encryption scheme [20]. They are prominently used in combination with Groth-Sahai proofs and other tools to design cryptographic protocols that do not rely on heuristic assumptions such as random oracles [21]. They have numerous applications which include group signatures, e.g. [3, 34, 35], blind signatures, e.g. [3, 23], tightly secure encryption schemes, e.g. [2, 32], malleable signatures, e.g. [9], anonymous credentials, e.g. [23], network coding, e.g. [9], oblivious transfer, e.g. [28].

Related Work. The notion was formally defined by Abe et al. [3] but earlier schemes conforming to the definition were given by Groth [29] and Green and Hohenberger [28]. Because of its importance, the notion has received a significant amount of attention from the cryptographic community and many results relating to proving lower bounds for the design of such schemes as well as new schemes meeting those lower bounds have been published in the literature. Abe et al. [3] gave two constructions of structure-preserving signatures both relying on non-interactive intractability assumptions. Abe et al. [4] proved that any structure-preserving signature scheme in the most efficient Type-III bilinear group setting (cf. Sect. 2.1) must have at least 3 group elements and 2 pairing product verification equations. They also ruled out the existence of unilateral signatures and argued that the signature must contain elements from both source groups. They also gave constructions meeting the lower bound and proved them secure in the generic group model [40]. Abe et al. [5] proved the impossibility of the existence of a 3 group element structure-preserving signature in the Type-III setting that is based on non-interactive intractability assumptions. In essence, their result implies that in the Type-III setting, the only way to meet the 3 group element lower bound is to either employ interactive intractability assumptions or resort to direct proofs in the generic group model. Ghadafi [25] gave a structure-preserving variant of the Camenisch-Lysyanskaya signature scheme [15] that is secure under an interactive assumption in the Type-III setting. Abe et al. [7] constructed a scheme in the Type-II setting (where there is an efficiently computable isomorphism from the second source group to the first) which contains only 2 group elements. Chatterjee and Menezes [17] revisited the work of [7] and showed that Type-III constructions outperform their Type-II counterparts [17] also gave constructions in Type-III setting meeting the 3 group element lower bound. Barthe et al. [10] also gave optimal constructions of structure-preserving signatures in Type-II setting. Constructions relying on standard assumptions (such as DLIN and DDH) were given by [1, 2, 14, 16, 33, 35]. Constructions based on standard assumptions are less efficient than those based on non-standard assumptions or proven directly in the generic group model. Recently, Abe et al. [8] and Groth [30] gave fully structure-preserving constructions where even the secret key consists of only group elements.

While by now there exist a number of schemes, e.g. [4, 6, 10, 17, 30], with signatures meeting the 3 group element lower bound in the Type-III setting proved by Abe et al. [4], all those schemes have at least one component of the signature in group $\tilde{\mathbb {G}}$ whose elements bit size is at least double that of those in $\mathbb {G}$. To the best of our knowledge, the only existing structure-preserving signature scheme in the Type-III setting whose all signature components are in $\mathbb {G}$ is that of Ghadafi [25]. However, signatures of latter consist of 4 group elements and require 3 pairing-product verification equations.

Our Contribution. We construct a (unilateral) structure-preserving signature scheme with signatures shorter than all existing structure-preserving signatures. Our scheme yields fully re-randomizable signatures consisting of 3 group elements from the first short source group.

Our results also serve as a proof that the impossibility of unilateral structure-preserving signature schemes in the Type-III setting result of Abe et al. [4] does not apply when the message space is dual in both source groups. We stress that Abe et al. never claimed that their Type-III lower bounds apply to this setting since their proofs only considered schemes with unilateral messages. As is the tradition with most existing structure-preserving schemes, we prove the security of our scheme directly in the generic group model. Our scheme can be viewed as an extension of the recent non-structure-preserving signature scheme of Pointcheval and Sanders [38].

We show that replacing some existing schemes used as building blocks in some protocols with ours improves the efficiency of those protocols which include direct anonymous attestation and group signature related constructions.

Paper Organization. In Sect. 2, we give some preliminary definitions. In Sect. 3, we present our signature scheme and prove its security. We give some applications of our signature scheme in Sect. 4.

Notation. We write $y=A(x;r)$ when the algorithm A on input x and randomness r outputs y. We write $y\leftarrow A(x)$ for the process of setting $y=A(x;r)$ where r is sampled at random. We also write $y\leftarrow S$ for sampling y uniformly at random from a set S. A function $\nu (.): \mathbb {N}\rightarrow \mathbb {R}^+$ is negligible (in n) if for every polynomial p(.) and all sufficiently large values of n, it holds that $\nu (n)<\frac{1}{p(n)}$. By PPT we mean running in probabilistic polynomial time in the relevant security parameter. By [k], we denote the set $\{1,\ldots ,k\}$.

2 Preliminaries

In this section we provide some preliminary definitions.

2.1 Bilinear Groups

A bilinear group is a tuple $\mathcal {P}:=(\mathbb {G}, \tilde{\mathbb {G}}, \mathbb {T}, p, G, \tilde{G}, e)$ where $\mathbb {G}$, $\tilde{\mathbb {G}}$ and $\mathbb {T}$ are groups of a prime order p, and G and $\tilde{G}$ generate $\mathbb {G}$ and $\tilde{\mathbb {G}}$, respectively. The function $e$ is a non-degenerate bilinear map $e: \mathbb {G}\times \tilde{\mathbb {G}}\longrightarrow \mathbb {T}$.

For clarity, elements of $\tilde{\mathbb {G}}$ will be accented with $\tilde{~}$. We use multiplicative notation for all the groups. We let $\mathbb {G}^\times := \mathbb {G}\setminus \{1_{\mathbb {G}}\}$ and $\tilde{\mathbb {G}}^\times := \tilde{\mathbb {G}}\setminus \{1_{\tilde{\mathbb {G}}}\}$. In this paper, we work in the efficient Type-III setting [24], where $\mathbb {G}\ne \tilde{\mathbb {G}}$ and there is no efficiently computable isomorphism between the source groups in either direction. We assume there is an algorithm $\mathsf {BGSetup}$ that on input a security parameter $\lambda$, outputs a description of bilinear groups.

The message space of our signature scheme are elements of the subgroup $\hat{G}$ of $\mathbb {G}\times \tilde{\mathbb {G}}$ defined as the image of the map

$$ \psi : \left\{ \begin{array}{ccc} \mathbb {Z}_p &{} \longrightarrow &{} \mathbb {G}\times \tilde{\mathbb {G}}\\ x &{} \longmapsto &{} (G^x, \tilde{G}^x) \end{array} \right. $$

Given an element $(M,\tilde{N})\in \mathbb {G}\times \tilde{\mathbb {G}}$, one can efficiently test whether $(M,\tilde{N}) \in \hat{G}$ by checking $e(M,\tilde{G}) = e(G,\tilde{N})$.¹

2.2 Complexity Assumptions

Definition 1

(Decisional Diffie-Hellman (DDH) Assumption). The DDH assumption holds relative to a group setup $\mathcal {G}$ if for all PPT adversaries $\mathcal {A}$

$$ \Pr \left[ \begin{array}{l} (\mathbb {G}, G, p)\leftarrow \mathcal {G}(1^\lambda );~ r,s,t\leftarrow \mathbb {Z}_p;~b\leftarrow \{0,1\};\\ R:=G^r;~S:=G^{s};~ T:=G^{brs+(1-b)t} ~: \mathcal {A}(G,R,S,T)=b \end{array} \right] \le \frac{1}{2} + \nu (\lambda )~\cdot $$

Definition 2

(Symmetric External Diffie-Hellman (SXDH) Assumption). Given a bilinear group $\mathcal {P}:=(\mathbb {G}, \tilde{\mathbb {G}}, \mathbb {T}, p, G, \tilde{G}, e)$, the SXDH assumption requires that the DDH assumption holds in both groups $\mathbb {G}$ and $\tilde{\mathbb {G}}$.

2.3 Digital Signatures

A digital signature scheme (over a bilinear group $\mathcal {P}$ generated by $\mathsf {BGSetup}$) for a message space $\mathcal {M}$ is a tuple $\mathcal {DS}:=(\mathsf {KeyGen}, \mathsf {Sign}, \mathsf {Verify})$ whose definitions are:

• $\mathsf {KeyGen}(\mathcal {P})$ this probabilistic algorithm takes as input a bilinear group $\mathcal {P}$ and outputs a pair of secret/verification keys $(\mathsf {sk},\mathsf {vk})$.

• $\mathsf {Sign}(\mathsf {sk}, m)$ this probabilistic algorithm takes as input a secret key $\mathsf {sk}$ and a message $m \in \mathcal {M}$, and outputs a signature $\sigma$.

• $\mathsf {Verify}(\mathsf {vk}, m,\sigma )$ this deterministic algorithm outputs 1 if $\sigma$ is a vlaid signature on m w.r.t. the verification key $\mathsf {vk}$.

Definition 3

(Correctness). A signature scheme $\mathcal {DS}$ over a bilinear group generator $\mathsf {BGSetup}$ is (perfectly) correct if for all $\lambda \in \mathbb {N}$

$$\Pr \left[ \begin{array}{c} \mathcal {P}\leftarrow \mathsf {BGSetup}(1^\lambda ) ; (\mathsf {sk},\mathsf {vk})\leftarrow \mathsf {KeyGen}(\mathcal {P}) ;\\ m \leftarrow \mathcal {M}; \sigma \leftarrow \mathsf {Sign}(\mathsf {sk}, m) : \mathsf {Verify}(\mathsf {vk}, m,\sigma )=1 \end{array}\right] =1.$$

Definition 4

(Existential Unforgeability). A signature scheme $\mathcal {DS}$ over a bilinear group generator $\mathsf {BGSetup}$ is existentially unforgeable against adaptive chosen-message attack if for all $\lambda \in \mathbb {N}$ for all PPT adversaries $\mathcal {A}$

$$\Pr \left[ \begin{array}{c} \mathcal {P}\leftarrow \mathsf {BGSetup}(1^\lambda ) ; (\mathsf {sk},\mathsf {vk})\leftarrow \mathsf {KeyGen}(\mathcal {P}) ; (\sigma ^*,m^*)\leftarrow \mathcal {A}^{\mathsf {Sign}(\mathsf {sk}, \cdot )}(\mathcal {P},\mathsf {vk}) \\ ~~~~~~~~~~~~~~~~: \mathsf {Verify}(\mathsf {vk}, m^*,\sigma ^*)=1 \text{ and } m^* \notin Q_{\mathsf {Sign}} \end{array}\right] \le \nu (\lambda ),$$

where $Q_{\mathsf {Sign}}$ is the set of messages queried to $\mathsf {Sign}$.

We consider schemes which are re-randomizable (i.e. weakly unforgeable) in the sense that given a signature on a message m, anyone without knowledge of the signing key, can compute a fresh signature on the same message. A desirable property for such class of schemes is that randomized signatures are indistinguishable from fresh signatures on the same message. Thus, we define an algorithm $\mathsf {Randomize}$ which on input $(\mathsf {vk},m,\sigma )$, where $\sigma$ being a valid signature on m, outputs a new signature $\sigma ^\prime$ on m.

Definition 5

(Randomizability). A signature scheme $\mathcal {DS}$ over a bilinear group generator $\mathsf {BGSetup}$ is randomizable if for all $\lambda \in \mathbb {N}$ for all stateful adversaries $\mathcal {A}$

$$\Pr \left[ \begin{array}{l} \mathcal {P}\leftarrow \mathsf {BGSetup}(1^\lambda ); (\mathsf {sk},\mathsf {vk})\leftarrow \mathsf {KeyGen}(\mathcal {P});\\ (\sigma ^*,m^*)\leftarrow \mathcal {A}(\mathcal {P},\mathsf {sk},\mathsf {vk}); b \leftarrow \{0,1\};\\ \sigma _0 \leftarrow \mathsf {Sign}(\mathsf {sk},m^*); \sigma _1 \leftarrow \mathsf {Randomize}(\mathsf {vk},m^*,\sigma ^*);\\ ~~~~~: \mathsf {Verify}(\mathsf {vk}, m^*,\sigma ^*)=1 \text{ and } \mathcal {A}(\sigma _b)=b \end{array}\right] \le \frac{1}{2}+\nu (\lambda ).$$

We say the scheme has Perfect Randomizability when $\nu (\lambda )=0$. Note that the above definition of randomizability is stronger than the variant where the signature $\sigma ^*$ is generated by the challenger rather than the adversary herself.

Structure-Preserving Signatures. Structure-preserving signatures [3] are signature schemes defined over bilinear groups where the messages, the verification key and signatures are all group elements and verifying signatures only involves deciding group membership of the signature components and evaluating Pairing Product Equations (PPE) of the form of Eq. 1.

$$\begin{aligned} \prod \limits _{i}\prod \limits _{j}e({A}_i,\tilde{B}_j)^{c_{i,j}}=1_\mathbb {T}, \end{aligned}$$

(1)

where ${A}_i\in \mathbb {G}$ and $\tilde{B}_j \in \tilde{\mathbb {G}}$ are group elements appearing in $\mathcal {P}, m, \mathsf {vk}, \sigma$, whereas $c_{i,j}\in \mathbb {Z}_p$ are constants.

2.4 Randomizable Weakly Blind Signatures

A randomizable weakly blind signature scheme, as defined by Bernhard et al. [12], is similar to a standard blind signature scheme [18] but unlike the latter, in the former, the signer never gets to see the signed message. More precisely, in the blindness game of the former (referred to as weak blindness), the challenge messages are chosen by the challenger rather than the adversary and are never revealed to the adversary. Formally, a randomizable weakly blind signature scheme $\mathsf {BS}$ (with a two-move signature request phase) for a message space $\mathcal {M}_\mathsf {BS}$ consists of the following polynomial-time algorithms $\mathsf {BS}:=(\mathsf {Setup}_{\mathsf {BS}},\mathsf {KeyGen}_{\mathsf {BS}}, \mathsf {Request}_{\mathsf {BS}},\mathsf {Issue}_{\mathsf {BS}}, \mathsf {Verify}_{\mathsf {BS}},\mathsf {Randomize}_{\mathsf {BS}})$. All algorithms (bar $\mathsf {Setup}_{\mathsf {BS}}$) are assumed to take as (implicit) input a parameter set $\mathsf {param}_{\mathsf {BS}}$ output by $\mathsf {Setup}_{\mathsf {BS}}$.

• $\mathsf {Setup}_{\mathsf {BS}}(1^\lambda )$ outputs public parameters $\mathsf {param}_{\mathsf {BS}}$.

• $\mathsf {KeyGen}_{\mathsf {BS}}(\mathsf {param}_{\mathsf {BS}})$ outputs a public/secret key pair $(\mathsf {vk}_\mathsf {BS},\mathsf {sk}_\mathsf {BS})$ for the signer.

• $(\mathsf {Request}_{\mathsf {BS}}^0,\mathsf {Issue}_{\mathsf {BS}}^1,\mathsf {Request}_{\mathsf {BS}}^1)$ is an interactive protocol run between a user and a signer. The protocol is initiated by the user by calling $\mathsf {Request}_{\mathsf {BS}}^0(\mathsf {vk}_\mathsf {BS},m)$ to obtain a value $\rho _0$ and some state information $\mathsf {st}_R^0$ (which is assumed to contain the message m). Then the signer and user execute, respectively,

  $$ (\beta _1,\mathsf {st}_I^1) \leftarrow \mathsf {Issue}_{\mathsf {BS}}^1(\mathsf {sk}_\mathsf {BS},\rho _{0}) \text{ and } \sigma \leftarrow \mathsf {Request}_{\mathsf {BS}}^1(\beta _1,\mathsf {st}_R^{0}), $$

  where $\sigma$ is a signature on the message m (or the reject symbol $\perp$). We write $\sigma \leftarrow \langle \mathsf {Request}_{\mathsf {BS}}(\mathsf {vk}_\mathsf {BS},m) , \mathsf {Issue}_{\mathsf {BS}}(\mathsf {sk}_\mathsf {BS}) \rangle$ for the output of correct running of this protocol on the given inputs.

• $\mathsf {Verify}_{\mathsf {BS}}(\mathsf {vk}_\mathsf {BS},m,\sigma )$ outputs 1 if $\sigma$ is a valid signature on m and 0 otherwise.

• $\mathsf {Randomize}_{\mathsf {BS}}(\mathsf {vk}_\mathsf {BS},\sigma )$ given a signature $\sigma$ on an unknown message m, produces another valid signature $\sigma ^\prime$ on the same message.

Definition 6

(Correctness). A randomizable weakly blind signature scheme is (perfectly) correct if for all $\lambda \in \mathbb {N}$

$$\Pr \left[ \begin{array}{l} \mathsf {param}_\mathsf {BS}\leftarrow \mathsf {Setup}_{\mathsf {BS}}(1^\lambda ); (\mathsf {vk}_\mathsf {BS},\mathsf {sk}_\mathsf {BS}) \leftarrow \mathsf {KeyGen}_{\mathsf {BS}}(\mathsf {param}_{\mathsf {BS}});\\ m \leftarrow \mathcal {M}_\mathsf {BS}; \sigma \leftarrow \langle \mathsf {Request}_{\mathsf {BS}}(\mathsf {vk}_\mathsf {BS},m),\mathsf {Issue}_{\mathsf {BS}}(\mathsf {sk}_\mathsf {BS}) \rangle ;\\ \sigma ^\prime \leftarrow \mathsf {Randomize}_{\mathsf {BS}}(\mathsf {vk}_\mathsf {BS}, \sigma )\\ ~~: \mathsf {Verify}_{\mathsf {BS}}(\mathsf {vk}_\mathsf {BS}, m,\sigma ) = 1 \text{ and } \mathsf {Verify}_{\mathsf {BS}}(\mathsf {vk}_\mathsf {BS},m,\sigma ^\prime ) = 1 \end{array}\right] =1.$$

Definition 7

(Unforgeability). A randomizable weakly blind signature scheme is unforgeable if for all $\lambda \in \mathbb {N}$, all PPT adversaries $\mathcal {A}$ have a negligible advantage in the game in Fig. 1.

Fig. 1.

The unforgeability game for randomizable weakly blind signatures

Definition 8

(Weak Blindness). A randomizable weakly blind signature scheme is weakly blind if for all $\lambda \in \mathbb {N}$, all PPT adversaries $\mathcal {A}$ have a negligible advantage in the game in Fig. 2.

Fig. 2.

The weak blindness game for randomizable weakly blind signatures

2.5 Groth-Sahai Proofs

Groth-Sahai (GS) proofs [31] are non-interactive proofs in the CRS model. We will use GS proofs that are secure under the SXDH assumption, which is the most efficient instantiation of the proof system [27], and that prove knowledge of witnesses to pairing-product equations of the form

$$\begin{aligned} \prod _{j=1}^n e(A_j,\underline{\tilde{Y}_j})\,\prod _{i=1}^m e(\underline{X_i},\tilde{B}_i)\,\prod _{i=1}^m\prod _{j=1}^n e(\underline{X_i},\underline{\tilde{Y}_j})^{\gamma _{i,j}}\ =\ \prod _{\ell =1}^k e(G_\ell ,\tilde{H}_\ell ) \end{aligned}$$

(2)

All underlined variables are part of the witness whereas the rest of the values are public constants. The language for these proofs is of the form $\mathcal {L}:=\{\mathsf {statement} \mid \exists \,\mathsf {witness}:E(\mathsf {statement},\mathsf {witness})\text {~holds~}\},$ where $E(\mathsf {statement},\cdot )$ is a set of pairing-product equations. The system is defined by a tuple of algorithms $(\mathsf {GS}{\mathsf {Setup}},\mathsf {GS}{\mathsf {Prove}},\mathsf {GS}{\mathsf {Verify}},\mathsf {GS}{\mathsf {Extract}},\mathsf {GS}{\mathsf {SimSetup}},\mathsf {GS}{\mathsf {SimProve}})$. $\mathsf {GS}{\mathsf {Setup}}$ takes as input the description of a bilinear group $\mathcal {P}$ and outputs a binding reference string $\mathsf {crs}$ and an extraction key $\mathsf {xk}$. $\mathsf {GS}{\mathsf {Prove}}$ takes as input the string $\mathsf {crs}$, a set of equations $\mathsf {statement}$ and a witness, and outputs a proof $\varOmega$ for the satisfiability of the equations. $\mathsf {GS}{\mathsf {Verify}}$ takes as input a set of equations, a string $\mathsf {crs}$ and a proof $\varOmega$ and outputs 1 if the proof is valid, and 0 otherwise. $\mathsf {GS}{\mathsf {Extract}}$ takes as input a binding $\mathsf {crs}$, the extraction key $\mathsf {xk}$ and a valid proof $\varOmega$, and outputs the witness used for the proof. $\mathsf {GS}{\mathsf {SimSetup}}$, on input a bilinear group $\mathcal {P}$, outputs a hiding string $\mathsf {crs}_\text {Sim}$ and a trapdoor key $\mathsf {tr}$ that allows to simulate proofs. $\mathsf {GS}{\mathsf {SimProve}}$ takes as input $\mathsf {crs}_\text {Sim}$, a statement and the trapdoor $\mathsf {tr}$ and produces a simulated proof $\varOmega _\text {Sim}$ without a witness. The distributions of strings $\mathsf {crs}$ and $\mathsf {crs}_\text {Sim}$ are computationally indistinguishable and simulated proofs are indistinguishable from proofs generated by an honest prover. The proof system has perfect completeness, (perfect) soundness, composable witness-indistinguishability/composable zero-knowledge. We refer to [31] for the formal definitions and the details of the instantiations.

3 Our Structure-Preserving Signature Scheme

Given the description of Type-III bilinear groups $\mathcal {P}$ output by $\mathsf {BGSetup}(1^\lambda )$, our scheme is given by the following four algorithms.

• $\mathsf {KeyGen}(\mathcal {P})$: Select $x,y \leftarrow \mathbb {Z}^\times _p$. Set $\mathsf {sk}:=(x,y)$ and $\mathsf {vk}:=(\tilde{X},\tilde{Y}) :=(\tilde{G}^{x}, \tilde{G}^{y})$.

• $\mathsf {Sign}(\mathsf {sk},(M,\tilde{N}))$: To sign a message $(M,\tilde{N})\in \hat{G}$, (i.e. $(M,\tilde{N}) \in \mathbb {G}\times \tilde{\mathbb {G}}$ and $e(M,\tilde{G})=e(G,\tilde{N})$), select $a \leftarrow \mathbb {Z}^\times _p$, and set $A:=G^a$, $B :=M^a$, $C:=A^{x} \cdot B^{y}$. Return $\sigma :=(A,B,C)\in \mathbb {G}^3$.

• $\mathsf {Verify}(\mathsf {vk},(M,\tilde{N}),\sigma =(A,B,C))$: Return 1 iff $A\in \mathbb {G}^\times$ (i.e. $A\ne 1_\mathbb {G}$), $B,C \in \mathbb {G}$, $(M,\tilde{N}) \in \hat{G}$, and all of the following hold:

  $$\begin{aligned}&e(A, \tilde{N})=e(B, \tilde{G})\\&e(C, \tilde{G}) = e(A, \tilde{X}) e(B, \tilde{Y}) \end{aligned}$$

• $\mathsf {Randomize}(\mathsf {vk},(M,\tilde{N}),\sigma =(A,B,C))$: Select $r \leftarrow \mathbb {Z}^\times _p$, and set $A^\prime :=A^r$, $B^\prime :=B^r$, $C^\prime :=C^{r}$. Return $\sigma ^\prime :=(A^\prime ,B^\prime ,C^\prime )$.

Remark 1

Note that verifying the well-formedness of the message pair, i.e. that $(M,\tilde{N}) \in \hat{G}$, need only be done once when verifying multiple signatures on the same message. A similar argument applies to signature schemes with the same message space, e.g. [3, 22, 25].

Also, note that requiring checking that $A\ne 1_{\mathbb {G}}$ in the verification can in some sense be considered a slight deviation from the rigorous variant of the definition of structure-preserving signatures. However, since A is information-theoretically independent of the message, even when proving knowledge of a signature, one can reveal A after re-randomizing it which allows for verifying such a condition for free. We end by noting that Ghadafi [25] gave efficient Groth-Sahai proofs that a committed Groth-Sahai value is not the identity element.

Correctness of the scheme follows by inspection and is straightforward to verify. Also, that the signature is perfectly randomizable is straightforward. The distributions of valid signatures returned by the $\mathsf {Randomize}$ algorithm are identical to those returned by the $\mathsf {Sign}$ algorithm on the same message. Also, note that assuming the signature to be re-randomized is valid, one only needs the old signature to be able to produce a new one.

The following theorem proves that the scheme is unforgeable in the generic group model [37, 40]. We note here that the unforgeability of the scheme could also be based on an interactive assumption.

Theorem 1

The structure-preserving signature scheme is (weakly) existentially unforgeable against adaptive chosen-message attack in the generic group model.

Proof. The proof follows from the proof of the following theorem:

Theorem 2

Let $\mathcal {A}$ be an adversary in the generic group model against our scheme. Assume $\mathcal {A}$ makes $q_G$ group operation queries, $q_P$ pairing queries, and $q_S$ sign queries. The probability $\epsilon$ of adversary $\mathcal {A}$ winning the game is bounded by $\epsilon \le \frac{(q_G+q_P+3 q_S + 4)^2 \cdot 3}{p}$, where p is the (prime) order of the generic groups.

Proof. We start by re-stating the following Schwartz Zippel lemma [39]:

Lemma 1

Let p be a prime and $P(x_1 ,\ldots , x_n )\in \mathbb F_p[x_1 ,\ldots , x_n]$ be a non-zero polynomial with a total degree $\le d$. Then the probability that $P(x_1 ,\ldots , x_n )=0$ is $\le \frac{d}{p}$.

Adversary $\mathcal {A}$ interacts with those oracles via group handles. We define three random encoding functions $\xi _1: \mathbb {G}\longrightarrow \{0,1\}^*$, $\xi _2: \tilde{\mathbb {G}}\longrightarrow \{0,1\}^*$ and $\xi _3: \mathbb {T}\longrightarrow \{0,1\}^*$ where $\xi _i$ maps elements from the corresponding group into random strings. The challenger keeps three lists $\mathcal {L}_1, \mathcal {L}_2, \mathcal {L}_T$ which contain pairs of the form $(\tau ,P)$ where $\tau$ is a “random” encoding of the group element (i.e. $\tau$ is an output of the map $\xi _i$) and P is some polynomial in $\mathbb F_p[X,Y,A_1,\ldots ,A_{q_S}]$.

To each list we associate an $\mathsf {Update}$ algorithm, that takes as input the specific list $\mathcal {L}_i$ and a polynomial P. The algorithm $\mathsf {Update}(\mathcal {L}_i,P)$ searches the list in question for a pair whose second component is equal to P, if such a pair is found, the algorithm returns its first component as a result. Otherwise, a new random encoding $\tau$, different from all other elements used so far, is chosen and the pair $(\tau ,P)$ is added to the list $\mathcal {L}_i$. The value $\tau$ is then returned. Note that at no point $\mathcal {A}$ gets access to the second element in the pairs.

The challenger starts by calling: $\mathsf {Update}(\mathcal {L}_1,1)$, $\mathsf {Update}(\mathcal {L}_2,1)$, $\mathsf {Update}(\mathcal {L}_2,X)$ and $\mathsf {Update}(\mathcal {L}_2,Y)$. Those correspond to the group elements $G\in \mathbb {G}$ and $\tilde{G},\tilde{X},\tilde{Y}\in \tilde{\mathbb {G}}$ of the verification key and public elements the adversary gets in the scheme.

The oracles used in the game are defined as follows:

• Group Oracles: Oracles $\mathcal {O}_1$, $\mathcal {O}_2$ and $\mathcal {O}_T$ allow $\mathcal {A}$ access to the group operations in groups $\mathbb {G},\tilde{\mathbb {G}}$ and $\mathbb {T}$, respectively, via subtraction/addition operations. On a call to $\mathcal {O}_i(\tau _1,\tau _2)$ $\mathcal {B}$ searches list $\mathcal {L}_i$ for pairs of the form $(\tau _1,P_1)$ and $(\tau _2,P_2)$. If both pairs exist, $\mathcal {B}$ returns the output of $\mathsf {Update}(\mathcal {L}_i,P_1\pm P_2)$. Otherwise, it returns $\perp$. Note that exponentiation operations can be performed by calls to the group operation oracles.

• Pairing Oracle: Oracle $\mathcal {O}_P$ allows $\mathcal {A}$ to perform pairing operations. On a call to $\mathcal {O}_P(\tau _1,\tau _2)$, $\mathcal {B}$ searches the list $\mathcal {L}_1$ for the pair $(\tau _1,P_1)$, and the list $\mathcal {L}_2$ for the pair $(\tau _2,P_2)$. If both pairs exist, $\mathcal {B}$ returns the output of $\mathsf {Update}(\mathcal {L}_T,P_1 \cdot P_2)$. Otherwise, it returns $\perp$.

• Sign Oracle: The adversary may make up to $q_S$ queries $\mathcal {O}_{S}(\tau _1,\tau _2)$. The challenger searches list $\mathcal {L}_1$ for a pair $(\tau _1,P_1)$ and list $\mathcal {L}_2$ for a pair $(\tau _2,P_2)$. If they do not exist or $P_1\ne P_2$, $\mathcal {B}$ returns $\perp$. Otherwise, it executes the following operations, where $A_i, X$ and Y are indeterminants:

  $$\begin{aligned} \tau _{A_i}&\leftarrow \mathsf {Update}(\mathcal {L}_1, A_i),\\ \tau _{B_i}&\leftarrow \mathsf {Update}(\mathcal {L}_1, A_i \cdot P_1),\\ \tau _{C_i}&\leftarrow \mathsf {Update}(\mathcal {L}_1, A_i \cdot (X + P_1 \cdot Y) ). \end{aligned}$$

  Returning the tuple $(\tau _{A_i},\tau _{B_i},\tau _{C_i})$ to $\mathcal {A}$.

By using the above oracles, we can simulate the entire run of the adversary. At the end of the game, the total number of non-constant polynomials contained in the three lists $\mathcal {L}_1, \mathcal {L}_2$ and $\mathcal {L}_T$ is bounded from above by $t=q_G+q_P+3 q_S+ 4$.

The Adversary Output. Eventually, $\mathcal {A}$ outputs a tuple $\left( \tau _{A^*}, \tau _{B^*},\tau _{C^*},\tau _{M^*},\tau _{\tilde{N}^*}\right)$, where $\tau _{A^*}$, $\tau _{B^*}$, $\tau _{C^*}$, and $\tau _{M^*}$ are on list $\mathcal {L}_1$ while $\tau _{\tilde{N}^*}$ is on list $\mathcal {L}_2$. Let $P_{A^*}, P_{B^*}, P_{C^*}, P_{M^*}, P_{\tilde{N}^*}$ denote their associated polynomials. For $\mathcal {A}$’s output to be valid, those polynomials can be assumed to satisfy, for some assignment $(x,y,a_1,\ldots ,a_{q_S}) \in \mathbb F^{2+q_S}_p$ to the variables $(X,Y,A_1,\ldots ,A_{q_S})$, the equations:

$$\begin{aligned} P_{B^*}&= P_{A^*} \cdot P_{\tilde{N}^*} \end{aligned}$$

(3)

$$\begin{aligned} P_{C^*}&= P_{A^*} \cdot X + P_{B^*} \cdot Y \end{aligned}$$

(4)

$$\begin{aligned} P_{M^*}&= P_{\tilde{N}^*} \end{aligned}$$

(5)

From this we derive a contradiction, i.e. conclude that the adversary cannot win the game. To achieve this, we need to first ensure that these polynomial identities cannot hold identically, i.e. regardless of any particular assignment $(x,y,a_1,\ldots ,a_{q_S}) \in \mathbb F^{2+ q_S}_p$ to the variables $(X,Y,A_1,\ldots ,A_{q_S})$.

Let $(M_{i},\tilde{N}_{i})$ denote the i-th signing query where we discount queries where $(M_{i},\tilde{N}_{i}) \notin \hat{G}$. Note that $P_{\tilde{N}_i}$ can only be a linear combination of the terms 1, X and Y. Thus, we have $P_{\tilde{N}_i} = r_i + s_i \cdot X + t_i \cdot Y$. Since we must have $P_{M_i}=P_{\tilde{N}_i}$, this implies that the above polynomials must also appear on the list $\mathcal {L}_1$. However, there is no operation in $\mathbb {G}$ which creates a polynomial with a monomial term of X, nor one of Y. Thus, we conclude that all queries to the sign oracle correspond to elements whose polynomials are a constant term of the form $P_{M_i}=P_{\tilde{N}_i}=r_i$. By a similar argument, we can also deduce that the output of the adversary corresponds to polynomials with $P_{M^*}=P_{\tilde{N}^*}=r^*$. This is precisely where we use the property that the oracle will return $\perp$ unless the input query lies in $\hat{G}$.

Note that $P_{A^*}$, $P_{B^*}$, and $P_{C^*}$ can only by a linear combination of the polynomials appearing on the list $\mathcal {L}_1$. Therefore, we have:

$$\begin{aligned} P_{A^*}&= w_{1} + \sum \limits _{i=1}^q u_{1,i} \cdot A_i + \sum \limits _{i=1}^q v_{1,i} \cdot A_i \cdot (X + r_i \cdot Y ) \end{aligned}$$

(6)

$$\begin{aligned} P_{B^*}&= w_{2} + \sum \limits _{i=1}^q u_{2,i} \cdot A_i + \sum \limits _{i=1}^q v_{2,i} \cdot A_i \cdot (X + r_i \cdot Y ) \end{aligned}$$

(7)

$$\begin{aligned} P_{C^*}&= w_{3} + \sum \limits _{i=1}^q u_{3,i} \cdot A_i + \sum \limits _{i=1}^q v_{3,i} \cdot A_i \cdot (X + r_i \cdot Y ) , \end{aligned}$$

(8)

where $w_j, u_{j,i}, v_{j,i} \in \mathbb F_p$.

Note that $P_{C^*}$, i.e. Eq. (8), there is no monomial with a power $>1$ of Y. Also, there is no monomial in $X\cdot Y$. Thus, by Eq. (4), we must have $v_{1,i}=v_{2,i}=0$ for all i. Thus, we have

$$\begin{aligned} P_{A^*}= w_{1} + \sum \limits _{i=1}^q u_{1,i} \cdot A_i&~~~~~~~~&P_{B^*}= w_{2} + \sum \limits _{i=1}^q u_{2,i} \cdot A_i \end{aligned}$$

Now by Eq. (3) we must have that

$$ w_{2} + \sum \limits _{i=1}^q u_{2,i} \cdot A_i = r^*\cdot w_{1} + \sum \limits _{i=1}^q r^* \cdot u_{1,i} \cdot A_i $$

For the above to hold, we must have $w_{2}=r^*\cdot w_{1}$ and $r^* \cdot u_{1,i}= u_{2,i}$ for all i.

By Eq. (4), we must have

$$\begin{aligned} w_{3} + \sum \limits _{i=1}^q u_{3,i} \cdot A_i&+ \sum \limits _{i=1}^q v_{3,i} \cdot A_i \cdot (X + r_i \cdot Y ) \\&=w_{1} \cdot X + \sum \limits _{i=1}^q u_{1,i} \cdot A_i \cdot X + r^*\cdot w_{1} \cdot Y + \sum \limits _{i=1}^q r^* \cdot u_{1,i} \cdot A_i \cdot Y \end{aligned}$$

There is no term in X on the left-hand side so we must have $w_{1}=0$. Also, no constant terms or terms in $A_i$ on the right-hand side so we must have $w_3=0$ and $u_{3,i}=0$ for all i. Thus, we must have

$$\begin{aligned} \sum \limits _{i=1}^q v_{3,i} \cdot A_i \cdot X + \sum \limits _{i=1}^q v_{3,i} \cdot r_i \cdot A_i \cdot Y = \sum \limits _{i=1}^q u_{1,i} \cdot A_i \cdot X + \sum \limits _{i=1}^q r^* \cdot u_{1,i} \cdot A_i \cdot Y \end{aligned}$$

By the monomial $A_i \cdot X$, we must have $u_{1,i}=v_{3,i}$ for all i. Since we must have $A^*\ne 1_{\mathbb {G}}$, we must have at least one pair $u_{1,i}=v_{3,i}\ne 0$ for some i. By the monomial $A_i \cdot Y$, we must have $v_{3,i} \cdot r_i = r^* \cdot u_{1,i}$. Since as we have seen we must have $u_{1,i}=v_{3,i}$, we have $r_i = r^*$ which contradicts the unforgeability requirement as the forgery is on a message pair that was queried to the sign oracle.

Thus, the adversary must win, or tell it is in a simulation, via a specific (random) assignment to the variables. We now turn to bounding the probability that the adversary wins (or detects the simulation) in this case.

The Simulation. Now the challenger chooses random values $x,y,a_i\in \mathbb F_p$ and evaluates the polynomials. We need to show that the challenger’s simulation is sound. If $\mathcal {A}$ learned it was interacting in a simulated game, there would be two different polynomials $P_{i,j}(x,y,a_i)=P_{i,j'}(x,y,a_i)$ in list $\mathcal {L}_i$ where $P_{i,j}\ne P_{i,j'}$. The simulation will fail if any of the following is correct:

$$\begin{aligned} P_{1,j}(x,y,a_i)&=P_{1,j'}(x,y,a_i) \end{aligned}$$

(9)

$$\begin{aligned} P_{2,j}(x,y,a_i)&=P_{2,j'}(x,y,a_i) \end{aligned}$$

(10)

$$\begin{aligned} P_{T,j}(x,y,a_i)&=P_{T,j'}(x,y,a_i) \end{aligned}$$

(11)

Since the maximum degree of any polynomial in list $\mathcal {L}_1$ $\le 2$, by applying [40][Lemma 1], we have that the probability of Eq. (9) holding is $\le \frac{2}{p}$. Similarly, since the maximum degree of any polynomial in list $\mathcal {L}_2$ $\le 1$, we have that the probability of Eq. (10) holding is $\le \frac{1}{p}$. Finally, the probability of Eq. (11) holding is $\le \frac{3}{p}$.

Summing over all possible values of j in each case, we have

$$\epsilon \le \left( \begin{array}{c} |\mathcal {L}_1| \\ 2 \end{array} \right) \frac{2}{p} + \left( \begin{array}{c} |\mathcal {L}_2| \\ 2 \end{array} \right) \frac{1}{p} + \left( \begin{array}{c} |\mathcal {L}_T| \\ 2 \end{array} \right) \frac{3}{p}, $$

where $|\mathcal {L}_i|$ denotes the size of list $\mathcal {L}_i$.

In conclusion, the probability that an adversary wins the unforgeability game is bounded by $\epsilon \le \frac{(q_G+q_P+3 q_S + 4)^2 \cdot 3}{p}$.    $\square$

3.1 Efficiency Comparison

We compare in Table 1 the efficiency of our scheme with that of existing schemes for a single a message in the Type-III setting. For concrete comparison, for instance, at 128-bit security, elements of $\mathbb {G}$ and $\tilde{\mathbb {G}}$ in Type-III are 256 and 512 bits long, respectively. Therefore, our signatures at this security level are at least 256 bits shorter than the best existing scheme. The efficiency gain is even better as the security level increases. Also, as can be seen, our scheme compares favorably to existing ones in terms of the efficiency of the verification equation. For the schemes whose message space is $\hat{G}$, the cost does not include checking membership of the message in the relevant group. As discussed earlier, such a check only needs to be performed once when verifying multiple signatures on the same message. Note that many applications require the signer to prove possession of/provide multiple signatures/credentials (possibly from different signers/issuers).

Also, our scheme works well in association with the (less efficient) automorphic structure-preserving signature scheme of [3, 22] since the message and key spaces of the latter lie in the message space of our scheme.

Table 1. Efficiency comparison between our scheme and other schemes

It is obvious that structure-preserving signatures (on unilateral messages) in the Type-III setting have shorter messages than schemes, including ours, whose message space is $\hat{G}$. However, we stress that this is a small price to pay to get shorter signatures and more efficient verification while remaining in the most efficient Type-III bilinear group setting.

4 Applications of Our Scheme

In this section we give some examples of how using our signature scheme improves the efficiency of some existing cryptographic protocols.

4.1 Direct Anonymous Attestation

Bernhard et al. [11] gave the first instantiations of Direct Anonymous Attestation (DAA) [13] which do not rely on random oracles. Their constructions are instantiations of Bernhard et al. [12] generic construction. Among other things, the generic construction of the latter requires a randomizable weakly blind signature. The weakly blind signature is used in the join protocol to issue a credential to the user without learning her secret key. Note that unlike in group signatures [19], in DAA users do not have public keys matching their secret keys.

To get an efficient instantiation of the notion and hence an efficient instantiation of DAA (without relying on random oracles), the efficient instantiation of Bernhard et al. [11] combined Ghadafi’s structure-preserving signature scheme [25] with Groth-Sahai proofs [31] to construct an efficient weakly blind signature scheme. Their weakly blind signature instantiation yields signatures of size $\mathbb {G}^4$ and require 3 PPE equations (7 pairings or 6 pairings and 1 elliptic curve point addition in total) to verify. Exploiting the fact that our signature scheme has a similar structure to Ghadafi’s scheme but yet has shorter signatures and the verification algorithm is more efficient, we get a more efficient instantiation of weakly blind signatures and hence DAA by using our scheme instead. The weakly blind signature (see Fig. 3) obtained by combining our signature scheme with Groth-Sahai proofs yields signatures of size $\mathbb {G}^3$ and require only 2 PPE equations (5 pairings in total) to verify. Also, the communication complexity of both the user and the signer in the signing protocol is the same as that in the instantiation in [11]. Thus, using our scheme one gets more efficient instantiations of DAA without relying on random oracles.

Fig. 3.

Our weakly blind signature scheme

In the construction detailed in Fig. 3, we use the following languages for the zero-knowledge proofs for the user and signer respectively²:

$$\begin{aligned} \mathcal {L}_{1}&:\Big \{ \big (M, (\tilde{N}, \tilde{G}^\prime )\big ):e(G, \underline{ \tilde{N}}) = e(M, {\underline{\tilde{G}^\prime }}) ~\wedge ~ \underline{\tilde{G}^\prime } \cdot \tilde{G}^{-1}= 1_{\tilde{\mathbb {G}}} \Big \} \\ \mathcal {L}_{2}&:\Big \{ \big ((A, B, M), (\tilde{A},\tilde{G}^\prime )\big ):e(G, \underline{ \tilde{A}}) = e(A, \underline{\tilde{G}^\prime }) ~\wedge ~ e(M, \underline{ \tilde{A}}) = e(B, \underline{\tilde{G}^\prime }) ~\wedge ~ \underline{\tilde{G}^\prime } \cdot \tilde{G}^{-1}= 1_{\tilde{\mathbb {G}}} \Big \} \end{aligned}$$

We prove following theorem in the full version of the paper [26].

Theorem 3

If the SXDH assumption holds and the signature scheme is existentially unforgeable, the weakly blind signature scheme in Fig. 3 is secure.

4.2 Group Signatures and Similar Primitives

In all constructions of group signatures [19], the issuer (the group manager) issues membership certificates by certifying users’ verification keys. The message space of our scheme being the set of Diffie-Hellman pairs makes our scheme ideal to be combined with the automorphic structure-preserving signature scheme of Fuchsbauer [3, 22]. For instance, combining our signature scheme with Fuchsbauer’s blind signature scheme [3, 22], we get more efficient instantiations of group blind signatures [25, 36] (without relying on random oracles) than those in [25]. An instantiation using our signature scheme yields group blind signatures of size $36 \cdot |\mathbb {G}| + 34\cdot |\tilde{\mathbb {G}}|$ compared to $38 \cdot |\mathbb {G}| + 36\cdot |\tilde{\mathbb {G}}|$ and $42 \cdot |\mathbb {G}| + 38\cdot |\tilde{\mathbb {G}}|$ for the original constructions given in [25]. Also, since the final signature involves less Groth-Sahai proofs, the verification algorithm is much more efficient as each Groth-Sahai proof requires a few pairings to verify.