key: cord-0047001-rekki5hb
authors: Ràfols, Carla; Silva, Javier
title: QA-NIZK Arguments of Same Opening for Bilateral Commitments
date: 2020-06-06
journal: Progress in Cryptology - AFRICACRYPT 2020
DOI: 10.1007/978-3-030-51938-4_1
sha: 72ffa3e6a0158ce099f8785a3fe480d2f5918d1a
doc_id: 47001
cord_uid: rekki5hb

Zero-knowledge proofs of satisfiability of linear equations over a group are often used as a building block of more complex protocols. In particular, in an asymmetric bilinear group we often have two commitments in different sides of the pairing, and we want to prove that they open to the same value. This problem was tackled by González, Hevia and Ràfols (ASIACRYPT 2015), who presented an aggregated proof, in the QA-NIZK setting, consisting of only four group elements. In this work, we present a more efficient proof, which is based on the same assumptions and consists of three group elements. We argue that our construction is optimal in terms of proof size.

single committed value can be proven. 1 This formalization is also a conceptually cleaner approach. It allows to differentiate clearly between the "commit" and the "proof" part among all the elements computed by the prover. In this work we also make the separation between commitment and proof, so when we discuss proof sizes we refer exclusively to the latter part.

For many equation types, the Groth-Sahai proof system is still the state of the art. Few improvements are known, like the general techniques to replace dual mode commitments by ElGamal ciphertexts [10] , aggregation of many Groth-Sahai proofs [16, 24] , which are of limited applicability, or some techniques to encode partial satisfiability [30] .

A notable exception are quasi-adaptive NIZK (QA-NIZK) arguments of membership in linear spaces over a source group [24, 26, 27] , introduced by Jutla-Roy [23] , which allow to prove satisfiability of linear equations. More precisely, let e : G 1 × G 2 → G T be an asymmetric bilinear group equipped with a pairing. We use implicit notation as in [12] , where [y] 1 ∈ G n 1 denotes a vector (y 1 P, . . . , y n P), for P a generator of G 1 . Such QA-NIZK arguments allow to prove that a vector [y] 1 ∈ G n 1 is of the form y = Mw, for some public matrix [M] 1 ∈ G n×t 1 . These arguments are extremely efficient: under an assumption weaker than DDH, their size is only 1 group element, for most distributions of [M] 1 . 2 The same statement proven with Groth-Sahai proofs requires O(t) elements for committing to w and O(n) elements to prove that y is of this form.

Because of their efficiency, these arguments have many applications, for instance to different flavors of identity-based encryption [23] or group signatures [28] . These arguments also have a close relation to structure-preserving signatures [1, 2, 25] . Membership in linear spaces naturally encodes statements about ciphertexts and commitments: for example, two ElGamal ciphertexts (or more generally, any 'algebraic' commitment scheme, like Pedersen or Groth-Sahai commitments) encrypt the same message if their difference is in a certain linear space dependent of the public key. More generally, QA-NIZK arguments allow to aggregate proof easily: proving that two vectors of ElGamal commitments open pairwise to the same value requires only one group element, using the constructions of Kiltz-Wee [26] , and the security relies on Kernel assumptions [29] . On the other hand, with the Groth-Sahai proof system, this requires two elements of each group G 1 , G 2 for each pair of ciphertexts.

In this paper, we consider the problem of proving that two commitments, one in G 1 and one in G 2 , open to the same value. This statement appears naturally when one wants to prove quadratic relations in asymmetric bilinear groups. Indeed, suppose that we want to prove that a commitment opens to a bit, that is, that the opening of some commitments satisfies the quadratic equation X(X − 1) = 0. This often appears as part of a larger proof, for example in ring signatures [8, 14, 15] , e-voting [7] or range proofs [6] . To prove that a commitment opens to a bit, Groth-Sahai proofs proceed as follows:

1. Rewrite the equation as X(Y − 1) = 0. 2. Commit to a solution: [c] 1 = Com(x; r) and [d] 2 = Com(y; s). 3 . Prove satisfiability of the equation X(Y − 1) = 0 using the commitments c, d and providing some additional proof elements. 4. Prove that the commitments c, d open to the same value.

