New Techniques for Non-interactive Shuffle and Range Arguments

Zero-knowledge proofs are proofs which yield nothing beyond the validity of a certain statement. Although one can prove every NP statement in zero-knowledge (going through a proof of circuit satisfiability, for instance), the literature has extensively explored more efficient alternatives for concrete statements which appear often in practice. Among them, some of the most important are: proofs of membership in linear spaces [13, 14, 16, 17], range proofs [3, 4, 20], membership in a set [2, 20], or correctness of a shuffle [5, 7, 10, 18].

These problems have been studied following a variety of approaches and techniques. For instance, they have been studied both in the interactive [1, 3, 9] and the non-interactive setting [4, 7, 10, 18, 20], and in the latter setting, both under falsifiable (but not always standard) [10, 20] and non-falsifiable assumptions [4, 7, 18] (like knowledge of exponent type of assumptions).

Generally speaking, non-interactive zero-knowledge proofs under falsifiable assumptions remain more inefficient than other approaches for the same problem (one notable exception being the recent QA-NIZK arguments of membership in linear spaces of [14, 16, 17]). However, this is the most desirable alternative from a cryptographic point of view. Indeed, interaction is not so convenient in practice and further, there is the additional problem of non-transferability (a proof might not convince a third party who cannot check if the challenges were computed correctly). On the other hand, non-falsifiable assumptions are very strong assumptions whose use is, at the very least, controversial. Although it might still be interesting to use these assumptions in practice, from a theoretical viewpoint it is definitely worth to explore how to improve efficiency based only on standard assumptions.

This paper focuses on obtaining efficiency improvements for non-interactive arguments based on falsifiable assumptions for two of the interesting examples discussed above, namely, range proofs and proofs of correctness of a shuffle.

An argument of Correctness of a Shuffle is an essential tool in the construction of Mix-nets [5]. A Mix-net consists of a series of mixers, each of which receives as input a set of n ciphertexts and outputs a shuffle of the input ciphertexts. That is, a rerandomization of the set of ciphertexts obtained after applying a random permutation to the input set of ciphertexts. To enforce the honest behavior of mixers they are required to produce a zero-knowledge argument that the shuffle was correctly computed.

A Range argument is a tool often required in e-voting and e-cash scenarios, with the purpose of showing that the opening y of some commitment c is an integer in some interval [A, B]. For simplicity, the range considered is usually \([0,2^n-1]\) since a proof in any interval can be reduced to a proof in this interval.

To derive efficiency improvements for these two languages we develop specific techniques that we can apply to both problems. Our resulting proofs are more efficient in terms of proof size and are based on more standard assumptions, but they have a rather large common reference string. They build on the recent arguments for membership in linear spaces of [14, 16, 17] and the argument for proving that some commitment to a vector of integers in \(\mathbb {Z}_q^{n}\) opens to \(\{0,1\}^n\) due to [8].

1.1 Our Techniques

All our results are in a bilinear group \(gk:=(q,\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T,e,\mathcal {P}_1,\mathcal {P}_2)\), where \(\mathbb {G}_1,\mathbb {G}_2\) and \(\mathbb {G}_T\) are groups of prime order q, \(\mathcal {P}_\gamma \) generates \(\mathbb {G}_\gamma \) for \(\gamma \in \{1,2\}\) and \(e:\mathbb {G}_1\times \mathbb {G}_2\rightarrow \mathbb {G}_T\) is an efficiently computable, non-degenerate bilinear map. Given a generator \(\mathcal {P}_\gamma \) of \(\mathbb {G}_\gamma \), for any \(x\in \mathbb {Z}_q\) we define \([x]_\gamma :=x\mathcal {P}_\gamma \). We simply write \([x]_1[y]_2\) to denote \(e([x]_1,[y]_2)\).

Note that in bilinear groups we could use Groth-Sahai proofs to prove any the statements we consider (quadratic equations allow to prove every statement in NP, [11]). However, a naive use of GS proofs results in a large proof size (\(\varTheta (n^2)\) for shuffles, \(\varTheta (n)\) for range proofs) and in fact, as we discuss below, they have always been combined with other strategies to obtain improved asymptotic efficiency.

A Common Building Block. Our starting point is the observation that range and shuffle proofs can be constructed by using as a common building block a “zero-knowledge aggregated set membership argument”. This is achieved by slightly modifying some previous strategies used for shuffle and range proofs.

More specifically, given some publicly known set S, such an argument proves that n commitments \(c_1,\ldots ,c_n\) open to values \(x_1,\ldots ,x_n \in S\). The set S is of polynomial size and is either \([0,d-1]\subset \mathbb {Z}_q\) or a subset of \(\mathbb {G}_\gamma \), \(\gamma \in \{1,2\}\). In other words, an aggregated set membership argument proves that each \(c_1,\ldots ,c_n\) is in the language

and \(c=\mathsf {Com}_{ck}(x;\mathbf {w})\) is a Groth-Sahai commitment to x with randomness \(\mathbf {w}\). The proof is Quasi-Adaptive [13], in the sense that the common reference string depends on ck and S, which are assumed to be sampled from some distribution \(\mathcal {D}\) and further, the marginal distribution of ck is assumed to be witness samplable, which essentially means it can be sampled along with its discrete logarithms. The argument is said to be aggregated because the size of the proof is independent of n (\(\varTheta (\log d)\) when \(S=[0,d-1]\) and \(\varTheta (|S|)\) when \(S\subset \mathbb {G}_\gamma \)). However, in the soundness proof we will loose a factor of n in the reduction.

Before discussing how to construct such an argument, we show how to use it as a building block for range and shuffle proofs.

Range Argument: Let \(n,d\in \mathbb {N}\), \(m:=\log d\), and \(\ell :=n/m\). A commitment c opens to an integer x in the range \([0,2^n-1]\) if \(\exists x_1,\ldots ,x_\ell \in [0,d-1]\) and \(x=\sum _{i\in [\ell ]}x_id^{i-1}\). Indeed, since \(x_i\in [0,d-1]\), \( x = \sum _{i\in [\ell ]} x_i d^{i-1} \in [0,d^\ell -1]\) and \([0,d^\ell -1]=[0,(d^{1/\log d})^n-1] = [0,2^n-1]. \) The statement \(\exists x_1,\ldots ,x_\ell \in [0,d-1]\) can be proven by showing that \((c_1,\ldots ,c_\ell )\in \mathcal {L}_{ck,[0,d-1]}^\ell \), where \(c_i=\mathsf {Com}_{ck}(x_i)\), with an aggregated set membership proof, and the statement \(x=\sum _{i\in [\ell ]}d^{i-1}x_i\) can be proven using standard techniques.

While this way of constructing range arguments has been widely used in the literature, with the addition of our techniques we get a smaller proof size. Indeed, the total cost of the range proof is \(\varTheta (\ell )+\varTheta (m)\) (\(\ell \) is due to the size of the commitments \(c_1,\ldots ,c_\ell \) and m to the size of an aggregated proof of membership in \(\mathcal {L}_{ck,[0,d-1]}^\ell \)). Setting \(d=n^{k}\) for arbitrary k leads to a proof size of \(\varTheta (\frac{n}{k \log n})\). Compared to previous approaches, the novelty of ours is that the cost of proving that \(x_1,\ldots ,x_\ell \in [0,d-1]\) is significantly reduced.

Shuffle Argument: The proof is partially inspired by the non-interactive shuffle of [10]. The statement we want to prove in a correctness of a shuffle argument is: “Given two vectors of ciphertexts which open, respectively, to vectors of plaintexts \([\mathbf {m}_1]_2, [\mathbf {m}_2]_2\), prove that \([\mathbf {m}_2]\) is a permutation of \([\mathbf {m}_1]\)”. Roughly, our strategy is the following: (1) publish some vector of group elements \([\mathbf {s}]_1 =([s_1]_1,\ldots ,[s_n]_1)^\top \) (which we identify with the set S of its components) in the common reference string, where \(\mathbf {s}\) is sampled from some distribution \(\mathcal {D}_{n,1}\); (2) the prover commits to \([\mathbf {x}]_1=([x_1]_1,\ldots ,[x_n]_1)^\top \), a permutation of the set S and proves that the commitments to \([\mathbf {x}]_1\) are in \(\mathcal {L}^{n}_{ck,S}\); (3) the prover proves that \(\sum _{i \in [n]} [x_i]_1 =\sum _{i \in [n]} [s_i]_1\); (4) finally, the prover outputs a proof that:^{Footnote 1}

