How Low Can You Go? Short Structure-Preserving Signatures for Diffie-Hellman Vectors

Abstract

Structure-Preserving Signatures (SPSs) are an important tool for the design of modular cryptographic protocols. It has been proven that such schemes in the most efficient Type-3 bilinear group setting have a lower bound of 3-element signatures, which must include elements from both base groups, and a verification overhead of at least 2 Pairing-Product Equations (PPEs). Very recently, Ghadafi (ESORICS 2017) showed that by restricting the message space to the set of Diffie-Hellman pairs (which does not hinder applicability of the schemes), some of the existing lower bounds for the single message case can be circumvented. However, the case of signing multiple messages, which is required for many applications, was left as an open problem since the techniques used for signing single messages do not seem to lend themselves to the multi-message setting. In this work we investigate this setting and answer the question in the affirmative. We construct schemes that sign vectors of messages and which yield shorter signatures than optimal schemes for vectors of unilateral messages. More precisely, we construct 2 fully randomiazble schemes that sign vectors of Diffie-Hellman pairs yielding signatures consisting of only 2 elements regardless of the size of the vector signed. We also construct a unilateral scheme that signs a pair of messages yielding signatures consisting of 3 elements from the shorter base group. All of our schemes require a single PPE for verification (not counting the cost of verifying the well-formedness of the messages). Thus, all of our schemes compare favourably to all existing schemes with respect to signature size and verification overhead. Even when considering single messages, our first 2 schemes compare favourably to the best existing schemes in many aspects including the verification overhead and the key size.

1 Introduction

Structure-Preserving Signatures (SPSs) [3] are pairing-based signature schemes where the message, the verification key and the signature consist of only group elements from one or both base groups, and signature verification requires evaluating Pairing-Product Equations (PPEs). Due to their elegant structure and the fact that they compose nicely with existing widely used tools such as ElGamal encryption [20] and Groth-Sahai proofs [34], SPS schemes are an ideal building block for designing cryptographic protocols not relying on random oracles [22].

The notion has numerous applications which include group signatures, e.g [3, 38], blind signatures, e.g. [3, 25], attribute-based signatures, e.g. [21], tightly secure encryption, e.g. [2, 35], malleable signatures, e.g. [9], anonymous credentials, e.g. [16, 24], network coding, e.g. [9], oblivious transfer, e.g. [31], direct anonymous attestation, e.g. [13, 28], and e-cash, e.g. [10].

Related Work. The term “structure-preserving signature” was first formally introduced by Abe et al. [3] but earlier schemes conforming to the definition were given in [31, 32]. The notion has received a significant amount of attention and many studies on the notion have been published. Constructions of such schemes in the Type-3 setting (cf. Section 2.1) include [3, 4, 6, 19, 27, 33]. The vast majority of those constructions rely on security proofs in the generic group model [40, 41]. Abe et al. [4] proved that signatures of any scheme in the Type-3 bilinear group setting must contain at least 3 elements, which must include elements from both base groups, and require at least 2 PPEs for verification. This rules out the existence of schemes with unilateral signatures, i.e. where all components of the signature are from the same group.

Constructions relying on standard assumptions, e.g. DLIN and DDH, were given by [1, 2, 15, 18, 36,37,38]. Abe et al. [5] proved that it is impossible to base the security of an optimal Type-3 scheme on non-interactive intractability assumptions. Their result guarantees that schemes based on non-interactive intractability assumptions can never be as efficient as their counterparts relying on interactive assumptions or those proven secure directly in the generic group model. In fact all existing constructions based on standard (static) assumptions are far less efficient than existing optimal schemes.

Recently, Ghadafi [28] gave a randomizable scheme yielding signatures consisting of 3 elements from the shorter base group which signs a single Diffie-Hellman (cf. Section 2.1) pair. Signatures of his scheme are shorter than those of optimal schemes for unilateral messages since the bit size of the elements of the second base group are at least twice that of those from the first base group. Verification in his scheme requires, besides checking the well-formedness of the message, the evaluation of 2 PPEs. However, his scheme is only capable of signing a single message and it is unclear whether it can be extended (or even if that is at all possible) to signing multiple messages while preserving the signature size. More recently, Ghadafi [29] defined the notion of unilateral structure-preserving signatures on Diffie-Hellman pairs and gave constructions for a single Diffie-Hellman pair yielding signatures consisting of only 2 elements from the shorter base group. Ghadafi argued that restricting the message space to the set of Diffie-Hellman pairs does not restrict applicability of the schemes and used direct anonymous attestation [14], which is a protocol deployed in practice, and attribute-based signatures [39] as an example. Even though Ghadafi [29] gave a partially structure-preserving scheme which can sign a vector of field elements along the single Diffie-Hellman pair, it was left as an open problem to investigate the case of structure-preserving signatures for a vector of group elements.

Constructions in the Type-2 setting (where there is an efficiently computable homomorphism between the base groups in one direction) were given in [7, 11, 19]. Fully structure-preserving schemes where even the secret key consists of only group elements from the base groups were recently given by [8, 33, 42].

Numerous applications require signing a vector of group elements, e.g. when certifying the public key of an encryption/signature scheme, without hindering the structure of the messages, i.e. without hashing. This is particularly important when the aim is to avoid relying on random oracles. Therefore, the design of efficient signature schemes conforming to those requirements would have implications for various applications. Note that SPS schemes for Diffie-Hellman tuples proved useful for many applications see e.g. [3, 13, 24, 27, 29].

Our Contribution. We construct 3 new fully randomizable structure-preserving schemes for vectors of messages which yield shorter signatures than all existing schemes for vectors of unilateral messages. Our first 2 schemes yield signatures consisting of 2 elements and requiring 1 PPE for verification. Our third scheme which signs a vector of size 2 yield (unilateral) signatures consisting of 3 elements from the shorter base group and require 1 PPE for verification. The verification overhead of our schemes also compares favourably to exiting schemes, in particular, when verifying multiple signatures on the same message vector, which is what a number of applications require.

Even when signing single messages, our first 2 schemes compare favourably in many measures, e.g. the key size and verification overhead, to the best existing scheme [29].

Paper Organization. We provide some preliminary definitions in Sect. 2. In Sect. 3 we give two new fully randomizable schemes for signing arbitrary vectors of messages. In Sect. 4 we give a scheme for signing a pair of messages. In Sect. 5 we compare the efficiency of our constructions with that of existing ones.

Notation. We write $y=A(x;r)$ when 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. We use [k] to denote the set $\{1,\ldots ,k\}$. We use capital letters for group elements and small letters for field elements.

2 Preliminaries

In this section we provide some preliminary definitions.

2.1 Bilinear Groups

A bilinear group is a tuple $\mathcal {P}:=(\mathbb {G}, {\mathbb {H}}, \mathbb {T}, p, G, \tilde{H}, e)$ where $\mathbb {G}$, ${\mathbb {H}}$ and $\mathbb {T}$ are groups of a prime order p, and G and $\tilde{H}$ generate $\mathbb {G}$ and ${\mathbb {H}}$, respectively. The function $e$ is a non-degenerate bilinear map $e: \mathbb {G}\times {\mathbb {H}}\longrightarrow \mathbb {T}$. For clarity, elements of ${\mathbb {H}}$ 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 ${\mathbb {H}}^\times := {\mathbb {H}}\setminus \{1_{{\mathbb {H}}}\}$. In this paper, we work in the efficient Type-3 setting [26], where $\mathbb {G}\ne {\mathbb {H}}$ and there is no efficiently computable homomorphism between the groups in either direction. We assume there is an algorithm $\mathcal {BG}$ that on input a security parameter $\kappa$, outputs a description of bilinear groups.