We note that step 4 is proving the linear equation X = Y . Informally, the idea is that step 3 is a quadratic check which requires commitments in different groups, and step 4 makes sure there is some consistency between these values. Formally, the need for it arises from the fact that Groth-Sahai proofs work for disjoint sets of variables in G 1 and G 2 . This is one of the main techniques for proving quadratic equations in Z p in bilinear groups (in the CRS model and under standard assumptions), and any efficiency improvement in the same opening step (4) would have a direct impact on the overall efficiency. We note that there is another construction, introduced very recently in [9] , that proves that a commitment over G 1 opens to either 0 or 1. Their approach consists of using a pairing to compile interactive arguments into non-interactive ones, and they manage to prove that a commitment opens to a bit with 7 group elements. For comparison, the Groth-Sahai approach requires 10 group elements using our approach. Groth-Sahai proofs still seem better for proving that n commitments to a bit: in [9] the proof scales linearly, whereas if we use the aggregated version of our scheme, n proofs require 6n + 3 elements.

To the best of our knowledge, there are two ways of proving step 4. One is to use standard Groth-Sahai proofs, which requires 2 group elements in each of G 1 and G 2 . The alternative is to use QA-NIZK arguments of membership in linear spaces. However, because the statement is split between G 1 and G 2 , we need to resort to arguments of membership in bilateral spaces, which show, for two vectors [x] 1 , [y] 2 , and some matrices [M] 1 , [M] 2 that there exists some w such that x = Mw and y = Nw. These were constructed by González et al. [16] under some computational assumption in bilinear groups. 3 However, this does not improve step (4) over the cost of Groth-Sahai proofs. The proof of González et al. only improves on the state of the art for the aggregated case, namely to show that n pairs of commitments open (pairwise) to the same value with a proof made of 2 elements in G 1 and 2 elements in G 2 , independent of n. However, this is not an improvement for a single pair of commitments.

Noticing the gap between one element for one-sided proofs and four elements for bilateral proofs, a natural question is how much we can reduce the proof size in the bilateral case. In this paper, we give a construction which reduces the proof size of [16] to three elements, while maintaining the same computational assumption in the soundness proof.

We note that this is the first concrete improvement for step (4) since the publication of the work of Groth-Sahai. Our result is a sophisticated combination of the techniques of Kiltz-Wee [26] and González et al. [16] . Additionally, we argue that our constructions are optimal, by showing that any two-element proof is vulnerable to a simple attack.

We briefly review the linear space membership proof of Kiltz-Wee [26] . Their core idea is a clever translation to the bilinear group setting of a hash proof system, which is essentially a NIZK proof in the symmetric key setting. Given a matrix M ∈ Z m×t p , the starting point is a proof system for the language

which works as follows: prover and verifier share a key K ← Z m×(k+1) p

, where k will depend on the hardness assumption used to ensure soundness. The projection [M K] 1 is published in the CRS. The prover sends [π] 1 = w [M K] 1 , and the verifier checks that

Intuitively, the proof is sound because if c is not in Im(M) then c K is uniformly random given M K, and thus there is no way for the prover to produce such a proof.

Kiltz-Wee take this idea and remove the need for a shared secret key by using a bilinear group. Now the CRS includes [A, KA] 2 , for a matrix A ∈ Z (k+1)×k p . This partially fixes K without revealing it, the goal being that the verifier can use these elements to verify without needing to know K as before. The proof is still the same, but the verification is now

By assuming the hardness of a Kernel problem on A, i.e., it is hard to find non-trivial cokernel elements of A, we are essentially back to the argument of the hash proof system. For the right choice of distribution of A, the assumption is believed to hold starting at k = 1, so in this case we have that the proof is formed of 2 group elements.

However, this can be taken one step further. Assuming that the distribution of [M] 1 is witness sampleable, that is, that we can efficiently sampleM such that [M] 1 is distributed as [M] 1 , then it is enough to use the truncated matrix A ∈ Z k×k p instead of A, thus using K ∈ Z m×k p , which yields proofs consisting of only one group element.

We now consider the natural generalization of this approach to bilateral proofs, as developed by González et al. [16] . 4 Consider the following language:

To account for two-sided statements, we consider one key K for G 1 and one key L for G 2 , and so we publish the following elements in the CRS: 

(1)