The underlying computational assumption is that it is infeasible to find a non-trivial combination of elements of S which adds to 0, that is, given \([\mathbf {s}]_1\) it is infeasible to find \([\mathbf {k}]_2 \ne [\mathbf {0}]_2\) such that \(\mathbf {s}^{\top } \mathbf {k}=\mathbf {0}\) (this is the \(\mathcal {D}_{n,1}\)-\(\mathsf {KerMDH}\) Assumption of [19], which is a generalization of the Double Pairing Assumption, which is weaker than DDH).

Soundness goes as follows. First, by the soundness of the aggregated set membership proof, \([\mathbf {x}]_1 \in S^{n}\) and from the fact that \(\sum _{i \in [n]} x_i =\sum _{i \in [n]} s_i\), it holds that if \(\mathbf {x}\) is not a permutation of \(\mathbf {s}\), then one can extract in the soundness game (assuming the extractor knows ck) a non-trivial linear combination of elements of S which adds to 0, which contradicts the security assumption. Finally, if \(\mathbf {x}\) is a permutation of \(\mathbf {s}\), then Eq. (2) implies that the shuffle is correct, or, again, one can extract from \([\mathbf {m}_1]_2,[\mathbf {m}_2]_2\) the coefficients of some non-trivial combination of elements of S which is equal to 0 (breaking the \(\mathcal {D}_{n,1}\)-\(\mathsf {KerMDH}\) Assumption).

This soundness argument is an augmentation and translation into asymmetric groups of the argument of Groth and Lu [10]. Essentially, the argument there also consists of two parts: one devoted to proving that some GS commitments open to a permutation of some set in the CRS (in [10] this is done via the (non-standard) pairing permutation assumption), while the second part (Step 4) is proven very similarly (in particular, its soundness also follows from some Kernel Assumption secure in symmetric bilinear groups).

We note that it is crucial for our soundness argument that it is possible to decrypt the ciphertexts (otherwise we cannot extract solutions to the Kernel problems). This is possible in our case because public key for encryption is assumed to be witness-samplable and the argument is quasi-adaptive. This explains why we do not refer to the notion of culpable soundness, as in [7, 10].

Set Membership Proofs. Before we move to aggregated set membership proofs, we give a characterization of \(\mathcal {L}_{ck,S}\), defined as in Eq. (1), which is key to obtain our results. We observe that membership in S can be written as:

• If \(S \subset \mathbb {G}_{\gamma }\), and we identify S with \([\mathbf {s}]_\gamma =([s_1]_\gamma ,\ldots ,[s_m]_\gamma )^\top \) then, \(c \in \mathcal {L}_{ck,S}\) if and only if \(\exists \mathbf {b} \in \mathbb {Z}_q^{m}\) such that

  $$ 1) \mathbf {b} \in \{0,1\}^{m}, \ 2) c=\mathsf {Com}_{ck}(x;w), \ 3) x=\mathbf {s}^{\top } \mathbf {b}, \ 4) \sum _{i \in [m]} b_i=1.$$

• If \(S=[0,d-1]\) and \(m:=\log d\), then: \(c \in \mathcal {L}_{ck,S}\) if and only if \(\exists \mathbf {b} \in \mathbb {Z}_q^{m}\) such that:

  $$ 1) \mathbf {b} \in \{0,1\}^{m}, 2) c=\mathsf {Com}_{ck}(x;w), \ 3) x=(1,2,\ldots ,2^{m-1}) \mathbf {b} .$$

That is, both languages can be written in a similar way, except that when \(S \subset \mathbb {G}_{\gamma }\) there is an additional linear constraint that \(\mathbf {b}\) must satisfy (condition 4)).

To avoid distinguishing all the time between both types of subsets, we note that both languages can be seen as special case of the language \(\mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}\subseteq \mathbb {G}_1^{\ell _1}\), defined as: \([\mathbf {x}]_1\in \mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}\) if and only if \(\exists \mathbf {b}\in \mathbb {Z}_q^{m},\mathbf {w}\in \mathbb {Z}_q^{\ell _2}\) such that

The basic idea is that a GS commitment is a linear combination of the commitment keys whose coefficients are the randomness and the committed values, i.e. a commitment to a scalar \(x \in \mathbb {Z}_q\) is defined as \(\mathsf {Com}_{ck}(x;w)=x [\mathbf {u}_1]_1+w [\mathbf {u}_2]_1\), for \(ck=(\mathbf {u}_1,\mathbf {u}_2)\), so essentially membership in this space amounts to some “linear conditions” plus proving that \(\mathbf {b}\) is binary. For instance in the case where \(S=[0,d-1]\), it should hold that: where and \(\mathbf {{N}}=\mathbf {u}_2\). (In this case, because there is no condition 4), \(\mathbf {{\Lambda }}\) and \({\varvec{\alpha }}\) are zero and are ignored).

Proof Strategy. The most efficient strategy we are aware of for proving this type of statements follows a commit-and-prove approach. Namely, to prove that such a vector \(\mathbf {b}\) exists, one computes GS commitments \([\mathbf {d}_i]_1\), \(i \in [m]\), to all coordinates of \(\mathbf {b}\) and then it proves two independent statements, namely that:

• \(\exists \mathbf {b}\in \mathbb {Z}_q^{m}, \mathbf {r} \in \mathbb {Z}_q^m\) such that and ,

• \(\exists \widetilde{\mathbf {b}} \in \mathbb {Z}_q^{m}, \widetilde{\mathbf {r}} \in \mathbb {Z}_q^m, \mathbf {w} \in \mathbb {Z}_q^{\ell _2}\) such that and .

For the first, one can use the QA-NIZK argument for bit-strings of [8], and for the second, the QA-NIZK argument for linear spaces of [14, 16] (for the latter, note that conditions 2’) and 3’) can be written down as a single system of equations with a large matrix \(\widetilde{\mathbf {{M}}}\). Satisfiability of 2’) and 3’) is equivalent to \((\mathbf {c}^{\top },{\varvec{\alpha }}^{\top },\mathbf {d}_1^{\top }, \ldots , \mathbf {d}_m^{\top })^\top \) being in the span of this matrix \(\widetilde{\mathbf {{M}}}\)).

Since both proofs are constant-size, the resulting proof size is dominated by the cost of the commitments to \(b_i\), which is \(\varTheta (m)\). For soundness, the important point here is that we never prove that \(\mathbf {b}=\widetilde{\mathbf {b}}\), but, since GS commitments are perfectly binding (or, said otherwise, because \(\begin{pmatrix}\mathbf {u}_1&\mathbf {u}_2\end{pmatrix}\) has full rank), equality holds. This immediately proves the statement.

Aggregated Set Membership Proofs. An aggregated set membership proof amounts to proving membership in \(\mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}^n\). By definition, \(([\mathbf {c}_1]_1,\ldots , [\mathbf {c}_n]_1) \in \mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}^n\) if and only if \(\forall j \in [n], \exists \mathbf {b}_j\in \mathbb {Z}_q^{m},\mathbf {w}_j\in \mathbb {Z}_q^{\ell _2}\) such that

Recall that we want a proof size independent of n. This rules out the naive approach of computing GS commitments to all the coordinates of \(\mathbf {b}_j\), for all \(j \in [n]\), as the cost is \(\varTheta (nm)\). Therefore, to improve on the asymptotic size of the proof, we are forced to use shrinking commitments to \(b_{i,j}\). We stress that it is far from clear how to do this, as it might break down the soundness argument completely (e.g. in the single proof, we used in a fundamental way the uniqueness of the commitment openings). In fact, overcoming this problem is one of the main technical contributions of this paper.