The message space of the schemes we consider is the set of elements of the subgroup $\widehat{\mathbb {GH}}$ of $\mathbb {G}\times {\mathbb {H}}$ defined as the image of the map $\psi : x \longmapsto (G^x, \tilde{H}^x)$ for $x \in \mathbb {Z}_p$. One can efficiently test whether $(M,\tilde{N}) \in \widehat{\mathbb {GH}}$ by checking

$$e(M,\tilde{H}) = e(G,\tilde{N})~\cdot $$

Such pairs were called Diffie-Hellman pairs in [3, 23]. An important observation here is that techniques used for batch verification, e.g. [12, 17], can be applied when verifying the well-formedness of a vector of Diffie-Hellman pairs. This reduces the cost for verifying a vector of $\ell$ pairs from $2\ell$ pairings to 2 pairings.

2.2 Digital Signatures

A digital signature scheme $\mathcal {DS}$ over a bilinear group $\mathcal {P}$ generated by $\mathcal {BG}$ for a message space $\mathcal {M}$ consists of the following algorithms:  

$\mathsf {KeyGen}(\mathcal {P})$ :

on input $\mathcal {P}$, it outputs a pair of secret/verification keys $(\mathsf {sk},\mathsf {vk})$.

$\mathsf {Sign}(\mathsf {sk}, m)$ :

on input $\mathsf {sk}$ and a message $m \in \mathcal {M}$, it outputs a signature $\sigma$.

$\mathsf {Verify}(\mathsf {vk}, m,\sigma )$ :

outputs 1 if $\sigma$ is a valid signature on m w.r.t. $\mathsf {vk}$ and 0 otherwise.

 

Besides the usual correctness requirement, we require existential unforgeability.

Definition 1

(Existential Unforgeability). A signature scheme $\mathcal {DS}$ over a bilinear group generator $\mathcal {BG}$ is Existentially-Unforgeable against adaptive Chosen-Message Attack (EUF-CMA) if for all $\kappa \in \mathbb {N}$ for all PPT adversaries $\mathcal {A}$, the following is negligible (in $\kappa$)

