{'fraction_non_alphanumeric': 0.048827015179803555, 'fraction_numerical': 0.013069242633330628, 'mean_word_length': 4.128850957535387, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Further Lower Bounds for Structure-Preserving Signatures in Asymmetric Bilinear Groups

Structure-Preserving Signatures (SPSs) are a useful tool for the design of modular cryptographic protocols. Recent series of works have shown that by limiting the message space of those schemes to the set of Diffie-Hellman (DH) pairs, it is possible to circumvent the known lower bounds in the Type-3 bilinear group setting thus obtaining the shortest signatures consisting of only 2 elements from the shorter source group. It has been shown that such a variant yields efficiency gains for some cryptographic constructions, including attribute-based signatures and direct anonymous attestation. Only the cases of signing a single DH pair or a DH pair and a vector from Zp have been considered. Signing a vector of group elements is required for various applications of SPSs, especially if the aim is to forgo relying on heuristic assumptions. An open question is whether such an improved lower bound also applies to signing a vector of ` > 1 messages. We answer this question negatively for schemes existentially unforgeable under an adaptive chosenmessage attack (EUF-CMA) whereas we answer it positively for schemes existentially unforgeable under a random-message attack (EUF-RMA) and those which are existentially unforgeable under a combined chosenrandom-message attack (EUF-CMA-RMA). The latter notion is a leeway between the two former notions where it allows the adversary to adaptively choose part of the message to be signed whereas the remaining part of the message is chosen uniformly at random by the signer. Another open question is whether strongly existentially unforgeable under an adaptive chosen-message attack (sEUF-CMA) schemes with 2element signatures exist. We answer this question negatively, proving it is impossible to construct sEUF-CMA schemes with 2-element signatures even if the signature consists of elements from both source groups. On the other hand, we prove that sEUF-RMA and sEUF-CMA-RMA schemes with 2-element (unilateral) signatures are possible by giving constructions for those notions. Among other things, our findings show a gap between random-message/combined chosen-random-message security and chosen-message security in this setting.


Introduction
Structure-Preserving Signatures (SPSs) [4] are signature schemes over bilinear groups where the messages, the verification key and the signatures consist of only group elements from either/both source groups. Verification of signatures in those schemes only involves evaluating Pairing-Product Equations (PPEs) and checking group memberships. Such properties make them compatible with widely used constructs such as ElGamal encryption [22] and Groth-Sahai proofs [37]. Hence, they are an ideal building block for designing cryptographic protocols not relying on heuristic assumptions such as random oracles [25]. They have numerous applications which include group signatures, e.g [4,41], blind signatures, e.g. [4,27], attribute-based signatures, e.g. [24], tightly secure encryption, e.g. [38,3], malleable signatures, e.g. [12], anonymous credentials, e.g. [26,18], network coding, e.g. [12], oblivious transfer, e.g. [34], direct anonymous attestation, e.g. [15,31], and e-cash, e.g. [13]. Related Work. The notion was coined by Abe et al. [4] but earlier constructions conforming to the definition were given by [35,34]. The notion has been extensively studied. Constructions in the Type-3 setting (cf. Section 2.1) include [4,5,30,7,20,36,32,33]. Abe et al. [5] proved that signatures of schemes over Type-3 bilinear groups must contain at least 3 elements, which must include elements from both source groups, and require at least 2 PPEs for verification. This ruled out the existence of schemes with unilateral signatures, i.e. where all signature's components are from one of the source groups. Constructions relying on non-interactive assumptions were given by [19,2,17,3,40,41,39,9,29]. Abe et al. [6] proved that it is impossible to base the security of an optimal Type-3 scheme (i.e. with 3-element signatures) on non-interactive intractability assumptions. This in essence means that schemes based on non-interactive assumptions cannot be as efficient as their counterparts relying on interactive assumptions or those proven secure directly in the generic group model [45,44]. More recently, Abe et al. [1] proved lower bounds for schemes signing bilateral messages and based on non-interactive intractability assumptions.
Ghadafi [31] gave a randomizable scheme which can only sign a single Diffie-Hellman pair (cf. Section 2.1) yielding 3-element unilateral signatures and requiring the evaluation of 2 PPEs, excluding the cost for checking the well-formedness of the message, to verify signatures. More recently, Ghadafi [32] gave constructions for a single Diffie-Hellman pair yielding signatures consisting of only 2 elements from the shorter source group and requiring besides checking the wellformedness of the message, the evaluation of a single PPE for verification. He 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 [16], which is a protocol deployed in practice, and attribute-based signatures [42] as an example. Even though [32] 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. More recently, Ghadafi [33] gave EUF-CMA constructions for a vector of DH pairs with 2-element bilateral signatures.
Constructions in the Type-2 setting (where an efficiently computable unidirectional homomorphism between the source groups exists) were given in [8,20,14,1].
Fully structure-preserving schemes where even the secret key consists of only group elements from the source groups were recently given by [10,36,47].
Motivation & Contribution. Many applications of SPSs require signing a vector of group elements. For instance, consider the case when certifying the public keys of encryption or signature schemes. This is, for instance, required for constructing various variants of anonymous signatures, including group signatures [21], attribute-based signatures [42], proxy signatures [43], k-times anonymous authentication [46], and direct anonymous attestation [16]. This is particularly important when the aim is to dispense with relying on random oracles as in such cases one cannot use standard signature schemes which hinder the structure of the message, e.g. by hashing or requiring knowledge of their discrete logarithm. Therefore, the design of efficient SPS schemes for a vector of messages would have implications for various applications.
SPS schemes on Diffie-Hellman pairs have rendered themselves as a tool to get around the known lower bounds for SPS schemes thus improving efficiency without being too restrictive as they suffice for many applications of SPS schemes. Examples of where SPS schemes on Diffie-Hellman pairs provide better efficency than optimal SPS schemes on unilateral messages include [32,23]. Also, as argued by [32], optimal SPS schemes on Diffie-Hellman pairs outperform some widely used non-structure-preserving schemes in terms of efficiency.
Note that the size of the elements of one of the source groups is twice as large as that of those from the other source group and hence having schemes with 2-element unilateral signatures from the shorter source group is desirable.
A first intriguing open question is whether EUF-CMA SPS schemes for a vector of group elements with 2-element unilateral signatures are possible. We answer this question negatively by proving the impossibility of the existence of such schemes. However, we show that EUF-RMA and EUF-CMA-RMA (cf. Section 2.2) schemes are possible. The latter is a leeway between EUF-RMA and EUF-CMA where it allows the adversary to adaptively choose some part of the message whereas the remaining part of the message is chosen uniformly at random by the signer. While EUF-RMA and EUF-CMA-RMA are both weaker notions than EUF-CMA since unlike the latter, they restrict part of the message to being chosen uniformly at random, we envisage that EUF-CMA-RMA may suffice to replace EUF-CMA for some applications. Consider, for instance, κ-times anonymous authentication schemes [43], where an authority provides users with κ credentials which allow them to anonymously authenticate themselves κ times. The underlying idea for some of the existing constructions is that the credential is a signature by the authority on the user's public key/ID along with a random element chosen by the authority. EUF-CMA-RMA signature schemes may suffice to replace EUF-CMA schemes for such applications.
Another open question is whether strongly existentially unforgeable schemes under an adaptive chosen-message attack (sEUF-CMA) with 2-element (whether unilateral or bilateral) signatures exist. Strong unforgeability is essential for various applications, e.g. [11]. Optimal Type-3 sEUF-CMA schemes for unilateral messages, e.g. [20,7,36], have a lower bound of 3-element bilateral signatures, thus, investigating whether the improved lower bound that exploits a special structure of the message also applies to strong unforgeability would have implications for various applications of SPS schemes. We prove that sEUF-CMA schemes with 2-element signatures are not possible. This holds even if the signature is bilateral. On the other hand, we show that sEUF-RMA and sEUF-CMA-RMA schemes with 2-element (unilateral) signatures exist by giving constructions.
Our results highlight a gap between random-message/combined chosen-randommessage security and chosen-message security in this setting.
Paper Organization. We provide some preliminary definitions in Section 2. In Section 3 we prove the impossibility of the existence of EUF-CMA schemes for a vector of > 1 messages with 2-element unilateral signatures. In Section 4 we prove the impossibility of the existence of sEUF-CMA schemes with 2-element signatures regardless of whether the signatures are unilateral or bilateral. Finally, in Section 5 we construct a sEUF-CMA-RMA scheme for a vector of messages with 2-element unilateral signatures.
Notation. We write y = A(x; r) when algorithm A on input x and randomness r outputs y. We write y ← A(x) for the process of setting y = A(x; r) where r is sampled at random. We also write y ← S for sampling y uniformly at random from a set S. A function ν(.) : N → R + is negligible (in n) if for every polynomial p(.) and all sufficiently large values of n, it holds that ν(n) < 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, . . . , k}.

Preliminaries
In this section we provide some preliminary definitions.

Bilinear Groups
A bilinear group is a tuple P := (G, H, T, p, G,H, e) where G, H and T are groups of a prime order p, and G andH generate G and H, respectively. The function e is a non-degenerate bilinear map e : G × H −→ T. We refer to G and H as the source groups whereas we refer to T as the target group. We use multiplicative notation for all the groups. For clarity we will accent elements of H with˜. We let G × := G \ {1 G } and H × := H \ {1 H }. We limit our attention to the efficient Type-3 setting [28], where G = H and there is no efficiently computable homomorphism between the source groups in either direction. We assume there is an algorithm BG that on input a security parameter κ, outputs a description of bilinear groups.
The message space of the schemes we consider is the set of elements of the subgroup GH of G × H defined as the image of the map ψ : x ∈ Z p . One can efficiently test whether (M,Ñ ) ∈ GH by checking e(M,H) = e(G,Ñ ) · Such pairs were called Diffie-Hellman (DH) pairs in [4]. We stress that we do not require that the signer knows the discrete logarithm of the message pair. In fact, in all of our proofs/constructions we assume a signer which does not know/does not exploit knowledge of such an exponent.

Digital Signatures
A digital signature scheme DS over a bilinear group P generated by BG for a message space M consists of the following algorithms: Definition 1 (Correctness). A signature scheme DS over a bilinear group generator BG is (perfectly) correct if for all κ ∈ N: A signature scheme is said to be existentially unforgeable if it is hard to forge a signature on a new message that has not been signed before where the adversary may see signatures on other messages before outputting her forgery. We distinguish between adaptive chosen-message (EUF-CMA), random-message (EUF-RMA) and combined chosen-random-message (EUF-CMA-RMA) variants of existential unforgeability as defined below.
Definition 2 (EUF-CMA). A signature scheme DS over a bilinear group generator BG is Existentially Unforgeable under an adaptive Chosen-Message Attack if for all κ ∈ N for all PPT adversaries A, the following is negligible (in κ): Strong Existential Unforgeability under an adaptive Chosen-Message Attack (sEUF-CMA) is defined similarly and requires that the adversary cannot even output a new signature on a message that was queried to the sign oracle.
Definition 3 (EUF-RMA). A signature scheme DS over a bilinear group generator BG is Existentially Unforgeable under a Random-Message Attack if for all κ ∈ N for all PPT adversaries A, the following is negligible (in κ): where Sign uniformly samples a message m from M and returns m and a signature σ on it, and Q Sign is the set {m i } q i=1 of messages returned by Sign. Strong Existential Unforgeability under a Random-Message Attack (sEUF-RMA) is defined similarly and requires that the adversary cannot even output a new signature on a message that was chosen by Sign.
The following variant lies in between the two previous notions where it allows the adversary to adaptively choose some part of the message whereas the remaining part of the message is chosen uniformly at random by the sign oracle.
Definition 4 (EUF-CMA-RMA). A signature scheme DS over a bilinear group generator BG for a message space M = M C × M R is Existentially Unforgeable under a combined Chosen-Random-Message Attack if for all κ ∈ N for all PPT adversaries A, the following is negligible (in κ): where when queried on a message m i ∈ M C , Sign uniformly samples a message m i from M R and returns m i and a signature σ on (m i , m i ), and Q Sign is the set containing pairs on which signatures have been generated by Sign. Strong Existential Unforgeability under a combined Chosen-Random-Message Attack (sEUF-CMA-RMA) requires that the adversary cannot even output a new signature on a message pair on which she has obtained a signature from Sign.

Structure-Preserving Signatures
Structure-preserving signatures [4] are signature schemes defined over bilinear groups where the messages, the verification key and signatures are all group elements from either or both source groups, and verifying signatures only involves deciding group membership and evaluating PPEs of the form of Equation (1).
where A i ∈ G andB j ∈ H are group elements appearing in P, m, vk, σ, whereas c i,j ∈ Z p are public 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 G, H and T, and compare group elements as a generic signer.
3 Impossibility of generic-signer EUF-CMA SPS Schemes for a vector of > 1 Messages with 2-element Unilateral Signatures In this section we prove that generic-signer EUF-CMA SPS schemes for a vector of > 1 messages with 2-element unilateral signatures cannot exist. We start by proving the following theorem which is a generalization of Lemma 1 from [8] for SPS schemes for unilateral messages.
Theorem 1. A generic-signer EUF-RMA SPS scheme for a vector of ≥ 1 DH pairs must have for any message vector superpolynomially many potential signatures.
Proof. Since the signer is generic, the signature σ = (R,S) ∈ G n × Hñ on is computed via entry-wise exponentiation as Let's assume for contradiction that there is a scheme which has a polynomial number of potential signatures. This means there is a polynomial set for some polynomial ploy corresponding to the list of potential signatures. Now given signatures σ 1 = (R 1 ,S 1 ) and σ 2 = (R 2 ,S 2 ) on random DH message vectors (M 1 ,M 1 ) and (M 2 ,M 2 ), respectively, we have with probability 1 poly(κ) 2 that those signatures were constructed using the same vector This means such a scheme is not EUF-RMA secure against an adversary which makes 2 (non-adaptive) signing queries.
We now proceed to proving the impossibility of the existence of genericsigner EUF-CMA (against q > 1 sign queries) SPS schemes for a vector of > 1 messages with 2-element unilateral signatures. We prove that such schemes even for the simpler case where = 2 cannot exist.

Theorem 2.
There is no generic-signer EUF-CMA (against q > 1 sign queries) SPS schemes for a vector of 2 DH pairs with 2-element unilateral signatures. Proof. We start by proving the following lemma regarding the number of verification equations required for schemes with 2-element signatures. Now let's assume WLOG that the signature is of the form σ = (S 1 , S 2 ) ∈ G 2 , whereas the verification key is of the form (X,Ỹ ) ∈ G n × H n . The proof for the case where σ = (S 1 ,S 2 ) ∈ H 2 is similar.
A generic signer computes the signature as . Note that none of those polynomials has a term in m 1 or m 2 , i.e. they are independent of the messages. Thus, it is infeasible for a generic signer to compute a non-trivial signature component where its discrete logarithm s i contains a message m i (for any i ∈ {1, 2}) in a term in the denominator. This means that we must have that the verification equation does not contain the pairings e(S i ,M j ) for all j ∈ [2] and some i ∈ [2], i.e. either S 1 or S 2 is independent of the messages as otherwise this would mean that m i appears in the denominator of one of the signature components. Let's assume WLOG that S 1 is independent of the messages, i.e. the verification equation does not contain the pairings e(S 1 ,M i ) for i = 1, 2. This means the scheme has a verification equation of the following form: A generic signer cannot produce a signature component whose discrete logarithm has a term with any of the monomials: m 2 1 , m 1 m 2 , or m 2 2 . Thus, WLOG we can also assume that the verification equation does not contain a pairing of the form e(M i ,M j ) for all i, j ∈ [2], i.e. u i,j = 0 for all i, j ∈ [2]. This means the verification equation is of the following form: Lemma 2 below proves that a scheme with a verification equation of the form of Equation (3) is not secure against an adversary which makes 2 chosen-message sign queries, whereas Lemma 3 proves that even if we consider schemes with a verification equation of the form of Equation (2) such schemes are not EUF-CMA secure against an adversary that makes 3 chosen-message sign queries, which concludes the proof of the theorem. (3) is not EUF-CMA against 2 (non-adaptive) chosenmessage sign queries.

Lemma 2. A SPS scheme for a vector of 2 DH pairs with a verification equation of the form of Equation
Proof. We have 2 cases as follows:   This concludes the proof.
The following corollary follows from Theorem 2.

Corollary 1.
There is no generic-signer EUF-CMA SPS scheme for a vector of > 1 DH pairs with 2-element unilateral signatures.

Impossibility of sEUF-CMA (against q > 1 sign queries) SPS Schemes with 2-element Signatures
In this section we prove the impossibility of the existence of sEUF-CMA SPS schemes with 2-element (unilateral/bilateral) signatures. However, in Section 5 we show that sEUF-RMA and sEUF-CMA-RMA with 2-element (unilateral) signatures are possible by giving concrete constructions.
Proof. Lemma 1 proved that 1 PPE is sufficient for verifying 2-element signatures. The following 2 lemmata complete the proof, where the first deals with the case of bilateral signatures whereas the second deals with unilateral signatures.
Proof. Let's WLOG assume that the signature is of the form σ = (S 1 ,S 2 ) ∈ G × H, whereas the verification key (including any public parameters) is of the form (X,Ỹ ) ∈ G n × H n . The case where the signature is transposed is similar.
A generic signer computes the signature as S 1 := M α 1 (x,y) We have 3 cases as follows: • Case for some i ∈ [n ], c i = 0: After getting a signature σ = (S 1 ,S 2 ) on a (random) message (M,M ), fix any i ∈ [n ] where c i = 0, we can compute a new signature σ * = (S * 1 ,S * 2 ) on the random message (M,M ) as follows: The new signature is a valid forgery and we have σ * = σ for any γ ∈ Z × p .
Theorem 4. The scheme is sEUF-CMA-RMA secure in the generic group model.
Proof. We show that no linear combinations representing Laurent polynomials (of degrees ranging from −1 to 2 after q sign queries) in the discrete logarithms of the group elements the adversary sees correspond to a forgery on a new message. At the start of the game, the only elements in H the adversary sees arẽ H,W 1 ,W 2 which correspond to the discrete logarithms 1, w 1 , w 2 , respectively, whereas the only elements in G the adversary sees are G, X, Y 1 , . . . , Y η , U which correspond to the discrete logarithms 1, x, y 1 , . . . , y η , u, respectively.
Note that the only elements of H the q sign queries return are the uniformly random parts of the message {M i,j } for i ∈ [q] and j ∈ [η]. Thus, at the i-th sign query on the message (M i ,Ñ i ) ∈ GH, m i and n i the discrete logarithms of M i andÑ i , respectively, can only be linear combinations of the discrete logarithms of the elements in G and H, respectively, the adversary sees up to that point of time. Thus, we have Since for all i ∈ [q], we must have that (M i ,Ñ i ) ∈ GH, i.e. m i = n i , we must have that a m i = a n i , b m i = b n i = c m i = c n i = 0, d m i,k = 0 for all k ∈ [η], f mi,j = g mi,j = 0 for all j ∈ [i − 1], and d n i, ,k = e m i, ,k for all ∈ [i − 1] and k ∈ [η]. Thus, we have If the message is well-formed, then at the i-th sign query, the adversary will receive a signature of the form σ i = (r i , s i ), where s i is of the following form: At the end of the game (after at most q sign queries), we must have Similarly, since the adversary can only construct her forgery as linear combinations of the Laurent polynomials she sees in the game, we have at the end of the game that r * and s * must be linear combinations of the Laurent polynomials in G. Thus, we have: Since by the verification equation we must have that: Thus, we must have that: There is no term of the form uw1 w2 on the LHS, so we must have that for all i ∈ [q] that g ri = 0. Also, for all i ∈ [η], there are no terms of the form xw 1 , y i w 1 , uw 1 or w 1 on the LHS so we must have that c r = 0, d ri = 0 for all i ∈ [η], b r = 0 and a r = 0. Thus, we have: There are no terms on the RHS with any of the monomials w 2 , uw 2 , xw 2 , y i w 2 for any i ∈ [η], r i w 2 for any i ∈ [q], or m i,j w 2 for any i ∈ [q] and j ∈ [η]. Thus, we must have that a s = 0, b s = 0, c s = 0, d si = 0 for all i ∈ [η], f si = 0 for all i ∈ [q] , and for all i ∈ [q] and all j ∈ [η] that e si,j = 0. Thus, we have: There are no terms of the form m i,j w 1 for any i ∈ [q] and any j ∈ [η] on the LHS. Thus, we must have that e ri,j = 0 for all i ∈ [q] and all j ∈ [η] and hence we must have that: By the term u we have that q i=1 g si = 1 and we must have that there is at least one value of g si = 0. Also, by the term r i w 1 we have that g si = f ri for all i ∈ [q]. Note that m i,j for all i ∈ [q] and all j ∈ [η] on the LHS are all chosen uniformly at random by the sign oracle. Also, there is no term on the LHS containing the monomial m i,j r k for any k = i. Thus, we cannot have for any i, j ∈ [q] where i = j that f ri = 0 and f rj = 0. This means we must have for some i ∈ [q] that: Since we must have that q i=1 g si = 1 and for all i ∈ [q] that g si = f ri , we must have: By the monomial x, we must have that m * = m i , whereas by the monomial y j we must have that m i,j = m j * for all j ∈ [η]. The above also means we have r * = r i and s * = s i . This means (r * , s * ) is not a valid forgery.
Remark 2. The proof holds even if we have that y 1 = 1 which means we can reduce the size of the verification key by eliminating 1 group element.
This concludes the proof.