Our idea is to use as a shrinking commitment a two-dimensional generalization of Multi-Pedersen commitments, which was used implicitly by González et al. [8]. Given some matrix \(\mathbf {{G}} \in \mathbb {Z}_q^{2 \times (n+1)}\) sampled from some distribution \(\mathcal {D}_{2,n+1}\), . The special thing about these commitments is that one can set a “hidden” linearly independent column of \(\mathbf {{G}}\), and thus commitments are perfectly binding at some coordinate \(j^*\in [n]\) which is computationally hidden to the adversary.

Define the matrix \(\mathbf {{B}}=(\mathbf {b}_1|| \ldots || \mathbf {b}_n) \in \{0,1\}^{{m}\times n}\) and let \(\mathbf {b}_i^*\) be the ith row of \(\mathbf {{B}}\). To prove \(([\mathbf {c}_1]_1,\ldots , [\mathbf {c}_n]_1) \in \mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}^n\), we first compute MP commitments \([\mathbf {d}_i]_1\), \(i \in [{m}]\), to \(\mathbf {b}_i^*\). As before, the proof actually consists of two independent statements:

• \(\exists \mathbf {r} \in \mathbb {Z}_q^{m}, \mathbf {{B}} \in \mathbb {Z}_q^{{m}\times n}\) such that \(1'') \mathbf {{B}} \in \{0,1\}^{{m}\times n}\) and ,

• \(\exists \widetilde{\mathbf {r}}\in \mathbb {Z}_q^{m}, \mathbf {w}_1,\ldots ,\mathbf {w}_n \in \mathbb {Z}_q^{\ell _2}, \widetilde{\mathbf {{B}}} \in \mathbb {Z}_q^{{m}\times n}\), (whose rows are denoted as \(\widetilde{\mathbf {b}}_i^*\), \(i \in [{m}]\), and the columns \(\widetilde{\mathbf {b}}_j\), \(j \in [n]\)), such that and .

Again, for the first we use a slight modification^{Footnote 2} of [8] and for the second, (after rewriting the equations) a QA-NIZK argument for linear spaces. With this approach, the proof remains of size \(\varTheta (m)\), the size of the commitments, while the rest of the proof is constant.

The interesting part is the soundness argument. The previous reasoning for the non-aggregated case (when \(n=1\)) fails here because now there is no guarantee that \(\mathbf {{B}}=\widetilde{\mathbf {{B}}}\) (as the openings of \([\mathbf {d}_i]_1\) are not unique). However, as we said, the distribution of the MP commitment key can be chosen so that it is binding at some coordinate \(j^*\). This implies that for all i, the \(j^*\)th coordinate of \(\mathbf {b}_i^*\) and \(\widetilde{\mathbf {b}}_i^*\) is equal, i.e. the \(j^*\)th column of \(\mathbf {{B}}\) and \(\widetilde{\mathbf {{B}}}\) must be equal.

Thus, we have that for the coordinate \(j^*\), the proof is sound (because \(\mathbf {b}_j^*\) is uniquely determined, which was the uniqueness of openings which was necessary to prove soundness for \(n=1\)). That is, the adversary cannot break soundness for any tuple \(([\mathbf {c}_1]_1,\ldots , [\mathbf {c}_n]_1)\) such that \([\mathbf {c}_j^*]_1 \notin \mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}\). But since \(j^*\) is computationally hidden from the adversary, we can reduce soundness to one coordinate soundness with a loss in the reduction of 1/n.

1.2 Related Work

Zero Knowledge Set Membership Arguments. Camenisch et al. constructed \(\varTheta (1)\) interactive Zero-Knowledge set membership arguments using Boneh-Boyen Signatures, and they prove them secure under the q-SDH assumption [3]. Bayer and Groth constructed \(\varTheta (\log |S|)\) interactive Zero-Knowledge arguments for polynomial evaluation, which can be used to construct set membership arguments, relying only on the discrete logarithm assumption [2]. However, none of the previous constructions have addressed the problem of aggregating many proofs, and a direct use of them will end up with a proof of size \(\varOmega (n)\).

NIZK Shuffle and Range Arguments. The most efficient NIZK Shuffle argument under falsifiable assumptions is the one from Groth and Lu [10], which works for BBS ciphertexts. The proof size is linear in the number of ciphertexts, specifically \(15n + 120\) group elements in Type I groups. The security of their construction relies on two assumptions: the Paring Product Assumption and the Permutation Pairing Assumption. The first assumption is a \(\mathcal {D}_{n,2}\)-\(\mathsf {KerMDH}\) Assumption, when \(\mathbf {{M}}\leftarrow \mathcal {D}_{n,2}\) is of the form \(\mathbf {{M}}^\top :=\left( \begin{matrix}x_1,\ldots ,x_n\\ x_1^2,\ldots ,x_n^2\end{matrix}\right) \) for \(x_i\leftarrow \mathbb {Z}_q\), \(i\in [n]\). The second assumption is proven generically secure in [10] but it seems to be unrelated with any other assumption.

Using non-falsifiable assumptions (i.e. Knowledge of Exponent type of assumptions), Lipmaa and Zhang [18] constructed a shuffle argument with communication \(6n|\mathbb {G}_1|+11|\mathbb {G}_2|\), and recently Fauzi and Lipmaa [7] constructed a shuffle argument with communication \((5n+2)|\mathbb {G}_1|+2n|\mathbb {G}_2|\).

Rial, Kohlweiss, and Preneel constructed a range argument in \([0,2^n-1]\) with communication \(\varTheta (\frac{n}{\log n -\log \log n})\) and prove it secure under the q-HSDH assumption [20]. One might get rid of the q-HSDH assumption replacing the P-signature with any Structure Preserving Signature, but, since the proof requires \(\frac{n}{\log n-\log \log n}\) Groth-Sahai proofs of satisfiability of the signature’s verification equation and the signature’s size is at least 7 group elements [15], the resulting protocol is far less efficient. Using non-falsifiable assumptions, Chaabouni, Lipmaa, and Zhang constructed a range argument with constant communication [4].

A detailed comparison of our Shuffle and Range arguments with the most efficient constructions under falsifiable assumptions is depicted in Table 1.

Let \(\mathsf {Gen}_a\) be some probabilistic polynomial time algorithm which on input \(1^{\lambda }\), where \(\lambda \) is the security parameter, returns the group key which is the description of an asymmetric bilinear group \(gk:=(q,\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T,e,\mathcal {P}_1,\mathcal {P}_2)\), where \(\mathbb {G}_1,\mathbb {G}_2\) and \(\mathbb {G}_T\) are groups of prime order q, the elements \(\mathcal {P}_1, \mathcal {P}_2\) are generators of \(\mathbb {G}_1,\mathbb {G}_2\) respectively, and \(e:\mathbb {G}_1\times \mathbb {G}_2\rightarrow \mathbb {G}_T\) is an efficiently computable, non-degenerate bilinear map.

Elements in \(\mathbb {G}_s\), are denoted implicitly as \([a]_s:=a \mathcal {P}_s\), where \(s \in \{1,2,T\}\) and \(\mathcal {P}_T:=e(\mathcal {P}_1,\mathcal {P}_2)\). The pairing operation will be written as a product \(\cdot \), that is \([a]_1 \cdot [b]_2=[a]_1 [b]_2=e([a]_1,[b]_2)=[ab]_T\). Vectors and matrices are denoted in boldface. Given a matrix \(\mathbf {{T}}=(t_{i,j})\), \([\mathbf {{T}}]_s\) is the natural embedding of \(\mathbf {{T}}\) in \(\mathbb {G}_s\), that is, the matrix whose (i, j)th entry is \(t_{i,j}\mathcal {P}_s\). We denote by \(|\mathbb {G}_s|\) the bit-size of the elements of \(\mathbb {G}_s\).