$$\Pr \left[ \begin{array}{l} \mathcal {P}\leftarrow \mathcal {BG}(1^\kappa ) ; (\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 \wedge m^* \notin Q_{\mathsf {Sign}} \end{array}\right] ,$$

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

Strong Existential Unforgeability against adaptive Chosen-Message Attack (sEUF-CMA) requires that the adversary cannot even output a new signature on a message that was queried to the sign oracle.

A weaker variant of EUF-CMA is Existential Unforgeability against a Random-Message Attack (EUF-RMA) in which the sign oracle samples a message uniformly from the message space and returns the message and a signature on it. In one-time signatures, the adversary is restricted to a single signing query.

We consider schemes which are publicly re-randomizable where there is an algorithm $\mathsf {Randomize}$ that on input $(\mathsf {vk},m,\sigma )$ outputs a new signature $\sigma ^\prime$ on m. A desirable property for such class of schemes is that randomized signatures are indistinguishable from fresh signatures.

Definition 2

(Randomizability). A signature scheme $\mathcal {DS}$ over a bilinear group generator $\mathcal {BG}$ is randomizable if for all $\kappa \in \mathbb {N}$ for all stateful adversaries $\mathcal {A}$ the following probability is negligibly close to $\frac{1}{2}$.

$$ \Pr \left[ \begin{array}{l} \mathcal {P}\leftarrow \mathcal {BG}(1^\kappa ); (\mathsf {sk},\mathsf {vk})\leftarrow \mathsf {KeyGen}(\mathcal {P}); (\sigma ^*,m^*)\leftarrow \mathcal {A}(\mathcal {P},\mathsf {sk},\mathsf {vk}); \sigma _0 \leftarrow \mathsf {Sign}(\mathsf {sk},m^*);\\ \sigma _1 \leftarrow \mathsf {Randomize}(\mathsf {vk},m^*,\sigma ^*);b \leftarrow \{0,1\} : \mathsf {Verify}(\mathsf {vk}, m^*,\sigma ^*)=1 \wedge \mathcal {A}(\sigma _b)=b \end{array}\right] $$

When the above is exactly $\frac{1}{2}$, we say the scheme has Perfect Randomizability.

2.3 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 from either or both base groups, and verifying signatures only involves deciding group membership of the signature components and evaluating PPEs of the form of Equation (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 {\mathbb {H}}$ are group elements appearing in $\mathcal {P}, m, \mathsf {vk}, \sigma$, whereas $c_{i,j}\in \mathbb {Z}_p$ are constants.

Generic Signer. We refer to a signer that can only decide group membership, evaluate the bilinear map $e$, compute the group operations in groups $\mathbb {G}, {\mathbb {H}}$ and $\mathbb {T}$, and compare group elements as a generic signer.

3 Constant-Size Schemes for Diffie-Hellman Vectors

In this section, we give 2 new schemes for signing a vector of Diffie-Hellman pairs.

3.1 Scheme I

Given the description of Type-3 bilinear groups $\mathcal {P}$ output by $\mathcal {BG}(1^\kappa )$, the scheme is as follows:

• $\mathsf {KeyGen}(\mathcal {P})$: Select $x_1,\ldots ,x_\ell ,y \leftarrow \mathbb {Z}_p$. Set $X_i:={G}^{x_i}$ for all $i \in [\ell ]$, $\tilde{Y} :=\tilde{H}^{y}$, $\mathsf {sk}:=(x_1,\ldots ,x_\ell ,y)$ and $\mathsf {vk}:=({X}_1,\ldots ,{X}_\ell ,\tilde{Y})\in \mathbb {G}^\ell \times {\mathbb {H}}$.

• $\mathsf {Sign}\left( \mathsf {sk},\left( (M_1,\tilde{N}_1), \ldots , (M_\ell ,\tilde{N}_\ell ) \right) \right)$: To sign $\left( (M_1,\tilde{N}_1), \ldots ,(M_\ell ,\tilde{N}_\ell ) \right) \in \widehat{\mathbb {GH}}^\ell$, select $r \leftarrow \mathbb {Z}_p$ and set $R:={G}^r$, and $\tilde{S} :=(\prod _{i=1}^{\ell } \tilde{N}_i^{x_i} \cdot \tilde{Y}^{x_1} \cdot \tilde{H})^{\frac{1}{r}}$. Return $\sigma :=(R,\tilde{S})\in \mathbb {G}\times {\mathbb {H}}$.

• $\mathsf {Verify}\left( \mathsf {vk},\left( (M_1,\tilde{N}_1), \ldots , (M_\ell ,\tilde{N}_\ell ) \right) ,\sigma =(R,\tilde{S})\right)$: Return 1 iff $R \in \mathbb {G}$, $\tilde{S} \in {\mathbb {H}}$, for all $i \in [\ell ]: (M_i,\tilde{N}_i) \in \widehat{\mathbb {GH}}$, and

  $$e(R, \tilde{S}) = \prod _{i=1}^{\ell }e( X_i ,\tilde{N}_i)e(X_1,\tilde{Y}) e(G, \tilde{H})~\cdot $$

• $\mathsf {Randomize}\left( \mathsf {vk},\left( (M_1,\tilde{N}_1), \ldots , (M_\ell ,\tilde{N}_\ell ) \right) ,\sigma =(R,\tilde{S})\right)$: Select $r' \leftarrow \mathbb {Z}_p$, and return $\sigma ':=(R^{r'},\tilde{S}^{\frac{1}{r'}})$.

Efficiency of the Scheme. The public key for signing a vector of size $\ell$ has size $\ell |\mathbb {G}| + |{\mathbb {H}}|$ whereas the signature is of size $|\mathbb {G}| + |{\mathbb {H}}|$ regardless of the size of the message vector. Thus, our signatures are shorter than all existing schemes since the best existing optimal schemes for unilateral messages, e.g. [4], have signatures of size $2|\mathbb {G}| + |{\mathbb {H}}|$. Assuming that the messages are already well-formed, verification requires only a single PPE with $\ell + 2$ pairings where 1 pairing, i.e. the pairing $e(G,\tilde{H})$ can be pre-computed. Hence, we only require $\ell + 1$ pairings for each signature after the first signature. If the messages are already assumed to be well-formed, this compares favourably to existing schemes since the most efficient existing scheme requires 2 PPE for verification. The scheme yields very short proofs of knowledge when combined with Groth-Sahai proofs [34] as one requires a proof for a linear (rather than quadratic) equation. As a result, our scheme outperforms the best existing scheme [29] in this respect. Refer to Sect. 5 for concrete efficiency comparison with existing schemes.

Security of the Scheme. The scheme is perfectly randomizable as the distribution of re-randomized signatures is identical to that of fresh signatures on the same vector. We now prove the following theorem.

Theorem 1

The scheme is EUF-CMA secure.

Proof

Correctness of the scheme follows by inspection and is straightforward to verify. The following two lemmata prove unforgeability of the scheme against adaptive chosen-message attacks. Lemma 1 proves that the case when $\ell =1$ is secure in the generic group model whereas Lemma 2 reduces any attack on the scheme when $\ell > 1$ to the case when $\ell =1$ which is proved by Lemma 1.

Lemma 1

The scheme for $\ell =1$ is EUF-CMA secure in the generic group model.

Proof

We proceed by proving that no linear combinations (which represent Laurent polynomials in the discrete logarithms) of the group elements the adversary sees in the game correspond to a forgery on a new message.

At the start of the game, the only elements in ${\mathbb {H}}$ the adversary sees are $\tilde{H}$, $\tilde{Y}$ which correspond to the discrete logarithms 1 and y, respectively. Also, at the start of the game the only elements in $\mathbb {G}$ the adversary sees are ${G}$, ${X}$ which correspond to the discrete logarithms 1 and x, respectively.

At the j-th sign query on the message $(M_j,\tilde{N}_j)$, $m_j$ and $n_j$ (the discrete logarithms of $M_j$ and $\tilde{N}_j$, respectively, can only be a linear combination of the discrete logarithms of the elements in $\mathbb {G}$ and ${\mathbb {H}}$, respectively, the adversary sees up to that point of time. Thus, we have

$$\begin{aligned} m_j&= a_{m_j} + b_{m_j} x + \sum \limits _{i=1}^{j-1} c_{m_j,i} r_i\\ n_j&= a_{n_j} + b_{n_j} y + \sum \limits _{i=1}^{j-1} c_{n_j,i} \frac{n_i x + xy + 1}{r_i} \end{aligned}$$

For the message to satisfy $(M_j,\tilde{N}_j)\in \widehat{\mathbb {GH}}$, we must have that $m_j=n_j$ and hence we must have that $a_{m_j}=a_{n_j}$, $b_{m_j}=b_{n_j}=0$ and for all i that $c_{m_j,i}=c_{n_j,i}=0$. This ensures that the message queried is nothing but a constant polynomial. If the message is well-formed¹, the sign oracle responds with a signature of the form

$$ \left( r_j, s_j=\frac{n_j x + x y + 1}{r_j}\right) $$

Since the adversary is generic, she can only construct $\left( (M^*,\tilde{N}^*),\sigma ^*=(R^*,\tilde{S}^*)\right)$ as a linear combination of the group elements she sees in the game. Thus, we have

$$\begin{aligned}&m^*= a_{m} + b_m x + \sum \limits _{i=1}^{q} c_{m,i} r_i&~~~~~&r^* = a_{r} + b_r x + \sum \limits _{i=1}^{q} c_{r,i} r_i \\&n^* = a_{n} + b_n y + \sum \limits _{i=1}^{q} c_{n,i} \frac{n_i x + xy + 1}{r_i}&~~~~~&s^*= a_{s} + b_s y + \sum \limits _{i=1}^{q} c_{s,i} \frac{n_i x + xy + 1}{r_i} \end{aligned}$$

Since the forged message $(M^*, \tilde{N}^*)$ must correspond to a Diffie-Hellman pair, we must have $m^*=n^*$ and thus $a_m=a_n$, $b_m=b_n=0$ and $c_{m,i}=c_{n,i}=0$ for all $i \in [q]$ and hence $m^*=n^*=a_m$. For the forgery to be accepted, $r^*$ and $s^*$ must satisfy $r^* s^* = n^* x + x y +1$. Therefore, we must have

$$\begin{aligned} \left( a_{r} + b_r x + \sum \limits _{i=1}^{q} c_{r,i} r_i \right) \left( a_{s} + b_s y + \sum \limits _{i=1}^{q} c_{s,i} \frac{n_i x + xy + 1}{r_i} \right) = n^* x + x y +1 \end{aligned}$$

Thus, we must have

$$\begin{aligned} a_{r}&a_{s} + a_{r} b_s y + \sum \limits _{i=1}^{q} a_{r}c_{s,i} \frac{n_i x + xy + 1}{r_i} \\ +&a_{s} b_r x + b_s b_r x y + \sum \limits _{i=1}^{q} b_r c_{s,i} \frac{n_i x^2 + x^2y + x}{r_i} \\ +&a_{s} \sum \limits _{i=1}^{q} c_{r,i} r_i + b_s y \sum \limits _{i=1}^{q} c_{r,i} r_i + \sum \limits _{i=1}^{q} c_{r,i} r_i \sum \limits _{i=1}^{q} c_{s,i} \frac{n_i x + xy + 1}{r_i} \\&~~~~~~ = n^* x + x y +1 \end{aligned}$$

There is no term in $\frac{xy}{r_i}$ or $\frac{x^2y}{r_i}$ on the RHS so we must have for all $i\in [q]$ that $a_r c_{s,i}=0$ and $b_r c_{s,i}=0$. This means that we either have that $c_{s,i}=0$ for all $i\in [q]$ or we have $a_r=b_r=0$.

• Case $a_r=b_r=0$: In this case we must have

  $$\begin{aligned} a_{s} \sum \limits _{i=1}^{q} c_{r,i} r_i + b_s y \sum \limits _{i=1}^{q} c_{r,i} r_i + \sum \limits _{i=1}^{q} c_{r,i} r_i \sum \limits _{i=1}^{q} c_{s,i} \frac{n_i x + xy + 1}{r_i}&= n^* x + x y +1 \end{aligned}$$

  There are no terms in $r_i$ or $r_i y$ on the RHS so we must have for all $i \in [q]$ that $a_s c_{r,i} =0$ and $b_s c_{r,i} =0$. This means that we either have that $c_{r,i}=0$ for all $i\in [q]$ or we have $a_s=b_s=0$. The former case cannot occur as otherwise the LHS will not have a term in xy and hence the equality will not hold. So we must have $a_s=b_s=0$ and hence we must have

  $$\begin{aligned} \sum \limits _{i=1}^{q} c_{r,i} r_i \sum \limits _{i=1}^{q} c_{s,i} \frac{n_i x + xy + 1}{r_i} = n^* x + xy +1 \end{aligned}$$

  There is no term on the RHS of the form $\frac{r_j x y}{r_i}$ for any $i,j \in [q]$ where $i \ne j$. Thus, we must have $c_{r,i}c_{s,j} =0$ for all $i \ne j$. This means we must have for some $i \in [q]$

  $$\begin{aligned} c_{r,i}c_{s,i} n_i x + c_{r,i}c_{s,i} x y + c_{r,i}c_{s,i} = n^* x + xy +1 \end{aligned}$$

  By the monomial xy, we must have $c_{r,i}c_{s,i}=1$ from which it is clear that the only way the equality will hold is if $n^*=n_i$ from some $i\in [q]$ which means the forgery is not valid as the signature is on a message that was queried to the sign oracle.

• Case $c_{s,i}=0$ for all $i\in [q]$: In this case we must have

  $$\begin{aligned} a_{r} a_{s} + a_{r} b_s y + a_{s} b_r x + b_s b_r x y + a_{s} \sum \limits _{i=1}^{q} c_{r,i} r_i + b_s y \sum \limits _{i=1}^{q} c_{r,i} r_i = n^* x + x y +1 \end{aligned}$$

  The only term on the LHS with the monomial xy is the term $b_s b_r xy$ thus for the equality to hold we must have that $b_s \ne 0$ and $b_r \ne 0$. There is no term on the RHS with the monomial $r_i y$ and since we cannot have $b_s=0$, we must have that $c_{r,i}=0$ for all $i \in [q]$, which means we have:

  $$\begin{aligned} a_{r} a_{s} + a_{r} b_s y + a_{s} b_r x + b_s b_r x y = n^* x + x y +1 \end{aligned}$$

  There is no term on the RHS wih the monomial y and since we cannot have $b_s=0$, we must have that $a_r=0$ which means we have:

  $$\begin{aligned} a_{s} b_r x + b_s b_r x y = n^* x + x y +1 \end{aligned}$$

  which cannot hold.

   $\square$

Lemma 2

The scheme for $\ell > 1$ is EUF-CMA secure.

Proof

We proceed by showing that any valid forgery in the case $\ell > 1$ can be reduced to a forgery for the case $\ell =1$.

Let $\mathcal {A}$ be a successful adversary in the $\ell >1$ case we show how to construct an adversary $\mathcal {B}$ who uses adversary $\mathcal {A}$ to break the scheme for the case $\ell =1$ which would contradict Lemma 1.

Adversary $\mathcal {B}$ gets $\mathsf {vk}'=({X}',\tilde{Y}')$ from her game where she has access to a sign oracle for a single Diffie-Hellman pair. She chooses $x_1,\ldots ,x_{\ell -1} \leftarrow \mathbb {Z}_p$ and sets $\tilde{Y} :=\tilde{Y}'$, ${X}_1 :=X'$ and ${X_i} :={X'}^{x_{i-1}}$ for $i=2,\ldots ,\ell$. She starts $\mathcal {A}$ on the verification key $\mathsf {vk}:=({X}_1,\ldots ,{X}_\ell ,\tilde{Y})$. Note that since $x_1,\ldots , x_{\ell -1}$ are chosen uniformly at random, the verification key $\mathsf {vk}$ $\mathcal {A}$ sees is indistinguishable from one she gets from the real signer. When receiving a query on $\mathbf {m}_i=\left( (M,\tilde{N})_{i,1}, \ldots , (M,\tilde{N})_{i,\ell } \right)$ from $\mathcal {A}$, $\mathcal {B}$ returns $\perp$ if $(M,\tilde{N})_{i,j} \notin \widehat{\mathbb {GH}}$ for any $j \in [\ell ]$. Otherwise, she forwards $(M'_i,\tilde{N}'_i):=\left( M_{i,1} \cdot \prod _{j=2}^{\ell }M_{i,j}^{x_{j-1}}, \tilde{N}_{i,1} \cdot \prod _{j=2}^{\ell } \tilde{N}_{i,j}^{x_{j-1}} \right) \in \widehat{\mathbb {GH}}$ to her sign oracle and returns the signature she gets to $\mathcal {A}$. Such a signature is a valid signature on the message $\mathbf {m}_i=\left( (M,\tilde{N})_{i,1}, \ldots , (M,\tilde{N})_{i,\ell } \right)$ w.r.t. the verification key $\mathsf {vk}=({X}_1,\ldots ,{X}_\ell ,\tilde{Y})$.

When $\mathcal {A}$ outputs her forgery $\sigma ^*$ on $\mathbf {m}^*=\left( (M^*,\tilde{N}^*)_{1}, \ldots , (M^*,\tilde{N}^*)_{\ell } \right)$, $\mathcal {B}$ returns $(M',\tilde{N}'):=\left( M_{1}^* \cdot \prod _{j=2}^{\ell } {M_j^*}^{x_{j-1}}, {\tilde{N_1^*}} \cdot \prod _{j=2}^{\ell } {\tilde{N_j^*}}^{{x_{j-1}} } \right) \in \widehat{\mathbb {GH}}$ and $\sigma ^*$ as the answer in her game. Thus, $\mathcal {B}$ wins her game with the same advantage as that of $\mathcal {A}$ in her game.    $\square$

3.2 Scheme II

We show here that by transposing the signature components of Scheme I, we obtain a scheme with signatures $(S,\tilde{R})\in \mathbb {G}\times {\mathbb {H}}$ where $\tilde{R}$ is information-theoretically independent of the message vector. The verification key matches that of Scheme I, i.e. the verification key size is $\ell |\mathbb {G}| + |{\mathbb {H}}|$. Note that the scheme has the property that signing requires only the $\mathbb {G}$ components of the messages whereas verification requires, besides verifying well-formedness of the messages, only the ${\mathbb {H}}$ components of the messages. We remark that existing schemes with similar properties have found various applications, see e.g. [13, 28].

Given the description of Type-3 bilinear groups $\mathcal {P}$ output by $\mathcal {BG}(1^\kappa )$, the scheme is as follows:

• $\mathsf {KeyGen}(\mathcal {P})$: Select $x_1,\ldots ,x_\ell ,y \leftarrow \mathbb {Z}_p$. Set $X_i:={G}^{x_i}$ for all $i \in [\ell ]$, $\tilde{Y} :=\tilde{H}^{y}$, $\mathsf {sk}:=(x_1,\ldots ,x_\ell ,y)$, and $\mathsf {vk}:=({X}_1,\ldots ,{X}_\ell ,\tilde{Y})\in \mathbb {G}^\ell \times {\mathbb {H}}$.

• $\mathsf {Sign}\left( \mathsf {sk},\left( (M_1,\tilde{N}_1), \ldots , (M_\ell ,\tilde{N}_\ell ) \right) \right)$: To sign $\left( (M_1,\tilde{N}_1), \ldots , (M_\ell ,\tilde{N}_\ell ) \right) \in \widehat{\mathbb {GH}}^\ell$, select $r \leftarrow \mathbb {Z}_p$ and set $\tilde{R}:=\tilde{H}^r$, and $S :=(\prod _{i=1}^{\ell } M_i^{x_i} \cdot X_1^y \cdot G )^{\frac{1}{r}}$. Return $\sigma :=(\tilde{R},S)\in {\mathbb {H}}\times \mathbb {G}$.

• $\mathsf {Verify}\left( \mathsf {vk},\left( (M_1,\tilde{N}_1), \ldots , (M_\ell ,\tilde{N}_\ell ) \right) ,\sigma =(\tilde{R},S)\right)$: Return 1 iff $\tilde{R} \in {\mathbb {H}}$, $S \in \mathbb {G}$, for all $i \in [\ell ]: (M_i,\tilde{N}_i) \in \widehat{\mathbb {GH}}$, and

  $$e(S, \tilde{R}) = \prod _{i=1}^{\ell }e( X_i ,\tilde{N}_i)e(X_1,\tilde{Y}) e(G, \tilde{H})~\cdot $$

• $\mathsf {Randomize}\left( \mathsf {vk},\left( (M_1,\tilde{N}_1), \ldots , (M_\ell ,\tilde{N}_\ell ) \right) ,\sigma =(\tilde{R},S)\right)$: Select $r' \leftarrow \mathbb {Z}_p$, and return $\sigma ':=(\tilde{R}^{r'},S^{\frac{1}{r'}})$.