Intuitively, the term Z in the CRS elements produces terms in the verification equation that will not cancel out unless w is the same in both sides. In a similar way as above, the soundness of this scheme reduces to the hardness of a Split Kernel problem, which is a Kernel problem with the solution split between G 1 and G 2 . However, Split Kernel problems are easy for k = 1, and so we must take at least k = 2. This has a direct impact on the sizes of the keys K and L, and so this approach yields proofs of two group elements in G 1 , and two in G 2 , and two verification equations. Our strategy to reduce the proof size is to use only one element in G 2 , so instead of having θ = (θ,θ) as above, we reuse the same θ. To make it work, we require the condition that the columns of N L are equal, so that θ = (θ, θ), and it is enough to send it once. This introduces extra complexity in the CRS generation, and the simulation of the CRS for the adversary in the soundness security reduction, particularly in the aggregated case. We present the proof directly for the most efficient case, k = 2.

To solve these new issues, we need to reformulate the problem slightly. Instead of considering the pair of commitments ([c] 1 , [d] 2 ) as the statement, we consider just [c] 1 , and build a proof of F -knowledge of F (w) = [w] 1,2 . Indeed, in applications the commitment [d] 2 is an artifact of the proof, as when proving quadratic statements we need to split the commitments between G 1 and G 2 to exploit the pairing. Regarding zero-knowledge, this change implies that the simulator knows the opening of one of the commitments. We note that both openings are required for proving zero-knowledge in Groth-Sahai proofs.

We stress that our modified formalization is due to the intricacies of the soundness reduction, and has no actual impact in most applications. This is because, as we have seen in the proof of X(X − 1) = 0 above, the commitment in G 2 is a byproduct of the proof, and thus can be seen as part of it, while the 'meaningful' statement is about the commitment in G 1 .

Interestingly, our trick of reusing θ does not work for both sides, and in fact in Sect. 5 we show an attack for any two-element proof of this form. We argue that the general form of any proof of bilateral same opening consisting of only two elements must have a verification equations that looks essentially like Eq. (1) above, but with π, θ scalars instead of vectors; then we show a simple algebraic attack that exploits the two-sided nature of the proof.

Let G be some probabilistic polynomial time algorithm which on input 1 λ , where λ is the security parameter, returns the group key which is the description of an asymmetric bilinear group gk := (p, G 1 , G 2 , G T , e, P 1 , P 2 ), where G 1 , G 2 and G T are additive groups of prime order p, the elements P 1 , P 2 are generators of G 1 , G 2 respectively, e : G 1 × G 2 → G T is an efficiently computable, nondegenerate bilinear map, and there is no efficiently computable isomorphism between G 1 and G 2 .

Elements in G γ are denoted implicitly as [a] γ := aP γ , where γ ∈ {1, 2, T } and P T := e(P 1 , P 2 ). For simplicity, we often write [a] 1,2 for the pair

The pairing operation will be written as a product, that is,

Vectors and matrices are denoted in boldface. Given a matrix T = (t i,j ), [T] γ is the natural embedding of T in G γ , that is, the matrix whose (i, j)th entry is t i,j P γ . We denote by |G γ | the bit-size of the elements of G γ .

A Quasi-Adaptive NIZK proof system [23] enables to prove membership in a language defined by a relation R ρ , which is in turn determined by some parameter ρ sampled from a distribution D gk . We say that D gk is witness sampleable if there exists an efficient algorithm that samples (ρ, ω) from a distribution D par gk such that ρ is distributed according to D gk , and membership of ρ in the parameter language L par can be efficiently verified with ω. While the Common Reference String (CRS) can be set based on ρ, the zero-knowledge simulator is required to be a single PPT algorithm that works for any relation R gk . We assume that CRS contains an encoding of ρ, which is thus available to V.

A tuple of algorithms (K 0 , K 1 , P, V) is called a QA-NIZK proof system for witness-relations R gk = {R ρ } ρ∈sup(D gk ) with parameters sampled from a distribution D gk over the parameter language L par , if there exists a PPT simulator (S 1 , S 2 ), such that for all non-uniform PPT adversaries A 1 , A 2 , A 3 we have:

Pr

Computational Quasi-adaptive Soundness:

Perfect Quasi-adaptive Zero-Knowledge:

where -P(CRS, ·, ·) emulates the actual prover. It takes input (x, w) and outputs a proof π if (x, w) ∈ R ρ . Otherwise, it outputs ⊥.