\(\mathbf {{I}}_{n\times n}\) refers to the identity matrix in \(\mathbb {Z}_q^{n\times n}\), \(\mathbf {{0}}_{m\times n}\) and \(\mathbf {{1}}_{m\times n}\) the all-zero and all-one matrices in \(\mathbb {Z}_q^{m\times n}\), respectively, and \(\mathbf {e}^{n}_i\) the ith element of the canonical basis of \(\mathbb {Z}_q^{n}\) (simply \(\mathbf {{I}}\), \(\mathbf {{0}}\), \(\mathbf {{1}}\), and \(\mathbf {e}_i\), respectively, if m and n are clear from the context). Given some matrices \(\mathbf {{A}}\in \mathbb {Z}_q^{m\times t},\mathbf {{A}}_1\in \mathbb {Z}_q^{m_1\times t},\ldots ,\mathbf {{A}}_n\in \mathbb {Z}_q^{m_n\times n}\), we define the operations and

2.1 Decisional Assumptions

Definition 1

Let \(\ell ,k \in \mathbb {N}\). We call \(\mathcal {D}_{\ell ,k}\) a matrix distribution if it outputs (in poly time, with overwhelming probability) matrices in \(\mathbb {Z}_q^{\ell \times k}\). We define \(\mathcal {D}_k := \mathcal {D}_{k+1,k}\).

For the following decisional assumption to hold, it is a necessary condition that \(\ell >k\). However, in other contexts, we might need \(\mathcal {D}_{\ell ,k}\) distributions where \(\ell \ge k\).

Definition 2

(Matrix Diffie-Hellman Assumption in \(\mathbb {G}_{\gamma }\), \(\gamma \in \{1,2\}\) [6]). Let \(\mathcal {D}_{\ell ,k}\) be a matrix distribution and \({gk}\leftarrow \mathsf {Gen}_a(1^\lambda )\). We say that the \(\mathcal {D}_{\ell ,k}\)-Matrix Diffie-Hellman (\(\mathcal {D}_{\ell ,k}\text {-}\mathsf {MDDH}_{\mathbb {G}_\gamma }\)) Assumption holds relative to \(\mathsf {Gen}_a\) if for all PPT adversaries \(\mathsf {D}\),

is negligible in k, where the probability is taken over \({gk}\leftarrow \mathsf {Gen}_a(1^\lambda )\), \(\mathbf {{A}} \leftarrow \mathcal {D}_{\ell ,k}, \mathbf {w} \leftarrow \mathbb {Z}_q^k, [\mathbf {z}]_\gamma \leftarrow \mathbb {G}_\gamma ^{\ell }\) and the coin tosses of adversary \(\mathsf {D}\).

In this paper we will refer to the following matrix distributions:

where \(a_i,a_{i,j}\leftarrow \mathbb {Z}_q\). The \(\mathcal {L}_{k}\text {-}\mathsf {MDDH}\) Assumption is the k-linear family of Decisional Assumptions and corresponds to the Decisional Diffie-Hellman (DDH) Assumption in \(\mathbb {G}_\gamma \) when \(k=1\). The SXDH Assumption states that DDH holds in \(\mathbb {G}_\gamma \) for all \(\gamma \in \{1,2\}\). The \(\mathcal {U}_{\ell ,k}\) Assumption is the Uniform Assumption and is the weakest of all assumptions of size \(\ell \times k\).

Further, given any matrix distribution \(\mathcal {D}_{k}\), \(m \in \mathbb {N}\) and any \(i \in [m]\), we will repeatedly make reference to the distribution \(\mathcal {D}_k^{m,i}\), which is defined as follows:

where \(\mathbf {{B}} \leftarrow \mathcal {D}_{k}\), \(\mathbf {w}_i \leftarrow \mathbb {Z}_q^k\) and \(\mathbf {z} \leftarrow \mathbb {Z}_q^{k+1}\). The following are two trivial properties of the \(\mathcal {D}_k^{m,i}\) distribution.

Lemma 1

Under the \(\mathcal {D}_{k}\)-\(\mathsf {MDDH}\) Assumption in \(\mathbb {G}_\gamma \), for any \(0 < i \le n\), the distribution of \([\mathbf {{A}}]_\gamma \) when \(\mathbf {{A}}\leftarrow \mathcal {D}_k^{m,0}\) and when \(\mathbf {{A}}\leftarrow \mathcal {D}_k^{m,i}\) are computationally indistinguishable. Further, if \(\ell >k\), for any \(i>0\), if \(\mathbf {{A}} \leftarrow \mathcal {D}_k^{m,i}\), then with overwhelming probability its ith column is linearly independent of the rest.

2.2 Computational Assumptions

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

Definition 3

(Kernel Diffie-Hellman Assumption in \(\mathbb {G}_{\gamma }\) [19]). Let \({gk} \leftarrow \mathsf {Gen}_a(1^\lambda )\). The Kernel Diffie-Hellman Assumption in \(\mathbb {G}_\gamma \) (\(\mathcal {D}_{\ell ,k}\)-\(\mathsf {KerMDH}_{\mathbb {G}_\gamma }\)) says that every PPT Algorithm has negligible advantage in the following game: given \([\mathbf {{A}}]_\gamma \), where \(\mathbf {{A}}\leftarrow \mathcal {D}_{\ell ,k}\), find \([\mathbf {x}]_{3-\gamma } \in \mathbb {G}_{3-\gamma }^{\ell }\), \(\mathbf {x} \ne \mathbf {0}\), such that \([\mathbf {x}]_{3-\gamma }^{\top }[\mathbf {{A}}]_{\gamma }=[\mathbf {0}]_T\).

The Simultaneous Pairing Assumption in \(\mathbb {G}_\gamma \) (\(\mathsf {SP}\) \(_{\mathbb {G}_{\gamma }}\)) is the \( \mathcal {U}_1\)-\(\mathsf {KerMDH}_{\mathbb {G}_{\gamma }}\) Assumption. The Kernel Diffie-Hellman assumption is a generalization and abstraction of this assumption to other matrix distributions. The \(\mathcal {D}_{\ell ,k}\)-\(\mathsf {KerMDH}_{\mathbb {G}_{\gamma }}\) Assumption is weaker than the \(\mathcal {D}_{\ell ,k}\)-\(\mathsf {MDDH}_{\mathbb {G}_{\gamma }}\) Assumption, since a solution to the former allows to decide membership in \(\mathbf {Im}([\mathbf {{A}}]_{\gamma })\).

In asymmetric bilinear groups, there is a natural variant of this assumption which was introduced in [8].

Definition 4

(Split Kernel Diffie-Hellman Assumption). Let \({gk}\leftarrow \mathsf {Gen}_a(1^\lambda )\). The Split Kernel Diffie-Hellman Assumption in \(\mathbb {G}_1,\mathbb {G}_2\) (\(\mathcal {D}_{\ell ,k}\text {-}\mathsf {SKerMDH}\)) says that every PPT Algorithm has negligible advantage in the following game: given \(([\mathbf {{A}}]_1,[\mathbf {{A}}]_2)\), \(\mathbf {{A}} \leftarrow \mathcal {D}_{\ell ,k}\), find a pair of vectors \(([\mathbf {r}]_1,[\mathbf {s}]_2) \in \mathbb {G}_1^{\ell } \times \mathbb {G}_2^{\ell }\), \(\mathbf {r} \ne \mathbf {s}\), such that \([\mathbf {r}]_1^{\top }[\mathbf {{A}}]_2=[\mathbf {s}]_2^{\top }[\mathbf {{A}}]_1\).

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 \(\mathbf {{A}}\), the split assumption says one cannot find a pair of vectors in \(\mathbb {G}_1^{\ell } \times \mathbb {G}_2^{\ell }\) such that the difference of the vector of their discrete logarithms is in the co-kernel of \(\mathbf {{A}}\). As a particular case we consider the Split Simultaneous Double Pairing Assumption in \(\mathbb {G}_1,\mathbb {G}_2\) (\(\mathsf {SSDP}\)) which is the \(\mathcal {RL}_{2}\text {-}\mathsf {SKerMDH}\) Assumption, where \(\mathcal {RL}_{2}\) is the distribution which results of sampling a matrix from \(\mathcal {L}_{2}\) and replacing the last row by random elements.

2.3 Groth-Sahai NIZK Proofs