The scheme has identical efficiency as that of Scheme I.

Security of the Scheme. The scheme is perfectly randomizable as the distribution of re-randomized signatures is identical to that of fresh signatures on the same vector.

Theorem 2

The scheme is EUF-CMA secure.

Proof

Correctness of the scheme follows by inspection and is straightforward to verify. The following two lemmata prove unforgeability of the scheme against adaptive chosen-message attacks. Lemma 3 proves that the case when $\ell =1$ is secure in the generic group model whereas Lemma 4 reduces any attack on the scheme when $\ell >1$ to the case when $\ell =1$ which is proved by Lemma 3.

Lemma 3

The scheme for $\ell =1$ is EUF-CMA secure in the generic group model.

Proof

We proceed by proving that no linear combinations (which represent Laurent polynomials in the discrete logarithms) of the group elements the adversary sees in the game correspond to a forgery on a new message.

At the start of the game, the only elements in ${\mathbb {H}}$ the adversary sees are $\tilde{H}$, $\tilde{Y}$ which correspond to the discrete logarithms 1 and y, respectively. Also, at the start of the game the only elements in $\mathbb {G}$ the adversary sees are ${G}$, ${X}$ which correspond to the discrete logarithms 1 and x, respectively.

At the j-th query on message $(M_j,\tilde{N}_j)$, $m_j$ and $n_j$ which are the discrete logarithm of the message can only be a linear combination of the elements in the respective groups so far. Thus, we have