We will prove that our schemes have F -knowledge soundness, which we define in the context of witness sampleable distributions. Intuitively, F -knowledge means that, with access to some extraction key, it is possible to extract a function F of the witness from the statement and the proof. We note that our definition differs from the definition in [10] , as we give the extraction key generator access to the witness ω that proves membership of ρ in L par (in practice, this means that it has access to the discrete logarithms of the commitment key) and allow to extract information from not only the statement, but also the proof.

Given a function F , a scheme is F -knowledge sound if there exist a soundness PPT extraction key generator E 1 and a DPT extractor E 2 such that for any nonuniform PPT adversary A 2 , we have:

and the distributions of the CRS produced by K 1 and E 1 are the same.

We also define a stronger notion of zero-knowledge, called composable zeroknowledge [17] . Essentially, this means that real and simulated proofs are indistinguishable even when the simulation trapdoor is known. More formally, a scheme is composable zero-knowledge if there exists a PPT simulator (S 1 , S 2 ) such that for any non-uniform PPT adversary A 3 we have:

Composable Quasi-adaptive Zero-Knowledge:

: A 3 (π) = 1 . and the CRS produced by K 1 and S 1 are indistinguishable.

The following applies for G γ , where γ ∈ {1, 2}. [11] ). For all non-uniform PPT adversaries A,

where the probability is taken over gk

Intuitively, the D ,k -MDDH assumption means that it is hard to decide whether a vector is in the image space of a matrix or it is a random vector, where the matrix is drawn from D ,k . In this paper we will refer to the following matrix distributions:

where a i , r i ← Z p for i = 1, . . . , k. The L k -MDDH Assumption is the k-linear family of Decisional Assumptions and corresponds to the Decisional Diffie-Hellman (DDH) Assumption in G γ when k = 1. The SXDH Assumption states that DDH holds in G γ for γ = 1, 2.

Additionally, we will be using the following family of computational assumptions:

Assumption 2 (Kernel Diffie-Hellman Assumption in G γ [29] ). For all non-uniform PPT adversaries A:

where the probability is taken over gk ← G(1 λ ), A ← D ,k and the coin tosses of adversary A.

The D ,k -KerMDH Gγ Assumption is not stronger than the D ,k -MDDH Gγ Assumption, since a solution to the former allows to decide membership in Im([A] γ ). In asymmetric bilinear groups, there is a natural variant of this assumption. [16] ). For all non-uniform PPT adversaries A:

where the probability is taken over gk ← G(1 λ ), A ← D ,k and the coin tosses of adversary A.

While the Kernel Diffie-Hellman Assumption says one cannot find a non-zero vector in one of the groups which is in the co-kernel of A, the split assumption says one cannot find different vectors in G 1 × G 2 such that the difference of the vector of their discrete logarithms is in the co-kernel of A. As a particular case, [16] considers the Split Simultaneous Double Pairing Assumption in G 1 , G 2 (SSDP) which is the RL 2 -SKerMDH Assumption.

We present the type of commitments for which our QA-NIZK arguments can be used. These generalize many common schemes, like (multi-)Pedersen commitments and Groth-Sahai commitments. Our commitments are in the source groups, G γ for γ = 1, 2, of a bilinear group. Let F ∈ Z m×n p and U ∈ Z m× p be full-rank matrices. The commitment key is ck = [F, U] γ , and the commitment to a message x ∈ Z n p with randomness r ∈ Z p is defined as

Choosing the appropriate distributions for ([F] γ , [U] γ ), we can have two commitment keys, one that produces a perfectly binding commitment scheme and one that produces a perfectly hiding commitment scheme, and these two key distributions are computationally indistinguishable under a MDDH assumption (see [11] for details). In the description of our schemes and the soundness proofs we will use the perfectly binding key, switching to perfectly hiding to argue that our schemes are zero-knowledge.

The most well-known example is Groth-Sahai commitments to integers: given x ∈ Z p and randomness r ∈ Z p , this is an instantiation of the commitment defined above, with the matrices F ← Z 2 p , U ← Z 2 p when in perfectly binding mode, and F ← Z 2 p , U = λF for λ ← Z p , when in perfectly hiding mode.