The GS proof system allows to prove satisfiability of a set of quadratic equations in a bilinear group. The admissible equation types must be in the following form:

where \(\varvec{\alpha }\in A_1^{m_y}\), \(\varvec{\beta }\in A_2^{m_x}\), \(\mathbf {{\Gamma }}=(\gamma _{i,j}) \in \mathbb {Z}_q^{m_x\times m_y}\), \(t \in A_T\), and \(A_1,A_2,A_T\in \{\mathbb {Z}_q,\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T\}\) are equipped with some bilinear map \(f:A_1\times A_2 \rightarrow A_T\).

We give more details about GS proofs in the full version. Next, we introduce the GS commitment scheme.

Definition 5

The Groth-Sahai commitment scheme in the SXDH instantiation in the group \(\mathbb {G}_\gamma \), \(\gamma \in \{1,2\}\), is specified by the following three algorithms \((\mathsf {GS}.\mathsf {K},\mathsf {GS}.\mathsf {Com},\mathsf {GS}.\mathsf {Vrfy})\) such that:

• \(\mathsf {GS}.\mathsf {K}\) is a randomized algorithm, which on input the group key gk and the (optional and if not given assumed to be \(\mathsf {true}\)) flag \(\mathsf {binding}\), outputs a commitment key \(ck:=[\mathbf {{U}}]_\gamma =[(\mathbf {u}_1||\mathbf {u}_2)]_\gamma \in \mathbb {G}_\gamma ^{2\times 2}\). It samples \(\mathbf {u}_2\leftarrow \mathcal {L}_{1}\) and \(\mu \leftarrow \mathbb {Z}_q\), and, if \(\mathsf {binding}=\mathsf {true}\), \([\mathbf {{U}}]_\gamma \) is the perfectly binding key and \(\mathbf {u}_1:=\mu \mathbf {u}_2\) and else it is the perfectly hiding key and \(\mathbf {u}_1:=\mu \mathbf {u}_2-\mathbf {e}_2\).

• \(\mathsf {GS}.\mathsf {Com}\) is a randomized algorithm which, on input a commitment key \(ck=\left[ \mathbf {{U}}\right] _\gamma \), and a message \(\mathsf {m}\) in the message space \(\mathcal {M}_{ck}=\mathbb {Z}_q\cup \mathbb {G}_\gamma \), it proceeds as follows. If \(\mathsf {m}=m\in \mathbb {Z}_q\), it samples \(r \leftarrow \mathbb {Z}_q\) and outputs a commitment \(\left[ \mathbf {c}\right] _\gamma := m[\mathbf {e}_2+\mathbf {u}_1]_\gamma +r[\mathbf {u}_2]_\gamma \) in the commitment space \(\mathcal {C}_{ck}=\mathbb {G}_\gamma ^2\) and an opening \(Op=r\). If \(\mathsf {m}=[m]_\gamma \in \mathbb {G}_\gamma \), it samples \(\mathbf {r} \leftarrow \mathbb {Z}_q^2\) and outputs a commitment \(\left[ \mathbf {c}\right] _\gamma := [m]_\gamma \mathbf {e}_2+[\mathbf {{U}}]_\gamma \mathbf {r}\) in the commitment space \(\mathcal {C}_{ck}=\mathbb {G}_\gamma ^2\) and an opening \(Op=\mathbf {r}\).

• \(\mathsf {GS}.\mathsf {Vrfy}\) is a deterministic algorithm which, on input the commitment key \(ck=\left[ \mathbf {{U}}\right] _\gamma \), a commitment \(\left[ \mathbf {c}\right] _\gamma \), a message \(m \in \mathcal {M}_{ck}\) and an opening Op, outputs 1 if \(\left[ \mathbf {c}\right] _\gamma ={\mathsf {GS}}.\mathsf {Com}_{ck}(m;Op)\) and 0 otherwise.

Theorem 1

([12]). If \(ck\leftarrow \mathsf {K}(gk)\) (resp. \(ck\leftarrow \mathsf {K}(gk,\mathsf {false})\)) the Groth-Sahai commitment scheme is perfectly binding (resp. computationally binding) and computationally hiding (resp. perfectly hiding).

2.4 Quasi-Adaptive NIZK Arguments

A Quasi-Adaptive NIZK proof system [13] enables to prove membership in a language defined by a relation \(\mathcal {R}_\rho \), which in turn is completely determined by some parameter \(\rho \) sampled from a distribution \(\mathcal {D}_{gk}\). We say that \(\mathcal {D}_{gk}\) is witness samplable if there exists an efficient algorithm that samples \((\rho ,\omega )\) from a distribution \(\mathcal {D}_{gk}^{\mathsf {par}}\) such that \(\rho \) is distributed according to \(\mathcal {D}_{gk}\), and membership of \(\rho \) in the parameter language \(\mathcal {L}_\mathsf {par}\) can be efficiently verified with \(\omega \). While the Common Reference String can be set based on \(\rho \), the zero-knowledge simulator is required to be a single probabilistic polynomial time algorithm that works for the whole collection of relations \(\mathcal {R}_{gk}\).

The details of the QA-NIZK definition can be found in the full version.

QA-NIZK Argument for Linear Subspaces. In this section we describe the languages for which there exist constant-size QA-NIZK arguments of membership which will be used as building blocks in our constructions. These languages are (i) linear subspaces of \(\mathbb {G}_s^m\), \(s \in \{1,2\}\) [14, 16, 17], (ii) linear subspaces of \(\mathbb {G}_1^m\times \mathbb {G}_2^n\) [8], (iii) equal commitment opening [8], and (iv) sum in subspace [8]. More specifically, the languages are defined as follows for \(\gamma ,\nu \in \{1,2\}\),

In the above definitions, \(\mathbf {{M}} \in \mathbb {Z}_q^{m \times t_1}\), \(\mathbf {{N}} \in \mathbb {Z}_q^{n \times t_2}\) and ck (resp. ck’) defines some commitments to vectors of \(\mathbb {Z}_q^{n}\) where the randomness space is \(\mathbb {Z}_q^{t_1}\) (resp. \(\mathbb {Z}_q^{t_2}\)). In (iv), \(t_1=t_2\). The commitment scheme \(\mathsf {Com}\) is assumed to be of the form \(\mathsf {Com}_{ck}(\mathbf {w};\mathbf {r})=[\mathbf {{A}}]_\gamma \mathbf {w}+[\mathbf {{B}}]_\gamma \mathbf {r}\), for some matrices \([\mathbf {{A}}]_\gamma ,[\mathbf {{B}}]_\gamma \) defined in ck.

We denote indistinctly by \(\varPi _\mathsf {lin}\) the proof systems for (i) and (ii), by \(\varPi _\mathsf {com}\) the proof system for (iii), and by \(\varPi _\mathsf {sum}\) the proof system for (iv).

To compute the proof sizes of our constructions, we will use the most efficient instantiations for each of these languages, which are described in Table 2. We note that the argument of [8] for \(\mathcal {L}_{ck,ck',\mathsf {com}}\) is for the case \(\gamma =1,\nu =2\). It is not hard to see that when \(\nu =\gamma \), membership in \(\mathcal {L}_{ck,ck',\mathsf {com}}\) (for commitments of the form we specified) amounts to prove membership in some linear space in \(\mathbb {G}_\gamma \), which explains the second row of the table.

In this Section we introduce a new commitment scheme which is a generalization of Multi-Pedersen commitments and which was implicitly used in [8].

Given a vector \(\mathbf {m}\in \mathbb {Z}_q^m\), the Multi-Pedersen commitment in \(\mathbb {G}_{\gamma }\) is a single group element \([c]_\gamma :=\sum _{i\in [m]} m_i[g_i]_\gamma +r[g_{m+1}]_\gamma \in \mathbb {G}_\gamma \), where \([g_i]_{\gamma }\in \mathbb {G}_\gamma \), \(i\in [m+1]\), and \(r\leftarrow \mathbb {Z}_q\).^{Footnote 3} The \((k+1)\)-dimensional Multi-Pedersen commitment differs only in that the keys and the resulting commitments are in \(\mathbb {G}_{\gamma }^{k+1}\), for \(k\ge 1\).