$$\begin{aligned} m_j&= a_{m_j} + b_{m_j} x + \sum \limits _{i=1}^{j-1} c_{m_j,i} \frac{m_i x + x y + 1}{r_i} \\ n_j&= a_{n_j} + b_{n_j} y + \sum \limits _{i=1}^{j-1} c_{n_j,i} r_i \end{aligned}$$

For the message to satisfy $(M_j,\tilde{N}_j)\in \widehat{\mathbb {GH}}$, we must have that $m_j=n_j$ and hence we must have that $a_{m_j}=a_{n_j}$, $b_{m_j}=b_{n_j}=0$ and for all i that $c_{m_j,i}=c_{n_j,i}=0$. This ensures that the message queried is nothing but a constant polynomial.

If the message is well-formed, the sign oracle responds with a signature of the form

$$ \left( r_j, s_j=\frac{m_j x + x y + 1}{r_j}\right) $$

Since the adversary is generic, she can only construct $(M^*,\tilde{N^*})$ and $\sigma ^*=(\tilde{R^*},S^*)$ as a linear combination of the group elements she sees in the game. Thus, we must have

$$\begin{aligned}&m^*= a_{m} + b_m x + \sum \limits _{i=1}^{q} c_{m,i} \frac{m_i x + xy + 1}{r_i}&~~~~~~&r^* = a_{r} + b_r y + \sum \limits _{i=1}^{q} c_{r,i} r_i \\&n^* = a_{n} + b_n y + \sum \limits _{i=1}^{q} c_{n,i} r_i&~~~~~~~&s^*= a_{s} + b_s x + \sum \limits _{i=1}^{q} c_{s,i} \frac{m_i x + xy + 1}{r_i} \end{aligned}$$

Since the forged message $(M^*, \tilde{N}^*)$ must correspond to a Diffie-Hellman pair, we must have $m^*=n^*$ and thus $a_m=a_n$, $b_m=b_n=0$ and $c_{m,i}=c_{n,i}=0$ for all $i \in [q]$ and hence $m^*=n^*=a_m$. For the forgery to be accepted, $r^*$ and $s^*$ must satisfy $s^* r^* = m^* x + xy +1$. Therefore, we must have

$$\begin{aligned} \left( a_{r} + b_r y + \sum \limits _{i=1}^{q} c_{r,i} r_i \right) \left( a_{s} + b_s x + \sum \limits _{i=1}^{q} c_{s,i} \frac{m_i x + xy + 1}{r_i} \right) = m^* x + xy +1 \end{aligned}$$

Thus, we must have

$$\begin{aligned} ~~~~&a_{r} a_{s} + a_{r} b_s x + \sum \limits _{i=1}^{q} a_{r}c_{s,i} \frac{m_i x + xy + 1}{r_i} \\ ~~~~&+ a_{s} b_r y + b_s b_r x y + \sum \limits _{i=1}^{q} b_r c_{s,i} \frac{m_i x y + x y^2 + y}{r_i} \\ ~~~~&+ a_{s} \sum \limits _{i=1}^{q} c_{r,i} r_i + b_s x \sum \limits _{i=1}^{q} c_{r,i} r_i + \sum \limits _{i=1}^{q} c_{r,i} r_i \sum \limits _{i=1}^{q} c_{s,i} \frac{m_i x + xy + 1}{r_i} \\&~~~~~~ = m^* x + xy +1 \end{aligned}$$

There is no term in $\frac{xy}{r_i}$ or $\frac{xy^2}{r_i}$ on the RHS so we must have for all $i\in [q]$ that $a_r c_{s,i}=0$ and $b_r c_{s,i}=0$. This means that we either have that $c_{s,i}=0$ for all $i\in [q]$ or we have $a_r=b_r=0$.

• Case $a_r=b_r=0$: Here we must have

  $$\begin{aligned} a_{s} \sum \limits _{i=1}^{q} c_{r,i} r_i + b_s x \sum \limits _{i=1}^{q} c_{r,i} r_i + \sum \limits _{i=1}^{q} c_{r,i} r_i \sum \limits _{i=1}^{q} c_{s,i} \frac{m_i x + xy + 1}{r_i}&= m^* x + xy +1 \end{aligned}$$

  There is no terms in $r_i$ or $r_i x$ on the RHS so we must have for all $i \in [q]$ that $a_s c_{r,i} =0$ and $b_s c_{r,i} =0$. This means that we either have that $c_{r,i}=0$ for all $i\in [q]$ or we have $a_s=b_s=0$. The former case cannot occur as otherwise the LHS will not have a term in xy and hence the equality will not hold. So we must have $a_s=b_s=0$ and hence we have

  $$\begin{aligned} \sum \limits _{i=1}^{q} c_{r,i} r_i \sum \limits _{i=1}^{q} c_{s,i} \frac{m_i x + xy + 1}{r_i} = m^* x + xy +1 \end{aligned}$$

  There is no term on the RHS of the form $\frac{r_j x y}{r_i}$ for any $i,j \in [q]$ where $i \ne j$. Thus, we must have $c_{r,i}c_{s,i} =0$ if $i \ne j$. This means we have

  $$\begin{aligned} c_{r,i}c_{s,i} m_i x + c_{r,i}c_{s,i} x y + c_{r,i}c_{s,i} = m^* x + xy +1 \end{aligned}$$

  By the monomial xy, we must have $c_{r,i}c_{s,i}=1$ from which it is clear that the only way the equality will hold is if $m^*=m_i$ from some $i\in [q]$ which means the forgery is not valid as the signature is on a message that was queried to the sign oracle.