A set of linear equations split between the two sides of a bilinear group can be written as

where X is the vector of unknowns, [c, M] 1 are the coefficients in G 1 and [d, N] 2 are the coefficients in G 2 . Thus, proving satisfiability of this system is equivalent to proving that there exist some vector w such that w ∈ Im M N .

Thus, these proofs are usually seen as proofs of membership in a linear subspace, in this case split between G 1 and G 2 . The problem of same opening of two algebraic commitments,

can be seen in this framework of membership in linear spaces, where

Since we are particularly interested in the case of same opening, we present our constructions directly for this application, although it would be easy to generalize to any matrices [M] 1 , [N] 2 , as long as they verify some conditions on their dimensions. As a warm-up, we develop first a non-aggregated version of the proof, as the main ideas are easier to visualize in this case.

Given x ∈ Z p and two commitments [c] 1 , [d] 2 to x, we provide a proof of both commitments opening to the same element x. More precisely, given a group description gk and commitment keys ck

-gk := (p, P 1 , P 2 , G 1 , G 2 , G T , e) ← G (1 λ 

Finally, choose z 2 ← Z p and set

Algorithm K 1 outputs the following CRS: 

The algorithm outputs 1 iff the following equations hold:

Completeness. Both equations are analogous, and it is easy to see that for honest provers, using that f k u = w(l v g), we have that

F -extractor. We now define the algorithm that, given the extraction key xk = (f , g, u, v) , and builds the environment for A as follows. B samples f , u ←D par and k u ,k u ← Z 2 p , and u ⊥ ← Z 2 p conditioned on u u ⊥ = 0. Implicitly, B defines

Observe that this implies that

which B can compute in G 2 . For the other side, B samples g, v ← Z 2 p and l v ← Z 2 p , and let v ⊥ ∈ Z 2 p be the unique vector such that v v ⊥ = 0 and

(note that l v is the same in both), and implicitly

which means that

and these can be computed in G 1 . Note that, by construction,

where we have used equalities (5) and (4), and therefore w = f ku g lv . A similar argument shows thatŵ = f k u

Finally, choose z 2 ← Z p and set 

Notice that, using the equalities (3) and (6), we can rewrite these expressions in terms of the columns of A. Indeed, these are equivalent to c (k u ||k u ||u ⊥ )a 1 − d (wl v ||ŵl v ||v ⊥ )a 1 = (π,π, 0)a 1 − (wθ,ŵθ, 0)a 1 ,

We rearrange this as a solution of the RL 2 -SKerMDH problem that the reduction B can compute:

It remains to argue that this is not the trivial solution. To do so, we look at the third component. As {f , u} and {g, v} are bases of Z 2 p , we can write c = xf +ru and d = yg+sv for some x, y, r, s ∈ Z p . Since the proof provided by the adversary is false, it must be that x = y. Then, in the first equation, the third component on the left is c u ⊥ = xf u ⊥ , while the corresponding component on the right is d v ⊥ = yg v ⊥ . Since f u ⊥ = g v ⊥ and x = y, these values are different. We conclude that we have found a nontrivial solution of the RL 2 -SKerMDH problem.

Theorem 2. The above scheme is composable zero-knowledge, with simulation trapdoor τ = (k u ,k u , l v ).

Proof. We switch to a game in which the commitments in G 2 are perfectly hiding instead of perfectly binding, and prove that in this case the scheme has perfect zero-knowledge. The CRS simulator generates the CRS as in the honest execution of the protocol, and also outputs τ = (k u ,k u , l v ) as the simulation trapdoor. The proof simulator chooses δ ← Z p and uses τ to produce:

We have that d sim is distributed as d, as the commitment is perfectly hiding, and π sim ,π sim , θ sim are uniformly random elements conditioned on satisfying the verification equations for any fixed c, d, which is the same distribution that π,π, θ have in an honest execution.

Given x ∈ Z n p and two commitments [c] 1 , [d] 2 to x, we provide a proof of both commitments opening to the same vector x. More precisely, given a group description gk and commitment keys ck 1 = [F, U] 1 , and

where F (x, r) = [x] 1,2 .

-gk := (p, P 1 , P 2 , G 1 , G 2 , G T , e) ← G(1 λ ).

-K 0 (gk ): set ck 1 = [F, U] 1 ← D par , where D par is witness sampleable, that is, there exists an efficiently sampleable distributionD par outputting (F,Ũ) such that [F,Ũ] 1 is distributed as [F, U] 1 .

for some w,ŵ ← Z p . Choose z 2 ← Z p and set

Algorithm K 1 outputs the following CRS:

[π,π] 1 )): The algorithm outputs 1 iff the following equations hold:

Completeness. It is easy to check that, if the prover is honest,

We have used that k u F = w(l v G). The second equation is completely analogous.

Note on Dimensions. For this scheme to work and be secure, we require some relations between the dimensions of the different elements involved.

(1) We want our commitments to be perfectly binding to be able to open the commitments in the source groups, so we require that m i ≥ n + i , for i = 1, 2.

(2) To be able to find l v ,l v verifying the Eq. (7), we need to solve the linear system ⎛

Since F is only known in G 1 , the system cannot be fully solved over Z p . However, we do not need the full solution over Z p , as only the projection V l v needs to be given in G 2 , while the full l v is necessary in G 1 . Thus we proceed as follows: we start by sampling t ← Z 2 p and setting V l v = V l v = t. Then we consider the system ⎛

The matrix is known over Z p and the right hand side is known over G 1 (since F is known over G 1 and the rest is known over Z p ), so the system can be solved over G 1 using Gaussian elimination. The system has solutions if 2m 2 ≥ 2n + 2 2 , which is implied by condition (1) above. (3) In the proof of the zero-knowledge property, we want to be able to switch the commitment in G 2 to perfectly hiding, so we need to ensure that it has enough randomness. Thus 2 ≥ n. (4) Consider the matrices (F||U) and (G||V). These are of size m i × (n + i ), for i = 1, 2, respectively. In the soundness reduction we will be interested in finding nonzero vectors u ⊥ , v ⊥ such that w u ⊥ = 0 for any vector w outside of the span of the columns of F, and the same for v ⊥ and G.

Additionally, we will require that

As we have already established that m i ≥ n+ i , we might need to add more columns to the matrices (F||U) and (G||V) so that they form bases of Z mi p , so let U, V ∈ Z mi×(mi−n) p be the augmented matrices such that (F||U) and (G||V) are bases of Z mi p for i = 1, 2, respectively. Then the vectors u ⊥ , v ⊥ are given by the nontrivial solutions of the linear system ⎛ ⎜ ⎝

This matrix is of size (m 1 + m 2 − n) × (m 1 + m 2 ), and therefore it has nontrivial solutions.

F -extractor. We now define the algorithm that, given the extraction key xk = (F, G, U, V), outputs a function of the witness, in this case F (x, r) = [x] 1,2 .

- , and let V be as in (4) above. We choose w,ŵ ← Z p and l v ← Z m2

Observe that this implies that

which we can compute over G 1 . For the other side, we sample (F, U) ←D par and define U as in (4) above. We also sample k u ,k u ← Z m1 p conditioned on

Let u ⊥ ∈ Z m1 p such that U u ⊥ = 0 and

We implicitly define

which means that

Note that, by construction,

where we have used equalities (9) and (10), and therefore F k u = w(G l v ) A similar argument shows that F k u =ŵ(G l v ). We can also compute

Finally, choose z 2 ← Z p and set 

Notice that, using equalities (11) and (8), we can rewrite these expressions in terms of the columns of A. Indeed, these are equivalent to

We rearrange this as a solution of the RL 2 -SKerMDH problem that the reduction can compute:

It remains to argue that this is not the trivial solution. To do so, we look at the third component. As the columns of (F||U) and (G||V) are bases of Z mi p for i = 1, 2, respectively, we can write c = Fx + Ur and d = Gy + Vs for some x, y ∈ Z n p , r, s ∈ Z p . Since the proof provided by the adversary is false, it must be that x = y. Then, in the first equation, the third component on the left is c u ⊥ = x F u ⊥ , while the corresponding component on the right is

We conclude that we have found a nontrivial solution of the RL 2 -SKerMDH problem.

Theorem 4. The above proof system is composable zero-knowledge, with simulation trapdoor τ = (k u ,k u , l v ).

The proof is completely analogous to the proof of Theorem 2.