While the original MP commitments are perfectly hiding, the interest of the new commitments is that, if the keys come from the distribution \(\mathcal {D}_k^{m,i}\) defined in Sect. 2.1, they are perfectly binding at coordinate i. Intuitively, the new commitment is defined in a larger space so that not all the information about the witness is destroyed (in an information-theoretic sense).

Definition 6

The \((k+1)\)-dimensional Multi-Pedersen commitment scheme in the group \(\mathbb {G}_\gamma \) is specified by the following three algorithms \(\mathsf {MP}=(\mathsf {MP}.\mathsf {K},\mathsf {MP}.\mathsf {Com},\) \( \mathsf {MP}.\mathsf {Vrfy})\):

• \(\mathsf {MP}.\mathsf {K}\) is a randomized algorithm, which on input the group key gk, a natural number \(m \in \mathbb {N}\), and the description of some matrix distribution \(\mathcal {D}_{k+1,m+k}\), outputs a commitment key \(ck:=[\mathbf {{G}}]_\gamma \), where \(\mathbf {{G}} \leftarrow \mathcal {D}_{k+1,m+k}\).

• \(\mathsf {MP}.\mathsf {Com}\) is a randomized algorithm which, on input a commitment key \(ck=[\mathbf {{G}}]_\gamma \), and a message \(\mathbf {m}\) in the message space \(\mathcal {M}_{ck}=\mathbb {Z}_q^{m}\), samples \(\mathbf {r} \leftarrow \mathbb {Z}_q^k\) and outputs a commitment in the commitment space \(\mathcal {C}_{ck}=\mathbb {G}_\gamma ^{k+1}\) and an opening \(Op=\mathbf {r}\),

• \(\mathsf {MP}.\mathsf {Vrfy}\) is a deterministic algorithm which, on input the commitment key \(ck=\left[ \mathbf {{G}}\right] _\gamma \), a commitment \(\left[ \mathbf {c}\right] _\gamma \), a message \(\mathbf {m} \in \mathbb {Z}_q^{m}\) and an opening \(Op=\mathbf {r}\in \mathbb {Z}_q^k\), outputs 1 if and 0 otherwise.

Theorem 2

The \(\mathsf {MP}\) scheme is computationally binding if the discrete logarithm assumption holds in \(\mathbb {G}_\gamma \). Further, if \(\mathcal {D}_{k+1,m+k}=\mathcal {D}_k^{m,i}\), it holds that:

• If \(i=0\), then \(\mathsf {MP}\) is perfectly hiding,

• If \(i \in [m]\), then \(\mathsf {MP}\) is statistically binding at coordinate i, which means that for each \([\mathbf {c}]_\gamma \in \mathbb {G}_{\gamma }^{k+1}\), there exists a unique \(\tilde{m}_i \in \mathbb {Z}_q\) such that for all \(\mathbf {m} \in \mathbb {Z}_q^m, \mathbf {r} \in \mathbb {Z}_q^{k}\) such that , \(m_i=\tilde{m}_i\). Further, the scheme is perfectly hiding at the rest of coordinates.

The proof is not hard to derive from the definition of the \(\mathcal {D}_k^{m,i}\) distribution, and can be found in the full version.

We construct a QA-NIZK argument of membership in the language

where \(ck:=[\mathbf {{G}}]_1\) and \(\mathbf {{G}}\) is a matrix sampled from some distribution \(\mathcal {D}_k^{m,i}\). For simplicity, in the exposition we restrict ourselves to the case \(\mathcal {D}_k=\mathcal {L}_{1}\) so \(\mathbf {{G}}\) is sampled from \(\mathcal {L}_1^{m,i}\), for some \(0 \le i \le m\).

It is important to note that, as an extended MP commitment is at best only binding at one coordinate, a priori showing that it opens to \(\mathbf {b} \in \{0,1\}^m\) is not very meaningful, as it does open to other values as well. However, when combined with external protocols that univocally define \(\mathbf {b}\), it becomes a key building block to obtain the rest of the results of the paper.

The argument is implicit in [8], where the authors construct a QA-NIZK argument for proving that a perfectly binding commitment opens to a bit-string. More technically, to prove that a perfectly binding commitment \([\mathbf {c}']_1\) opens to a bit-string \(\mathbf {b}\), the argument in [8] takes the following steps: (1) construct two MP commitments \([\mathbf {c}]_1\); \([\mathbf {d}]_2\) to \(\mathbf {b}\) (2) prove that \([\mathbf {c}]_1\) and \([\mathbf {c}']_1\) open to the same string; (3) prove that the two MP commitments \([\mathbf {c}]_1\) and \([\mathbf {d}]_2\) open to the same string; (4) prove that \(\mathbf {c}(\mathbf {d}-\sum _{j \in [m]} \mathbf {h}_j)^\top \in \mathbf {Span}(\{\mathbf {g}_i\mathbf {h}_j^\top :i,j\in [m+1]\}\setminus \{\mathbf {g}_i\mathbf {h}_i^\top :i\in [m]\})\), where \(ck:=[(\mathbf {g}_1,\ldots ,\mathbf {g}_{m+1})]_1\) and \(ck':=[(\mathbf {h}_1,\ldots ,\mathbf {h}_{m+1})]_2\). The last step guarantees that \(b_i(b_i-1)=0\) for all \(i \in [m]\). Indeed, \(\mathbf {c}(\mathbf {d}-\sum _{j \in [m]} \mathbf {h}_j)^\top \) can be written as a linear combination of the vectors \(\{\mathbf {g}_i\mathbf {h}_j^\top \}\) where the coefficient of \(\mathbf {g}_i\mathbf {h}_i^{\top }\) is \(b_i(b_i-1)\). Intuitively, an adversary will be able to prove that \(\mathbf {c}(\mathbf {d}-\sum _{j \in [m]} \mathbf {h}_j)^\top \) is in the span of the vectors \(\{\mathbf {g}_i\mathbf {h}_j^\top \}\) without those pairs where \(i=j\) only if \(b_i(b_i-1)=0\) for all \(i \in [m]\).

The argument we need for our results eliminates the perfectly binding commitment, which of course also means that step 2 disappears. Additionally, in the original scheme of [8], the distribution of \(ck=[\mathbf {{G}}]_1\) is \(\mathcal {L}_1^{m,0}\), while in our argument of membership in \(\mathcal {L}_{ck,\mathsf {bits}}\), \(\mathbf {{G}}\) can follow any distribution \(\mathcal {L}_1^{m,i}\) for some \(0 \le i \le m\). However, it is not hard to adapt the original proof to these distributions (in fact, in the soundness proof of [8], there is a game where the distribution of \(\mathbf {{G}}\) is changed to \(\mathcal {L}_1^{m,i}\), for some \(i \leftarrow [m]\)). The proof that \(\mathcal {L}_{ck,\mathsf {bits}}\) admits a constant-size QA-NIZK argument essentially reuses parts of the proof of [8]. In summary, in the full version of this work we prove the following result, which heavily draws on the work of [8].

Theorem 3

There exists a QA-NIZK argument \(\varPi _\mathsf {bits}\) for membership in \(\mathcal {L}_{ck,\mathsf {bits}}\) with proof size \(8|\mathbb {G}_1|+10|\mathbb {G}_2|\) with perfect completeness, perfect-zero knowledge and computational soundness.

4.1 Constant-Size Argument for \(\mathcal {L}_{ck,\mathsf {bits}}^n\)

We give a QA-NIZK argument of membership in the language \(\mathcal {L}_{ck,\mathsf {bits}}^n = \mathcal {L}_{ck,\mathsf {bits}} \times \ldots \times \mathcal {L}_{ck,\mathsf {bits}}\) with a proof size which is independent of n (but with a loss factor in the proof of soundness of n). The result will be crucial to get improved proof sizes for more complex statements. More specifically, we prove:

Theorem 4

There exists a QA-NIZK argument \(\varPi _{\mathsf {bits},n}\) for membership in \(\mathcal {L}_{ck,\mathsf {bits}}^n\) with proof size \(10|\mathbb {G}_1|+10|\mathbb {G}_2|\) with perfect completeness, perfect-zero knowledge and computational soundness.

The description of the protocol and the full proof of Theorem 4 are in the full version.

In this section we construct a QA-NIZK argument that many commitments open to elements in a set \([0,d-1] \subset \mathbb {Z}_q\) or \(S \subset \mathbb {G}_{\gamma }\). We first express both languages in a unified way.

Definition 7

Denote by \(\mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}\subseteq \mathbb {G}_1^{\ell _1}\) the language parameterized by \([\mathbf {{M}}]_1 \in \mathbb {G}_1^{{\ell _1}\times {m}},[\mathbf {{N}}]_1\in \mathbb {G}_1^{{\ell _1}\times {\ell _2}},\mathbf {{\Lambda }}\in \mathbb {Z}_q^{{\ell _3}\times {m}},\) and \({\varvec{\alpha }}\in \mathbb {Z}_q^{\ell _3}\) such that