• Case $c_{s,i}=0$ for all $i\in [q]$:

  Thus, we must have

  $$\begin{aligned} a_{r} a_{s} + a_{r} b_s x + a_{s} b_r y + b_s b_r x y + a_{s} \sum \limits _{i=1}^{q} c_{r,i} r_i + b_s x \sum \limits _{i=1}^{q} c_{r,i} r_i = m^* x + xy +1 \end{aligned}$$

  The only term on the LHS with the monomial xy is the term $b_s b_r x y$ thus for the equality to hold we must have that $b_s \ne 0$ and $b_r \ne 0$. There is no term on the RHS with the monomial $r_i x$ and since we cannot have $b_s=0$, we must have that $c_{r,i}=0$ for all $i \in [q]$, which means we have:

  $$\begin{aligned} a_{r} a_{s} + a_{r} b_s x + a_{s} b_r y + b_s b_r x y = m^* x + xy +1 \end{aligned}$$

  There is no term on the RHS wih the monomial y and since we cannot have $b_r=0$, we must have that $a_s=0$ which means we have:

  $$\begin{aligned} a_{r} b_s x + b_s b_r x y = m^* x + xy +1 \end{aligned}$$

  which cannot hold.

   $\square$

Lemma 4

The scheme for $\ell > 1$ is EUF-CMA secure.

Proof

We proceed by showing that any valid forgery in the case $\ell > 1$ can be reduced to a forgery for the case $\ell =1$.

Let $\mathcal {A}$ be a successful adversary in the $\ell >1$ case we show how to construct an adversary $\mathcal {B}$ who uses adversary $\mathcal {A}$ to break the scheme for the case $\ell =1$ which would contradict Lemma .

Adversary $\mathcal {B}$ gets $\mathsf {vk}'=({X}',\tilde{Y}')$ from her game where she has access to a sign oracle for a single Diffie-Hellman pair. She chooses $x_1,\ldots ,x_{\ell -1} \leftarrow \mathbb {Z}_p$ and sets $\tilde{Y} :=\tilde{Y}'$, ${X}_1 :=X'$ and ${X_i} :={X'}^{x_{i-1}}$ for $i=2,\ldots ,\ell$. She starts $\mathcal {A}$ on the verification key $\mathsf {vk}:=({X}_1,\ldots ,{X}_\ell ,\tilde{Y})$. Note that since $x_1,\ldots , x_{\ell -1}$ are chosen uniformly at random, the verification key $\mathsf {vk}$ $\mathcal {A}$ sees is indistinguishable from one she gets from the real signer. When receiving a query on $\mathbf {m}_i=\left( (M,\tilde{N})_{i,1}, \ldots , (M,\tilde{N})_{i,\ell } \right)$ from $\mathcal {A}$, $\mathcal {B}$ returns $\perp$ if $(M,\tilde{N})_{i,j} \notin \widehat{\mathbb {GH}}$ for any $j \in [\ell ]$. Otherwise, she forwards $(M'_i,\tilde{N}'_i):=\left( M_{i,1} \cdot \prod _{j=2}^{\ell }M_{i,j}^{x_{j-1}}, \tilde{N}_{i,1} \cdot \prod _{j=2}^{\ell } \tilde{N}_{i,j}^{x_{j-1}} \right) \in \widehat{\mathbb {GH}}$ to her sign oracle and returns the signature she gets to $\mathcal {A}$. Such a signature is a valid signature on the message $\mathbf {m}_i=\left( (M,\tilde{N})_{i,1}, \ldots , (M,\tilde{N})_{i,\ell } \right)$ w.r.t. the verification key $\mathsf {vk}=({X}_1,\ldots ,{X}_\ell ,\tilde{Y})$.

When $\mathcal {A}$ outputs her forgery $\sigma ^*$ on $\mathbf {m}^*=\left( (M^*,\tilde{N^*})_{1}, \ldots , (M^*,\tilde{N^*})_{\ell } \right)$, $\mathcal {B}$ returns $(M',\tilde{N}'):=\left( M_1^* \cdot \prod _{j=2}^{\ell } {M_j^*}^{{x_{j-1}}}, {\tilde{N_1^*}} \cdot \prod _{j=2}^{\ell } {\tilde{N_j^*}}^{x_{j-1} } \right) \in \widehat{\mathbb {GH}}$ and $\sigma ^*$ as the answer in her game. Thus, $\mathcal {B}$ wins her game with the same advantage as that of $\mathcal {A}$ in her game.    $\square$

4 Unilateral Scheme for 2 Diffie-Hellman Pairs

We give here a scheme for 2 pairs of Diffie-Hellman messages yielding unilateral signatures of size $3|\mathbb {G}|$. The scheme is an extension of the recent single-message scheme from [29] where we use different randomness for each message. Signatures of this scheme are still shorter than those of all existing optimal Type-3 schemes since the latter require that at least one of the components of $\sigma$ is from the second base group. The scheme is also more efficient than the single-message scheme from [28]. The verification key of the scheme is of size $3|{\mathbb {H}}|$, whereas verification of signatures require 1 PPE and 3 pairings, excluding the cost for verifying well-formedness of the messages. Given the description of Type-3 bilinear groups $\mathcal {P}$ output by $\mathcal {BG}(1^\kappa )$, the scheme is as follows:

• $\mathsf {KeyGen}(\mathcal {P})$: Select $x_1,x_2,y \leftarrow \mathbb {Z}_p$. Set $\mathsf {sk}:=(x_1,x_2,y)$ and $\mathsf {vk}:=(\tilde{X}_1,\tilde{X}_2,\tilde{Y}) :=(\tilde{H}^{x_1},\tilde{H}^{x_2}, \tilde{H}^{y}) \in {\mathbb {H}}^3$.

• $\mathsf {Sign}\left( \mathsf {sk},\left( (M_1,\tilde{N}_1), (M_2,\tilde{N}_2) \right) \right)$: To sign $\left( (M_1,\tilde{N}_1), (M_2,\tilde{N}_2) \right) \in \widehat{\mathbb {GH}}^2$, select $r_1,r_2 \leftarrow \mathbb {Z}_p$, set $R_1:=G^{r_1}$, $R_2:=G^{r_2}$, $S :=\left( \left( G^{x_1} \cdot M_1 \right) ^{r_1} \cdot \left( G^{x_2} \cdot M_2 \right) ^{r_2} \right) ^{\frac{1}{y}}$. Return $\sigma :=(R_1,R_2,S)\in \mathbb {G}^3$.

• $\mathsf {Verify}\left( \mathsf {vk},\left( (M_1,\tilde{N}_1), (M_2,\tilde{N}_2) \right) ,\sigma =(R_1,R_2,S)\right)$: Return 1 iff $R_1 \in \mathbb {G}^\times$, $R_2,S \in \mathbb {G}$, $\left( (M_1,\tilde{N}_1), (M_2,\tilde{N}_2) \right) \in \widehat{\mathbb {GH}}^2$ and

  $$e(S, \tilde{Y}) = e(R_1, \tilde{X_1} \cdot \tilde{N}_1) e(R_2, \tilde{X_2} \cdot \tilde{N}_2)~\cdot $$

• $\mathsf {Randomize}\left( \mathsf {vk},\left( (M_1,\tilde{N}_1), (M_2,\tilde{N}_2) \right) ,\sigma =(R_1,R_2,S) \right)$: Select $r^\prime \leftarrow \mathbb {Z}^\times _p$, and set $R_1^\prime :=R_1^{r^\prime }$, $R_2^\prime :=R_2^{r^\prime }$ , $S^\prime :=S^{r^\prime }$. Return $\sigma ^\prime :=(R_1^\prime , R_2^\prime ,S^\prime )$.

Correctness of the scheme follows by inspection and is straightforward to verify. We remark here that the signer will always be able to link a randomized signature to the original signature from which it was obtained even if we additionally require that $R_2 \ne 1_{\mathbb {G}}$. For instance, the malicious signer can choose $r_2=-r_1$ which will make all randomized versions of the signature in question satisfy ${R^\prime _1}\cdot R^\prime _{2}=1_\mathbb {G}$. Another way the signer can link a randomized signature to its original signature is by using knowledge of the exponents $r_1$ and $r_2$ since we will always have that ${R^\prime _1}^{\frac{1}{r_1}} = {R^\prime _2}^\frac{1}{r_2}$.