We argue that our constructions are optimal in terms of proof size, at least based on this general strategy of commit-and-prove schemes, and where the prover is limited to linear algebraic operations on the group elements, and verification is a pairing equation. To the best of our knowledge, this is the approach that is always taken in the literature. We prove optimality by arguing that any such proof formed of two elements (plus the commitments) is vulnerable to an attack.

We now consider any proof in which we have two commitments [c] 1 and [d] 2 to the values x and y, respectively, and we have a two-element proof [π] 1 , [θ] 2 of same opening, that is, x = y. We consider a CRS formed of elements in G 1 and G 2 , and we assume that each side of the CRS is closed under linear combination. We can do this without loss of generality, since given the CRS it is easy to compute linear combinations of its elements.

Then the general verification equation of such a proof looks like this: 

where [k 1 , k 3 ] 2 , [k 2 , k 4 ] 1 are elements (some of them vectors of elements) of the CRS. We note two omissions from this general equation: there is no affine term and there are no "quadratic" terms, i.e., terms in c d, πd, cθ or πθ. This is because the linear terms (those in Eq. (12)) force π and θ to be linear in the witness, and so the terms above are quadratic. The quadratic condition causes the appearance of terms with coefficient xy, which must cancelled out with other quadratic terms of the same coefficient. We note that, unlike in the linear part, this check does not make a distinction when x = y or x = y, so we conclude that these quadratic terms do not contribute to achieving soundness. The intuition behind this is that we are proving membership in a linear space, and non-linear operations take us out of the space. This leaves us with the Eq. (12) above. We now observe a very simple attack on any scheme with a verification equation like this. We set

where α, β ← Z 2 p . It is trivial to verify that the first term in the equation cancels out with the fourth and the second with the third, and with overwhelming probability the openings of [c] 1 and [d] 2 do not match. Intuitively, this attack works because of the two-sided nature of the proof: the elements that are given in the CRS to ensure verifiability in one side are used to fool the other. Indeed, in an honest execution the first term is expected to cancel out with the third, and the second with the fourth, while in this attack the pairs are jumbled.

One could also consider one-sided two-element proofs, i.e., of the form [π 1 , π 2 ] 1 or [θ 1 , θ 2 ] 2 , but these can be handled in a very similar way. for β ← Z 2 p , α, r, s ← Z p . Thus we conclude that, with this approach, there is no possible proof of same opening of commitments in different groups which consists of less than three group elements, making our constructions optimal.

Lower bounds on structurepreserving signatures for bilateral messages

Improved (almost) tightly-secure simulation-sound QA-NIZK with applications

Compact E-cash and simulatable VRFs revisited

Efficient signatures of knowledge and DAA in the standard model

Full-domain subgroup hiding and constant-size group signatures

Efficient protocols for set membership and range proofs

BeleniosRF: a noninteractive receipt-free electronic voting scheme

Ring signatures of sub-linear size without random oracles

Shorter non-interactive zero-knowledge arguments and zaps for algebraic languages

Fine-tuning Groth-Sahai proofs

An algebraic framework for Diffie-Hellman assumptions

An algebraic framework for Diffie-Hellman assumptions

Commuting signatures and verifiable encryption

Sub-linear blind ring signatures without random oracles

Shorter ring signatures from standard assumptions

QA-NIZK arguments in asymmetric groups: new tools and new constructions

Simulation-sound NIZK proofs for a practical language and constant size group signatures

A non-interactive shuffle with pairing based verifiability

Non-interactive zaps and new techniques for NIZK

Perfect non-interactive zero knowledge for NP

Efficient non-interactive proof systems for bilinear groups

Tightly secure signatures and public-key encryption

Shorter quasi-adaptive NIZK proofs for linear subspaces

Switching lemma for bilinear tests and constant-size NIZK proofs for linear subspaces

Structure-preserving signatures from standard assumptions, revisited

Quasi-adaptive NIZK for linear subspaces revisited

Non-malleability from malleability: simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures

Short group signatures via structure-preserving signatures: standard model security from simple assumptions

The kernel matrix Diffie-Hellman assumption

Stretching Groth-Sahai: NIZK proofs of partial satisfiability

Acknowledgements. The second author was supported by a PhD grant from the Spanish government, co-financed by the ESF (Ayudas paracontratos predoctorales para la formación de doctores 2016).