(4)

Additionally, we require \((\mathbf {{N}},[\mathbf {{N}}]_1)\) to be efficiently samplable and that membership in \(\mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}\) is efficiently testable with the trapdoor \(\mathbf {{N}}\), that is, that there exists an efficient algorithm \(\mathsf {F}\) such that \(\mathsf {F}([\mathbf {{M}}]_1,\mathbf {{N}},[\mathbf {c}]_1)=1\Longleftrightarrow [\mathbf {c}]_1\in \mathcal {L}_{\mathbf {{M}},\mathbf {{N}},\mathbf {{\Lambda }},{\varvec{\alpha }}}.\) The witness of \([\mathbf {c}]_1\in \mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}\) is \((\mathbf {b},\mathbf {w})\), and the bit-witness is \(\mathbf {b}\). The size of the bit-witness is \({m}\).

Example 1

The language of GS commitments to group elements in the set \(S:=\{[s_1]_1,\ldots ,[s_{m}]_1\} \subset \mathbb {G}_1\), \(\mathcal {L}_{ck,S}\), where \(ck:=([\mathbf {u}_1]_1||[\mathbf {u}_2]_1)\), is equal to \(\mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}\), where , \(\mathbf {{N}}:=(\mathbf {u}_1||\mathbf {u}_2)\), \(\alpha =1\), and \(\mathbf {{\Lambda }}=(1,\ldots ,1)\). The bit-witness size is |S| and membership \(\mathcal {L}_{ck,S}\) is efficiently testable given \(\mathbf {u}_1,\mathbf {u}_2 \in \mathbb {Z}_q^2\) (assuming \(|S|=\mathsf {poly}(\lambda )\)).

Example 2

The language of GS commitments to integers in the range \([0,d-1]\), \(\mathcal {L}_{ck,[0,d-1]}\), where \(ck:=([\mathbf {u}_1]_1||[\mathbf {u}_2]_1)\), is equal to \(\mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}\), where \(\mathbf {{M}}:=(\mathbf {e}_2+\mathbf {u}_1)(2^0,2^1,\ldots ,2^{\log d-1})\in \mathbb {Z}_q^{2\times \log d}\), \(\mathbf {{N}}:=\mathbf {u}_2\in \mathbb {Z}_q^{2}\), and \({\ell _3}:=0\). The bit-witness size is \(\log d\) and membership in \(\mathcal {L}_{ck,[0,d-1]}\) is easily testable given \(\mathbf {u}_2 \in \mathbb {Z}_q^2\) (assuming \(d=\mathsf {poly}(\lambda )\)).

The general idea of how to prove membership in \(\mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}\) was explained in Sect. 1.1. As we discussed there the total size of the proof is \(2{m}|\mathbb {G}_1|+\varTheta (1)\).

5.1 QA-NIZK Argument of Membership in \(\mathcal {L}^{n}_{\mathbf {M},\mathbf {N},\mathbf {\Lambda },\mathbf {\alpha }}\)

The main result of this Section is a proof, of roughly the same size as in the last Section (\(2{m}|\mathbb {G}_1|+\varTheta (1)\)), that \(([\mathbf {c}_1]_1,\ldots ,[\mathbf {c}_n]_1)\) is in \(\mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}^n\).

For all \(j \in [n]\), let \((\mathbf {b}_j,\mathbf {w}_j) \in \{0,1\}^{{m}} \times \mathbb {Z}_q^{{\ell _2}}\) be the witness of \(\mathbf {c}_j \in \mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}.\) Let \(\mathbf {{B}}=(\mathbf {b}_1|| \ldots ||\mathbf {b}_n)\) and let \(\mathbf {b}^*_{i}\), \(i \in [m]\) the ith row of \(\mathbf {{B}}\). To get a proof of size independent of n we commit to \(\mathbf {{B}}\) “compressing the rows”, that is, the proof includes MP commitments \([\mathbf {d}_i]_1\), \(i \in [n]\) to \(\mathbf {b}_i^*\).^{Footnote 4} Further, as announced in Sect. 1.1, the proof consists of two independent statements:

• \(\exists \mathbf {r} \in \mathbb {Z}_q^{m}, \mathbf {{B}} \in \mathbb {Z}_q^{{m}\times n}\) such that and ,

• \(\exists \widetilde{\mathbf {r}} \in \mathbb {Z}_q^{m}, \mathbf {w}_1,\ldots ,\mathbf {w}_n \in \mathbb {Z}_q^{\ell _2}, \widetilde{\mathbf {{B}}} \in \mathbb {Z}_q^{{m}\times n}\) such that and .

For the first statement we use the constant-size argument for \(\mathcal {L}_{ck,\mathsf {bits}}^m\) of Sect. 4. For the second statement, we write conditions 2”), 3”) as a single system of equations and use \(\varPi _\mathsf {lin}\) to prove that it can be satisfied.

The soundness argument follows from the arguments exposed in Sect. 1.1. The full description of the argument together with the proof of the following theorem are in the full version.

Theorem 5

There exists a QA-NIZK argument \(\varPi _\mathsf {set}\) for membership in the language \(\mathcal {L}_{[\mathbf {{M}}]_1,[\mathbf {{N}}]_1,\mathbf {{\Lambda }},{\varvec{\alpha }}}^n\) with proof size \((2{m}+11)|\mathbb {G}_1|+10|\mathbb {G}_2|\), perfect completeness, perfect-zero knowledge and computational soundness.

In a NIZK Shuffle argument one wants to prove that two lists of ciphertexts open to the same values when the second list is permuted under some hidden permutation. We represent each list of ciphertexts as a matrix in \(\mathbb {G}_2^{2\times n}\) where each column is an El-Gamal ciphertext under public key \(pk:=[\mathbf {v}]_2\in \mathbb {G}^2_2\) and we write \(\mathsf {Enc}_{pk}([\mathbf {m}^\top ]_2;\mathbf {r}^\top ):=(\mathsf {Enc}_{pk}([m_1]_2;r_1)||\cdots ||\mathsf {Enc}_{pk}([m_n]_2;r_n))\), where \([\mathbf {m}]_2\in \mathbb {G}_2^n\), \(\mathbf {r}\in \mathbb {Z}_q^n\), and \(\mathsf {Enc}_{pk}([m]_2;r):=[m]_2\mathbf {e}_2+r[\mathbf {v}]_2\). Similarly, through this section we will sometimes write \({\mathsf {GS}}.\mathsf {Com}_{ck}([\mathbf {x}^\top ]_\gamma ;\mathbf {{R}}):=\) \(({\mathsf {GS}}.\mathsf {Com}_{ck}([x_1]_\gamma ;\mathbf {r}_1)||\cdots ||{\mathsf {GS}}.\mathsf {Com}_{ck}\) \(([x_n]_\gamma ;\mathbf {r}_n))\), where \(\mathbf {{R}}=(\mathbf {r}_1||\cdots ||\mathbf {r}_n)\in \mathbb {Z}_q^{2\times n}\).