We now prove the following theorem.

Theorem 3

The scheme is EUF-CMA secure in the generic group model.

Proof

Public elements in ${\mathbb {H}}$ are $\tilde{H}$, $\tilde{X}_1$,$\tilde{X}_2$, and $\tilde{Y}$ which correspond to the discrete logarithms 1, $x_1$, $x_2$, and y, respectively. At the i-th signing query, we have that $\left( (m_{i,1},n_{i,1}), (m_{i,2},n_{i,2}) \right)$, which are the discrete logarithms of the queried message $\left( ( M_{i,1}, \tilde{N}_{i,1}), ( M_{i,2}, \tilde{N}_{i,2}) \right)$, must be of the form

$$\begin{aligned} n_{i,k}&= a_{_{n_{i,k}}} + b_{_{n_{i,k}}} x_1 + c_{_{n_{i,k}}} x_2 + d_{_{n_{i,k}}} y ~\\ m_{i,k}&= a_{_{m_{i,k}}} + \sum _{j=1}^{i-1} b_{_{{m_{i,k,j}}}} {r_1}_{_j} + \sum _{j=1}^{i-1} c_{_{m_{i,k,j}}} {r_2}_{_j} + \sum \limits _{j=1}^{i-1} d_{_{m_{i,k,j}}} \frac{{r_1}_{_j} {m_1}_{_j} + {{r_1}_{_j} x_1} + {{r_2}_{_j} {m_2}_{_j}} + {r_2}_{_j} x_2}{y}, \end{aligned}$$

for $k=1,2$. Since we must have $m_{i,1} = n_{i,1}$ and $m_{i,1} = n_{i,2}$ for the messages to be valid, we have $m_{i,1}= n_{i,1} = a_{_{m_{i,1}}} = a_{_{n_{i,1}}}$ and $m_{i,2}= n_{i,2} = a_{_{m_{i,2}}} = a_{_{n_{i,2}}}$, i.e. the messages queried to the signing oracle correspond to constant polynomials. Note that the sign oracle does not produce any elements in ${\mathbb {H}}$.

After q signing queries, $\left( (m_1^*,n_1^*), (m_2^*,n_2^*) \right)$, which are the discrete logarithms of the forged Diffie-Hellman pairs $\left( ( M_1^*, \tilde{N}_1^*), ( M_2^*, \tilde{N}_2^*) \right)$, must be of the form

$$\begin{aligned} n_k^*&= a_{_{n_k}} + b_{_{n_k}} x_1 + c_{_{n_k}} x_2 + d_{_{n_k}} y ~\\ m_k^*&= a_{_{m_k}} + \sum _{i=1}^{q} b_{_{{m_{k,i}}}} {r_1}_{_i} + \sum _{i=1}^{q} c_{_{{m_{k,i}}}} {r_2}_{_i} + \sum \limits _{i=1}^{q} d_{_{m_{k,i}}} \frac{{r_1}_{_i} {m_1}_{_i} + {r_1}_{_i} x_1 + {r_2}_{_i} {m_2}_{_i} + {r_2}_{_i} x_2}{y}, \end{aligned}$$

for $k=1,2$. Since we must have $m_1^* = n_1^*$ and $m_2^* = n_2^*$ for the forgery to be a valid element of $\widehat{\mathbb {GH}}^2$, we have $m_1^*= n_1^* = a_{_{m_1}} = a_{_{n_1}}$ and $m_2^*= n_2^* = a_{_{m_2}} = a_{_{n_2}}$. Similarly, the signature $(R_1^*, R_2^*,S^*)$ has the form

$$\begin{aligned} r_1^*&= a_{_{r_1}} + \sum _{i=1}^{q} b_{_{{r_{1,i}}}} {r_1}_{_i} + \sum _{i=1}^{q} c_{_{{r_{1,i}}}} {r_2}_{_i} + \sum \limits _{i=1}^{q} d_{_{r_{1,i}}} \frac{{r_1}_{_i} {m_1}_{_i} + {{r_1}_{_i} x_1}+ {{r_2}_{_i} {m_2}_{_i}} + {r_2}_{_i} x_2}{y}\\ r_2^*&= a_{_{r_2}} + \sum _{i=1}^{q} b_{_{{r_{2,i}}}} {r_1}_{_i} + \sum _{i=1}^{q} c_{_{{r_{2,i}}}} {r_2}_{_i} + \sum \limits _{i=1}^{q} d_{_{r_{2,i}}} \frac{{r_1}_{_i} {m_1}_{_i} + {{r_1}_{_i} x_1} + {{r_2}_{_i} {m_2}_{_i}} + {r_2}_{_i} x_2}{y}\\ s^*&= a_{_{s}} + \sum _{i=1}^{q} b_{_{{s},i}} {r_1}_{_i} + \sum _{i=1}^{q} c_{_{{s},i}} {r_2}_{_i} + \sum \limits _{i=1}^{q} d_{_{s,i}} \frac{{r_1}_{_i} {m_1}_{_i} + {{r_1}_{_i} x_1} + {{r_2}_{_i} {m_2}_{_i}} + {r_2}_{_i} x_2}{y} \end{aligned}$$

For the forgery to be a valid signature, $(r_1^*,r_2^*,s^*)$ must satisfy $s^* y = r_1^* m_1^* + r_1^* x_1 + r_2^* m_2^* + r_2^* x_2$. So we must have

$$\begin{aligned} \Big (&a_{_{s}} + \sum _{i=1}^{q} b_{_{{s},i}} {r_1}_{_i} + \sum _{i=1}^{q} c_{_{{s},i}} {r_2}_{_i} + \sum \limits _{i=1}^{q} d_{_{s,i}} \frac{{r_1}_{_i} {m_1}_{_i} + {{r_1}_{_i} x_1} + {{r_2}_{_i} {m_2}_{_i}} + {r_2}_{_i} x_2}{y} \Big ) y \\ =&\left( a_{_{r_1}} + \sum _{i=1}^{q} b_{_{{r_{1,i}}}} {r_1}_{_i} + \sum _{i=1}^{q} c_{_{{r_{1,i}}}} {r_2}_{_i} + \sum \limits _{i=1}^{q} d_{_{r_{1,i}}} \frac{{r_1}_{_i} {m_1}_{_i} + {{r_1}_{_i} x_1}+ {{r_2}_{_i} {m_2}_{_i}} + {r_2}_{_i} x_2}{y} \right) (x_1+m^*_1) \\&+ \left( a_{_{r_2}} + \sum _{i=1}^{q} b_{_{{r_{2,i}}}} {r_1}_{_i} + \sum _{i=1}^{q} c_{_{{r_{2,i}}}} {r_2}_{_i} + \sum \limits _{i=1}^{q} d_{_{r_{2,i}}} \frac{{r_1}_{_i} {m_1}_{_i} + {{r_1}_{_i} x_1} + {{r_2}_{_i} {m_2}_{_i}} + {r_2}_{_i} x_2}{y} \right) (x_2+m^*_2) \end{aligned}$$

There is no term in y, ${r_1}_{_i} y$ or ${r_2}_{_i} y$ on the RHS so we must have $a_{_{s}}=0$ and $b_{_{{s},i}}=c_{_{{s},i}}=0$ for all i.

Also, there are no terms in $x_1$, $x_2$, ${r_1}_{_i} x_2$, ${r_2}_{_i} x_1$, $\frac{{r_1}_{_i}x^2_1}{y}$, or $\frac{{r_2}_{_i} x^2_2}{y}$ on the LHS so we must have $a_{_{r_1}}=a_{_{r_2}}=0$ and $c_{_{{r_{1,i}}}}=b_{_{{r_{2,i}}}}=d_{_{r_{1,i}}}=d_{_{r_{2,i}}}$ for all i. Thus, we have

$$\begin{aligned} \sum \limits _{i=1}^{q} d_{_{s,i}}&( {{r_1}_{_i} {m_1}_{_i}} + {{r_1}_{_i} x_1} + {{r_2}_{_i} {m_2}_{_i}} + {{r_2}_{_i} x_2}) \\ =&\sum _{i=1}^{q} b_{_{{r_1},i}} {r_1}_{_i} m_1^* + \sum _{i=1}^{q} b_{_{{r_1},i}} {r_1}_{_i} x_1 + \sum _{i=1}^{q} c_{_{{r_2},i}} {r_2}_{_i} m^*_2 + \sum _{i=1}^{q} c_{_{{r_2},i}} {r_1}_{_i} x_2 \end{aligned}$$

Since we must have $r^*_1 \ne 0$, it follows that we must have at least for one value of i that $b_{_{{r_1},i}}\ne 0$. By the monomial ${r_1}_{_i} x_1$, we have $b_{_{{r_1},i}}= d_{_{s,i}}$. Since $d_{_{s,i}} \ne 0$, we also have that $c_{_{{r_2},i}}= d_{_{s,i}}$. Now by the monomial ${r_1}_{_i}$, we have that $b_{_{{r_1},i}} m^*_1= d_{_{{s},i}} {m_1}_{_i}$ from which it follows that $m^*_1 ={m_1}_{_i}$. Similarly, by the monomial ${r_2}_{_i}$, we have that $c_{_{{r_2},i}} m^*_2= d_{_{{s},i}} {m_2}_{_i}$ from which it follows that $m^*_2 ={m_2}_{_i}$. Thus, the forgery is on a message pair that was queried to the oracle.    $\square$

5 Efficiency Comparison

We compare in Table 1 the efficiency of our schemes with that of existing ones.

Table 1. Efficiency comparison between our schemes and existing Type-3 schemes

In the table numbers superscripted with $\dagger$ are the number of pairings that can be precomputed, whereas numbers superscripted with $*$ are the cost needed to verify well-formedness of the Diffie-Hellman message. The latter cost is constant when verifying multiple signatures on the same message. Also, as mentioned earlier, one can use techniques from batch verification, e.g. [12, 17], to reduce the cost required for verifying the well-formedness of a vector of $\ell$ Diffie-Hellman pairs to a single PPE and 2 pairings. For our schemes, we give 2 estimations for the efficiency overhead where the first is for the case where no batch verification is applied to verifying the well-formedness of the messages, whereas the second cost is when batch verification is applied in that respect. For all schemes listed, public parameters PP do not include the default group generators. Note that the security of all schemes in the table except for [3] which rely on non-interactive q-type assumptions is proven in the generic group model. For the cost of verification, we give two estimations which are for verifying 1 and n different signatures on the same message vector.

As can be seen from the table, our schemes outperform existing schemes w.r.t signature size. The size of the verification key of our schemes matches the best existing scheme. Also, the verification cost compares favourably especially when verifying various signatures on the same message vector which is the case for many applications, e.g. when the user is required to prove possession of various credentials/attributes from an authority or possibly different authorities.

5.1 Efficiency in the Single Message Setting

The best existing scheme in terms of signature size and verification overhead is the one recently given in [29] which has signatures of size $2|\mathbb {G}|$ and verification key of size $2|{\mathbb {H}}|$. When used on their own, the scheme in [29] has slightly shorter signatures than ours, whereas schemes I and II of ours have shorter verification key. In fact, the combined size of signatures and verification key in the 3 schemes are identical. Note that the scheme in [29] has the slight non-standard requirement that one needs to check that a signature component (which is information-theoretically independent of the message) is not the trivial element and hence in the case that one needs to commit to that signature component, one needs more expensive alternatives to prove that it conforms to the requirement, which is not the case in our schemes. Let’s now compare the verification overhead when verifying n signatures on the same message. Ignoring the cost of checking that $(M,\tilde{N})\in \widehat{\mathbb {GH}}$, the scheme in [29] would require 2n pairings, whereas schemes I and II of ours require only $n + 2$ pairings where one of the pairings, i.e. $e(G,\tilde{H})$ can be pre-computed and used for signatures on other messages, i.e. the cost drops to only $n+1$ pairings after verifying signatures on the first message. Thus, it is obvious that ours have less computational overhead when verifying multiple signatures on the same message.

Let’s now compare the performance of Scheme I of ours and the one in [29] when combined with Groth-Sahai [34] to prove knowledge of a signature on a committed message. We consider the most efficient instantiation of the proofs which relies on the SXDH assumption as noted by [30]. The scheme from [29] has signatures of the form $(R,S)\in \mathbb {G}^2$ and a verification key of the form $(\tilde{X},\tilde{Y}) \in {\mathbb {H}}^2$, and verification requires checking that $(M,\tilde{N})\in \widehat{\mathbb {GH}}$, $R \ne 1_\mathbb {G}$, and evaluating the following PPE:

$$\begin{aligned} e(S,\tilde{Y})= e(R,\tilde{X} \cdot \tilde{N}) \end{aligned}$$

(2)

In the terminology of [34], Equation (2) is a quadratic PPE. When proving knowledge of a signature, one has to commit to M, $\tilde{N}$ and S and thus we need to produce a proof for the satisfiability of (2) as well as the quadratic PPE $e(G,\tilde{N})=e(M,\tilde{H})$ to prove that $(M,\tilde{N})\in \widehat{\mathbb {GH}}$. The total size of the Groth-Sahai commitments is $4|\mathbb {G}|+ 2|{\mathbb {H}}|$, whereas the size of the proof for each of the above equations is $4|\mathbb {G}|+ 4|{\mathbb {H}}|$. Thus, the total size of the witness indistinguishable Groth-Sahai proof of knowledge is $12|\mathbb {G}|+ 10|{\mathbb {H}}|$.

Scheme I of ours has signatures of the form $(R,\tilde{S})\in \mathbb {G}\times {\mathbb {H}}$ and a verification key of the form $(X,\tilde{Y}) \in \mathbb {G}\times {\mathbb {H}}$, and verification requires checking that $(M,\tilde{N})\in \widehat{\mathbb {GH}}$ and evaluating the following PPE:

$$\begin{aligned} e(R,\tilde{S})= e(X,\tilde{N} \cdot \tilde{Y}) e(G,H) \end{aligned}$$

(3)

When proving knowledge, we need to commit to M, $\tilde{N}$ and $\tilde{S}$ and thus we need to produce a proof for the satisfiability of (3), which is a linear PPE since components of the witness are all from the same group, as well as the quadratic PPE to prove that $(M,\tilde{N})\in \widehat{\mathbb {GH}}$. The total size of the Groth-Sahai commitments is $2|\mathbb {G}|+ 4|{\mathbb {H}}|$. The size of the proof for (3) is $2|\mathbb {G}|$ whereas proving $(M,\tilde{N})\in \widehat{\mathbb {GH}}$ requires a proof of size $4|\mathbb {G}|+ 4|{\mathbb {H}}|$. Thus, the total size of the witness indistinguishable Groth-Sahai proof of knowledge is $8|\mathbb {G}|+ 8|{\mathbb {H}}|$. From the above, it is obvious when proving knowledge of signatures using Groth-Sahai proofs, which was the main motivation behind introducing the structure-preserving signatures notion, and which is required for the vast majority of applications of the notion, e.g. group, blind, attribute-based signatures, e-cash, etc., our scheme outperforms the best existing scheme. The efficiency gain has implication for various applications.