The language of correct shuffles under public key \([\mathbf {v}]_2\in \mathbb {G}^2_2\) can can be defined as

where \(\mathcal {S}_n\) is the set of permutation matrices of size \(n\times n\).

6.1 Our Construction

Our proof system builds on a proof that a set of GS commitments open to elements in the set \(S=\{[s_1]_1,\ldots ,[s_n]_1\}\), where \(\mathbf {s}:=(s_1,\ldots ,s_n)^\top \leftarrow \mathcal {D}_{n,1}\) and the \(\mathcal {D}_{n,1}\text {-}\mathsf {KerMDH}\) Assumption holds in \(\mathbb {G}_1\). Given \([\mathbf {{F}}]_1\in \mathbb {G}_1^{2\times n}\), where the ith column is \([\mathbf {f}_i]_1\leftarrow {\mathsf {GS}}.\mathsf {Com}([x_i]_1)\), let \(\mathbf {x}:=({x}_1,\ldots ,{x}_n)^\top =\mathbf {{P}}\mathbf {s}\), for some permutation matrix \(\mathbf {{P}}\). Given a commitment to \([y]_1:=[\mathbf {s}^\top ]_1{\varvec{\delta }}\), we prove that \(([\mathbf {{C}}]_2,[\mathbf {{D}}]_2)\in \mathcal {L}_{[\mathbf {v}]_2,n,\mathsf {shuffle}}\) as follows: (a) show that \([\mathbf {{F}}]_1\in \mathcal {L}_{ck,S}^n\), where \(ck\leftarrow {\mathsf {GS}}.\mathsf {K}({gk})\); (b) give a GS proof for the satisfiability of \(\sum _{i\in [n]}[s_i]_1-\sum _{j\in [n]}[{x}_j]_1=[0]_1\); (c) give a GS proof for the satisfiability of \( [\mathbf {x}^\top ]_1[\mathbf {{C}}^\top ]_2-[\mathbf {s}^\top ]_1[\mathbf {{D}}^\top ]_2=[y]_1[\mathbf {v}^\top ]_2. \)

Soundness Intuition. Conditions (a) and (b) imply that \(\mathbf {x}\) is a permutation of \(\mathbf {s}\) or equivalently, \(\mathbf {{x}}=\mathbf {{P}}\mathbf {s}\) and \(\mathbf {{P}}\) is a permutation matrix. Note that \(\mathbf {{P}}\) is a permutation matrix iff \(\mathbf {{P}}\) is a binary matrix and for each row and column there is at most one 1. Let’s see in more detail why \(\mathbf {x}\) is a permutation of \(\mathbf {s}\). Condition (a) implies that each \(x_i\) is an element from \(\{s_1,\ldots ,s_n\}\), which can be written as \(\mathbf {x}=\mathbf {{P}}\mathbf {s}\), \(\mathbf {{P}}\in \{0,1\}^{n\times n}\), where each row of \(\mathbf {{P}}\) has at most one 1. But, given that there might be repeated elements, there might be also more than one 1 in some column of \(\mathbf {{P}}\). For example, if \(S=\{s_1,s_2,s_3\}\), it may be that but also . Condition (b) implies that there are no repeated \(x_i\)s unless one can break the \(\mathcal {D}_{n,1}\text {-}\mathsf {KerMDH}\) assumption. Indeed, there are repeated \(x_i\)s iff \((1,\ldots ,1)\mathbf {{P}}\) (the row vector of “frequencies” of \(\mathbf {x}\), which in the first example is (1, 1, 1) and in the second (0, 1, 2)) is not equal to \( (1,\ldots ,1)\). Given that (b) is equivalent to \(((1,\ldots ,1)-(1,\ldots ,1)\mathbf {{P}})[\mathbf {s}]_1=[0]_1\), then \(((1,\ldots ,1)-(1,\ldots ,1)\mathbf {{P}})^\top \) is a solution to the \(\mathcal {D}_{n,1}\text {-}\mathsf {KerMDH}\) problem. We conclude that \(\mathbf {{P}}\) is a permutation matrix and thus \(\mathbf {x}\) is a permutation of \(\mathbf {s}\).

The remainder of the proof follows essentially the proof from [10]. Suppose that \([\mathbf {{C}}]_2=\mathsf {Enc}_{[\mathbf {v}]_2}([\mathbf {{m}}^\top ]_2)\) and \([\mathbf {{C}}]_2=\mathsf {Enc}_{[\mathbf {v}]_2}([\mathbf {{n}}^\top ]_2)\). Let \(\mathbf {k}=(-v_2/v_1,1)^\top \) the “decryption key” (i.e. \(\mathbf {v}^\top \mathbf {k}=0\) and \((0,1)\mathbf {k}=1\))^{Footnote 5}. We multiply by \(\mathbf {{k}}\) on the right the equation from condition (c) to “decrypt” \([\mathbf {{C}}]_2\) and \([\mathbf {{D}}]_2\). We get that \([\mathbf {s}^\top ]_1\mathbf {{P}}^\top [\mathbf {{m}}]_2-[\mathbf {s}^\top ]_1[\mathbf {{n}}]_2=[0]_T\), which implies that \(\mathbf {{P}}^\top [\mathbf {{m}}]_2=[\mathbf {{n}}]_2\) unless \(\mathbf {{P}}^\top [\mathbf {{m}}]_2-[\mathbf {{n}}]_2\) is a solution to the \(\mathcal {D}_{n,1}\text {-}\mathsf {KerMDH}\). Finally this implies that \([\mathbf {{C}}]_2\mathbf {{P}}-[\mathbf {{D}}]_2\) is an encryption of \([\mathbf {{0}}_{n\times 1}]_2\) and thus \(([\mathbf {{C}}]_2,[\mathbf {{D}}]_2)\in \mathcal {L}_{[\mathbf {v}]_2,n,\mathsf {shuffle}}\).

A detailed description and the proof of security of our construction can be found in the full version.

We want to prove that a GS commitment \([\mathbf {c}]_1\) opens to some integer y in the range \([0,2^n-1]\). That is, construct a NIZK proof system for the language

where \(ck:=([\mathbf {u}_1]_1,[\mathbf {u}_2]_1)\leftarrow {\mathsf {GS}}.\mathsf {K}(1^\lambda )\). Our proof is as follows: (a) commit to \(y_1,\ldots y_\ell \), (b) show that \(y_i\in [0,d-1]\), for each \(i\in [\ell ]\), (c) show that \(y=\sum _{i\in [\ell ]}y_id^{i-1}\). Given that it must hold that \(\ell =n/\log d\), the total size of the proof is \(\mathsf {S}_{[0,d-1]}(\ell )+\varTheta (\ell )\), where \(\mathsf {S}_{[0,d-1]}(\ell )\) is the size of \(\ell \) Range Proofs in the interval \([0,d-1]\).

7.1 Our Construction

Note that (b) is equivalent to show that \(({\mathsf {GS}}.\mathsf {Com}_{ck}(y_1)||\cdots ||{\mathsf {GS}}.\mathsf {Com}_{ck}(y_\ell ))\in \mathcal {L}_{ck,[0,d-1]}^\ell \). Thus, using the proof system from Sect. 5 we are able to aggregate \(\ell \) Range Proofs in the interval \([0,d-1]\) into a single proof of size \(\varTheta (\log d)\). Choosing \(d=n^k\) we get that \(\mathsf {S}_{[0,d-1]}(\ell )=\varTheta (k\log n)\) and \(\ell =n/\log n^k=\frac{n}{k\log n}\), and thus the size of our Range Proof is \(\varTheta (\frac{n}{k\log n})\) for an arbitrarily chosen \(k\in \mathbb {N}\). One would be tempted to choose \(d=2^{\sqrt{n}}\) to obtain a proof of size \(\varTheta (\sqrt{n})\). However, the proof system from Sect. 5 requires membership in \(\mathcal {L}_{ck,[0,d-1]}\) to be efficiently testable, which seems to be infeasible as when \(d=2^{\sqrt{n}}\).

A detailed description and the security proofs of our proof system can be found in the full version.