Efficient Culpably Sound NIZK Shuffle Argument Without Random Oracles

Abstract

One way to guarantee security against malicious voting servers is to use NIZK shuffle arguments. Up to now, only two NIZK shuffle arguments in the CRS model have been proposed. Both arguments are relatively inefficient compared to known random oracle based arguments. We propose a new, more efficient, shuffle argument in the CRS model. Importantly, its online prover’s computational complexity is dominated by only two $(n + 1)$-wide multi-exponentiations, where n is the number of ciphertexts. Compared to the previously fastest argument by Lipmaa and Zhang, it satisfies a stronger notion of soundness.

1 Introduction

A mix network, or mix-net, is a network of mix-servers designed to remove the link between ciphertexts and their senders. To achieve this goal, a mix-server of a mix-net initially obtains a list of ciphertexts $(z_i)_{i = 1}^n$. It then re-randomizes and permutes this list, and outputs the new list $(z^\prime _i)_{i = 1}^n$ together with a non-interactive zero knowledge (NIZK, [2]) shuffle argument [22] that proves the re-randomization and permutation was done correctly, without leaking any side information. If $\mathsf {enc}$ is a multiplicatively homomorphic public-key cryptosystem like Elgamal [7], a shuffle argument convinces the verifier that there exists a permutation $\psi$ and a vector t of randomizers such that $z^\prime _i = z_{\psi (i)} \cdot \mathsf {enc}_{\mathsf {pk}} (1; t_i)$, without revealing any information about $\psi$ or t. Mix-nets improve security against malicious voting servers in e-voting. Other applications of mix-nets include anonymous web browsing, payment systems, and secure multiparty computation.

It is important to have a non-interactive shuffle argument outputting a short bit string that can be verified by anybody (possibly years later) without interacting with the prover. Many NIZK shuffle arguments are known in the random oracle model, see for example [9, 10, 13, 20, 23]. Since the random oracle model is only a heuristic, it is strongly recommended to construct NIZK arguments in the common reference string (CRS) model [2], without using random oracles.¹ We note that the most efficient shuffle arguments in the random oracle model like [13] also require a CRS.

Up to now, only two NIZK shuffle arguments in the CRS model have been proposed, by Groth and Lu [15] and Lipmaa and Zhang [18, 19], both of which are significantly slower than the fastest arguments in the random oracle model (see Table 1). The Groth-Lu shuffle argument only provides culpable soundness [15, 16] in the sense that if a malicious prover can create an accepting shuffle argument for an incorrect statement, then this prover together with a party that knows the secret key can break the underlying security assumptions. Relaxation of the soundness property is unavoidable, since [1] showed that only languages in $\mathbf {P/poly}$ can have direct black-box adaptive perfect NIZK arguments under a (polynomial) cryptographic hardness assumption. If the underlying cryptosystem is IND-CPA secure, then the shuffle language is not in $\mathbf {P/poly}$, and thus it is necessary to use knowledge assumptions [5] to prove its adaptive soundness. Moreover, [15] argued that culpable soundness is a sufficient security notion for shuffles, since in any real-life application of the shuffle argument there exists some coalition of parties who knows the secret key.

Lipmaa and Zhang [18] proposed a more efficient NIZK shuffle argument by using knowledge assumptions under which they also bypassed the impossibility result of [1] and proved that their shuffle argument is sound. However, their shuffle argument is sound only under the assumption that there is an extractor that has access to the random coins of all encrypters, e.g., all voters, allowing her to extract all plaintexts and randomizers. We say in this case that the argument is white-box sound. White-box soundness is clearly a weaker security notion than culpable soundness of [15], and it would be good to avoid it.

In addition, the use of knowledge assumptions in [18] forces the underlying BBS [4] cryptosystem to include knowledge components (so ciphertexts are twice as long) and be lifted (meaning that one has to solve discrete logarithm to decrypt, so plaintexts must be small). Thus, one has to use a random oracle-less range argument to guarantee that the plaintexts are small and thus to guarantee the soundness of the shuffle argument (see [18] for a discussion). While range proofs only have to be verified once (e.g., by only one mix-server), this still means that the shuffle argument of [18] is somewhat slower than what is given in Table 1. Moreover, in the case of e-voting, using only small plaintexts restricts the applicability of a shuffle argument to only certain voting mechanisms like majority. On the other hand, a mechanism such as Single Transferable Vote would likely be unusable due to the length of the ballots.

Table 1 provides a brief comparison between known NIZK shuffle arguments in the CRS model and the most computationally efficient known shuffle argument in the random oracle model [13]. We emphasize that the values in parentheses show the cost of computing and communicating the shuffled ciphertexts themselves, and must be added to the rest. Moreover, the cost of the shuffle argument from [18] should include the cost of a range argument. Unless written otherwise, the communication and the CRS length are given in group elements, the prover’s computational complexity is given in exponentiations, and the verifier’s computational complexity is given in bilinear pairings. In each row, highlighted cells denote the best efficiency or best security (e.g., not requiring the PKE assumption) among arguments in the CRS model. Of course, a full efficiency comparison can only be made after implementing the different shuffle arguments.

This brings us to the main question of the current paper:

Is it possible to construct an NIZK shuffle argument in the CRS model that is comparable in efficiency with existing random oracle model NIZK shuffle arguments? Moreover, can one do it while minimizing the use of knowledge assumptions (i.e., not requiring the knowledge extractor to have access to the random coins used by all encrypters) and using a standard, non-lifted, cryptosystem?

Table 1. A comparison of different NIZK shuffle arguments, compared with the computationally most efficient known shuffle argument in the random oracle model [13].

Our Contributions. We give a partial answer to the main question. We propose a new pairing-based NIZK shuffle argument in the CRS model. Differently from [18], we prove the culpable soundness of the new argument instead of white-box soundness. Compared to [15], which also achieves culpable soundness, the new argument has 3 times faster proving and more than 4 times faster verification. Compared to [15, 18], it is based on a more standard cryptosystem (Elgamal). While the new shuffle argument is still at least 2 times slower than the most efficient known random oracle based shuffle arguments, it has almost optimal online prover’s computation. Of course, a full efficiency comparison can only be made after implementing the different shuffle arguments.

Our construction works as follows. We first commit to the permutation $\psi$ (by committing separately to first $n - 1$ rows of the corresponding permutation matrix $\mathbf {\varPsi }$) and to the vector t of blinding randomizers. Here, we use the polynomial commitment scheme (see Sect. 2) with $\mathsf {com}(\mathsf {ck}; {{\varvec{m}}}; r) = (g_1, g_2^{\gamma })^{r P_0 (\chi ) + \sum _{i = 1}^n m_i P_i (\chi )} \in \mathbb {G}_1 \times \mathbb {G}_2$, in pairing-based setting, where $\hat{e}: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T$ is a bilinear pairing, $g_i$ is a generator of $\mathbb {G}_i$ for $i \in \{1, 2\}$, $(P_i (X))_{i = 0}^n$ is a tuple of linearly independent polynomials, $\chi$ is a trapdoor, $\gamma$ is a knowledge secret, and $\mathsf {ck}= ((g_1, g_2^{\gamma })^{P_i (\chi )})_{i = 0}^n$ is the CRS. For different values of $P_i (X)$, variants of this commitment scheme have been proposed before [12, 14, 17].

We show that $\mathbf {\varPsi }$ is a correct permutation matrix by constructing n witness-indistinguishable succinct unit vector arguments, each of which guarantees that a row of $\mathbf {\varPsi }$ is a unit vector, for implicitly constructed $\mathbf {\varPsi }_n = \mathbf {1_n} - \sum _{i = 1}^{n - 1} \mathbf {\varPsi }_i$. We use the recent square span programs (SSP, [6]) approach to choose the polynomials $P_i (X) = y_{i} (X)$ so that the unit vector argument is efficient. Since unit vectors are used in many contexts, we hope this argument is of independent interest.

After that, we postulate a natural concrete verification equation for shuffles, and construct the shuffle argument from this. If privacy were not an issue (and thus $z^\prime _i = z_{\psi (i)}$ for every i), the verification equation would just be the tautology $\prod _{i = 1}^n \hat{e}(z'_i, g_2^{y_{i} (\chi )}) =^? \prod _{i = 1}^n \hat{e}(z_i, g_2^{y_{\psi ^{-1} (i)} (\chi )})$. Clearly, if the prover is honest, this equation holds. However, it does not yet guarantee soundness, since an adversary can use $g_1^{y_{j} (\chi )}$ (given in the CRS) to create $(z^\prime _i)_{i = 1}^n$ in a malicious way. To eliminate this possibility, by roughly following an idea from [15], we also verify that $\prod _{i = 1}^n \hat{e}(z'_i, g_2^{\hat{y}_{i} (\chi )}) =^? \prod _{i = 1}^n \hat{e}(z_i, g_2^{\hat{y}_{\psi ^{-1} (i)} (\chi )})$ for some well-chosen polynomials $\hat{y}_{i} (X)$. (We note that instead of n univariate polynomials, [15] used n random variables $\chi _i$, increasing the size of the secret key to $\varOmega (n)$ bits.)

To show that the verifications are instantiated correctly, we also need a same-message argument that shows that commitments w.r.t. two tuples of polynomials $(y_{i} (X))_{i = 1}^n$ and $(\hat{y}_{i} (X))_{i = 1}^n$ commit to the same plaintext vectors. We construct an efficient same-message argument by using an approach that is (again, roughly) motivated by the QAP-based approach of [11]. This argument is an argument of knowledge, given that the polynomials $\hat{y}_{i} (X)$ satisfy an additional restriction.

Since we also require privacy, the actual verification equations are more complicated. In particular, $z^\prime _i = z_{\psi (i)} \cdot \mathsf {enc}_{\mathsf {pk}} (1; t_i)$, and (say) $g_2^{y_{\psi ^{-1} (i)} (\chi )}$ is replaced by the second element $g_2^{\gamma (r_i y_{0} (\chi ) + y_{\psi ^{-1} (i)} (\chi ))}$ of a commitment to $\mathbf {\varPsi }_i$. The resulting complication is minor (it requires one to include into the shuffle argument a single ciphertext $U \in \mathbb {G}_1^2$ that compensates for the added randomness). The full shuffle argument consists of commitments to $\mathbf {\varPsi }$ and to t (both committed twice, w.r.t. the polynomials $(y_{i} (X))_{i = 0}^n$ and $(\hat{y}_{i} (X))_{i = 0}^n$), n unit vector arguments (one for each row of $\mathbf {\varPsi }$), $n - 1$ same-message arguments, and finally U.

If $\hat{y}_{i} (X)$ are well-chosen, then from the two verification equations and the soundness of the unit vector and same-message arguments it follows, under a new computational assumption PSP (Power Simultaneous Product, related to an assumption from [15]), that $z^\prime _i = z_{\psi (i)}$ for every i.

We prove culpable soundness [15, 16] of the new argument. Since the security of the new shuffle argument does not depend on the cryptosystem either having knowledge components or being lifted, we can use Elgamal encryption [7] instead of the non-standard knowledge BBS encryption introduced in [18]. Since the cryptosystem does not have to be lifted, one can use more complex voting mechanisms with more complex ballots. The use of knowledge assumptions means that the new argument is an argument of knowledge.

The new shuffle argument can be largely precomputed by the prover and forwarded to the verifier even before the common input (i.e., ciphertexts) arrive. Similarly, the verifier can perform a large part of verification before receiving the ciphertexts. (See [24] for motivation for precomputation.) The prover’s computation in the online phase is dominated by just two $(n + 1)$-wide multi-exponentiations (the computation of U). The multi-exponentiations can be parallelized; this is important in practice due to the wide availability of highly parallel graphics processors.

Main Technical Challenges. While the main objective of the current work is efficiency, we emphasize that several steps of the new shuffle argument are technically involved. Throughout the paper, we use and combine very recent techniques from the design of efficient succinct non-interactive arguments of knowledge (SNARKs, [6, 11, 21], that are constructed with the main goal of achieving efficient verifiable computation) with quite unrelated techniques from the design of efficient shuffle arguments [15, 18].

The security of the new shuffle argument relies on a new assumption, PSP. We prove that PSP holds in the generic bilinear group model, given that polynomials $\hat{y}_{i} (X)$ satisfy a very precise criterion. For the security of the SSP-based unit vector argument, we need $y_{i} (X)$ to satisfy another criterion, and for the security of the same-message argument, we need $y_{i} (X)$ and $\hat{y}_{i} (X)$ to satisfy a third criterion. The fact that polynomials $y_{i} (X)$ and $\hat{y}_{i} (X)$ that satisfy all three criteria exist is not a priori clear; $y_{i} (X)$ and $\hat{y}_{i} (X)$ (see Proposition 3) are also unlike any polynomials from the related literature on non-interactive zero knowledge.

Finally, the PSP assumption was carefully chosen so it will hold in the generic bilinear group model, and so the reduction from culpable soundness of the shuffle argument to the PSP assumption would work. While the PSP assumption is related to the SP assumption from [15], the situation in [15] was less fragile due to the use of independent random variables $X_i$ and $X_i^2$ instead of polynomials $y_{i} (X)$ and $\hat{y}_{i} (X)$. In particular, the same-message argument is trivial in the case of using independent random variables.

Due to lack of space, several proofs and other details are given in the full version, [8].

2 Preliminaries

Let n be the number of ciphertexts to be shuffled. Let $S_{d}$ be the symmetric group of d elements. Let $\mathbb {G}^*$ denote the group $\mathbb {G}$ without its identity element. For $a \le b$, let $[a \, .. \, b] := \{c \in \mathbb {Z}: a \le c \le b\}$. Denote $(a, b)^c := (a^c, b^c)$. For a set of polynomials $\mathcal {F}$ that have the same domain, denote $g^{\mathcal {F}(\mathbf {a})} := (g^{f (\mathbf {a})})_{f \in \mathcal {F}}$.

A permutation matrix is a Boolean matrix with exactly one 1 in every row and column. If $\psi$ is a permutation then the corresponding permutation matrix $\mathbf {\varPsi }_\psi$ is such that $(\mathbf {\varPsi }_\psi )_{i j} = 1$ iff $j = \psi (i)$. Thus $(\mathbf {\varPsi }_{\psi ^{-1}})_{i j} = 1$ iff $i = \psi (j)$. Clearly, $\mathbf {\varPsi }$ is a permutation matrix iff its every row is a unit vector, and the sum of all its row vectors is equal to the all-ones vector $\mathbf {1}_n$.

Let $\kappa$ be the security parameter. We denote $f (\kappa ) \approx _\kappa g (\kappa )$ if $|f (\kappa ) - g (\kappa )|$ is negligible in $\kappa$. We abbreviate (non-uniform) probabilistic-polynomial time by (NU)PPT. On input $1^\kappa$, a bilinear map generator $\mathsf {BP}$ returns $(p, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, \hat{e})$, where $\mathbb {G}_1$, $\mathbb {G}_2$ and $\mathbb {G}_T$ are multiplicative cyclic groups of prime order p, and $\hat{e}$ is an efficient bilinear map $\hat{e}:\mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T$ that satisfies the following two properties, where $g_1$ (resp., $g_2$) is an arbitrary generator of $\mathbb {G}_1$ (resp., $\mathbb {G}_2$): (i) $\hat{e}(g_1, g_2) \ne 1$, and (ii) $\hat{e}(g_1^a, g_2^b) = \hat{e}(g_1, g_2)^{a b}$. Thus, $\hat{e}(g_1^a, g_2^b) = \hat{e}(g_1^c, g_2^{d})$ iff $a b \equiv c d \pmod {p}$. We give $\mathsf {BP}$ another input, n (related to the input length), and allow p to depend on n. Finally, we assume that all algorithms that handle group elements reject if their inputs do not belong to corresponding groups.

We will now give short explanations of the main knowledge assumptions. Let $1 < d (n) < d^* (n) = {\text {poly}}(\kappa )$ be two functions. We say that $\mathsf {BP}$ is

• d (n)-PDL (Power Discrete Logarithm, [17]) secure if any NUPPT adversary, given values $((g_1, g_2)^{\chi ^i})_{i = 0}^{d (n)}$, has negligible probability of producing $\chi$.

• $(d (n), d^* (n))$ -PCDH (Power Computational Diffie-Hellman, [11, 12, 14]) secure if any NUPPT adversary, given values $((g_1, g_2)^{\chi ^ i})_{i \in [0 \, .. \, d^* (n)] \setminus \{d (n) + 1\}}$, has negligible probability of producing $g_1^{\chi ^{d (n) + 1}}$.

• d (n)-TSDH (Target Strong Diffie-Hellman, [3, 21]) secure if any NUPPT adversary, given values $((g_1, g_2)^{\chi ^i})_{i = 0}^{d (n)}$, has negligible probability of producing a pair of values $\left( r, \hat{e}(g_1, g_2)^{1 / (\chi - r)}\right)$ where $r \ne \chi$.

For algorithms $\mathsf {A}$ and $X_\mathsf {A}$, we write $(y; y') \leftarrow (\mathsf {A}|| X_{\mathsf {A}}) (\chi )$ if $\mathsf {A}$ on input $\chi$ outputs y, and $X_{\mathsf {A}}$ on the same input (including the random tape of $\mathsf {A}$) outputs $y'$ [1]. We will need knowledge assumptions w.r.t. up to 2 knowledge secrets $\gamma _i$. Let m be the number of different knowledge secrets in any concrete argument, in the current paper $m \le 2$. Let $\mathcal {F}= (P_i)_{i = 0}^n$ be a tuple of univariate polynomials, and $\mathcal {G}_1$ (resp., $\mathcal {G}_2$) be a tuple of univariate (resp., m-variate) polynomials. For $i \in [1 \, .. \, m]$, $\mathsf {BP}$ is $(\mathcal {F}, \mathcal {G}_1, \mathcal {G}_2, \gamma _i)$ -PKE (Power Knowledge of Exponent, [14]) secure if for any NUPPT adversary $\mathsf {A}$ there exists a NUPPT extractor $X_{\mathsf {A}}$, such that

$$ \Pr \left[ \begin{aligned}&\mathsf {gk}\leftarrow \mathsf {BP}(1^\kappa , n), (g_1, g_2, \chi ) \leftarrow _r\mathbb {G}_1^* \times \mathbb {G}_2^* \times \mathbb {Z}_p, \mathbf {\gamma } \leftarrow _r\mathbb {Z}_p^m, \\ {}&\mathbf {\gamma _{-i}} = (\gamma _1, \dots , \gamma _{i - 1}, \gamma _{i + 1}, \dots , \gamma _m), \mathsf {aux}\leftarrow \left( g_1^{\mathcal {G}_1 (\chi )}, g_2^{\mathcal {G}_2 (\chi , \mathbf {\gamma _{-i}})}\right) , \\ {}&(h_1, h_2; (a_i)_{i = 0}^n) \leftarrow (\mathsf {A}|| X_{\mathsf {A}}) (\mathsf {gk}; (g_1, g_2^{\gamma _i})^{\mathcal {F}(\chi )}, \mathsf {aux}): \\ {}&\textstyle \hat{e}(h_1, g_2^{\gamma _i}) = \hat{e}(g_1, h_2) \wedge h_1 \ne g_1^{\sum _{i = 0}^n a_i P_i (\chi )} \end{aligned} \right] \approx _\kappa 0. $$

The definition implies that $\mathsf {aux}$ may depend on $\mathbf {\gamma _{-i}}$ but not on $\gamma _i$. If $\mathcal {F}= (X^i)_{i = 0}^{d}$ for some $d = d (n)$, then we replace the first argument in $(\mathcal {F}, \dots )$-PKE with d. If $m = 1$, then we omit the last argument $\gamma _i$ in $(\mathcal {F}, \dots , \gamma _i)$-PKE.

We will use the Elgamal cryptosystem [7] $\Pi = (\mathsf {BP}, \mathsf {genpkc}, \mathsf {enc}, \mathsf {dec})$, defined as follows, in the bilinear setting.

• Setup ( $1^\kappa$ ): Let $\mathsf {gk}\leftarrow (p, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, \hat{e}) \leftarrow \mathsf {BP}(1^\kappa )$.

• Key Generation $\mathsf {genpkc}(\mathsf {gk})$ : Let $g_1 \leftarrow _r\mathbb {G}_1^*$. Set the secret key $\mathsf {sk}\leftarrow _r\mathbb {Z}_p$, and the public key $\mathsf {pk}\leftarrow (g_1, h = g_1^{\mathsf {sk}})$. Output $(\mathsf {pk}, \mathsf {sk})$.

• Encryption $\mathsf {enc}_{\mathsf {pk}} (m; r)$ : To encrypt a message $m \in \mathbb {G}_1$ with randomizer $r \in \mathbb {Z}_p$, output the ciphertext $\mathsf {enc}_{\mathsf {pk}} (m; r) = \mathsf {pk}^r \cdot (1, m) = (g^r, m h^r)$.

• Decryption $\mathsf {dec}_{\mathsf {sk}} (c_1, c_2)$ : $m = c_2 / c_1^{\mathsf {sk}} = m h^r / h^r = m$.

Elgamal is clearly multiplicatively homomorphic. In particular, if $t \leftarrow _r\mathbb {Z}_p$, then for any m and r, $\mathsf {enc}_{\mathsf {pk}} (m; r) \cdot \mathsf {enc}_{\mathsf {pk}} (1; t) = \mathsf {enc}_{\mathsf {pk}} (m; r + t)$ is a random encryption of m. Elgamal is IND-CPA secure under the XDH assumption.

An extractable trapdoor commitment scheme consists of two efficient algorithms $\mathsf {gencom}$ (that outputs a CRS and a trapdoor) and $\mathsf {com}$ (that, given a CRS, a message and a randomizer, outputs a commitment), and must satisfy the following four security properties. Computational binding: without access to the trapdoor, it is intractable to open a commitment to two different messages. Trapdoor: given access to the original message, the randomizer and the trapdoor, one can open the commitment to any other message. Perfect hiding: commitments of any two messages have the same distribution. Extractable: given access to the CRS, the commitment, and the random coins of the committer, one can obtain the value that the committer committed to.

We use the following extractable trapdoor polynomial commitment scheme that generalizes various earlier commitment schemes [12, 14, 17]. Let $n = {\text {poly}}(\kappa )$, $n > 0$, be an integer. Let $P_i (X) \in \mathbb {Z}_p [X]$, for $i \in [0 \, .. \, n]$, be $n + 1$ linearly independent low-degree polynomials. First, $\mathsf {gencom}(1^\kappa , n)$ generates $\mathsf {gk}\leftarrow \mathsf {BP}(1^\kappa , n)$, picks $g_1 \leftarrow _r\mathbb {G}_1^*$, $g_2 \leftarrow _r\mathbb {G}_2^*$, and then outputs the CRS $\mathsf {ck}\leftarrow ((g_1^{P_i (\chi )}, g_2^{\gamma P_i (\chi )})_{i = 0}^n)$ for $\chi \leftarrow _r\mathbb {Z}_p \setminus \{j: P_0 (j) = 0\}$ and $\gamma \leftarrow _r\mathbb {Z}_p$. The trapdoor is equal to $\mathsf {td}_{\mathsf {com}} = \chi$.

The commitment of $\mathbf {a} \in \mathbb {Z}_p^n$, given a randomizer $r \leftarrow _r\mathbb {Z}_p$, is $\mathsf {com}(\mathsf {ck}; \mathbf {a}; r) := (g_1^{P_0 (\chi )}, g_2^{\gamma P_0 (\chi )})^r \cdot \prod _{i = 1}^n (g_1^{P_i (\chi )}, g_2^{\gamma P_i (\chi )})^{a_i} \in \mathbb {G}_1 \times \mathbb {G}_2$. The validity of a commitment $(A_1, A_2^{\gamma })$ can be checked by verifying that $\hat{e}(A_1, g_2^{\gamma P_0 (\chi )}) = \hat{e}(g_1^{P_0 (\chi )}, A_2^{\gamma })$. To open a commitment, the committer sends $(\mathbf {a}, r)$ to the verifier.

Theorem 1

Denote $\mathcal {F}_{\mathsf {com}}= (P_i (X))_{i = 0}^n$. The polynomial commitment scheme is perfectly hiding and trapdoor. Let $d := \max _{f \in \mathcal {F}_{\mathsf {com}}} (\deg f)$. If $\mathsf {BP}$ is d-PDL secure, then it is computationally binding. If $\mathsf {BP}$ is $(\mathcal {F}_{\mathsf {com}}, \emptyset , \emptyset )$-PKE secure, then it is extractable.

Alternatively, we can think of $\mathsf {com}$ as being a commitment scheme that does not depend on the concrete polynomials at all, and the description of $P_i$ is just given as a part of $\mathsf {ck}$. We instantiate the polynomial commitment scheme with concrete polynomials later in Sects. 3 and 6.

An NIZK argument for a group-dependent language $\mathcal {L}$ consists of four algorithms, $\mathsf {setup}$, $\mathsf {gencrs}$, $\mathsf {pro}$ and $\mathsf {ver}$. The setup algorithm $\mathsf {setup}$ takes as input $1^\kappa$ and n (the input length), and outputs the group description $\mathsf {gk}$. The CRS generation algorithm $\mathsf {gencrs}$ takes as input $\mathsf {gk}$ and outputs the prover’s CRS $\mathsf {crs}_p$, the verifier’s CRS $\mathsf {crs}_v$, and a trapdoor $\mathsf {td}$. ($\mathsf {td}$ is only required when the argument is zero-knowledge.) The distinction between $\mathsf {crs}_p$ and $\mathsf {crs}_v$ is only important for efficiency. The prover $\mathsf {pro}$ takes as input $\mathsf {gk}$ and $\mathsf {crs}_p$, a statement u, and a witness w, and outputs an argument $\pi$. The verifier $\mathsf {ver}$ takes as input $\mathsf {gk}$ and $\mathsf {crs}_v$, a statement u, and an argument $\pi$, and either accepts or rejects.

Some of the properties of an argument are: (i) perfect completeness (honest verifier always accepts honest prover’s argument), (ii) perfect witness-indistinguishability (argument distributions corresponding to all allowable witnesses are equal), (iii) perfect zero knowledge (there exists an efficient simulator that can, given u, $(\mathsf {crs}_p, \mathsf {crs}_v)$ and $\mathsf {td}$, output an argument that comes from the same distribution as the argument produced by the prover), (iv) adaptive computational soundness (if $u \not \in \mathcal {L}$, then an arbitrary non-uniform probabilistic polynomial time prover has negligible success in creating a satisfying argument), and (v) adaptive computational culpable soundness [15, 16] (if $u \not \in \mathcal {L}$, then an arbitrary NUPPT prover has negligible success in creating a satisfying argument together with a witness that $u \not \in \mathcal {L}$). An argument is an argument of knowledge, if from an accepting argument it follows that the prover knows the witness.

3 Unit Vector Argument

In a unit vector argument, the prover aims to convince the verifier that he knows how to open a commitment $(A_1, A_2^{\gamma })$ to some $(\mathbf {e}_I, r)$, where $\mathbf {e}_I$ denotes the Ith unit vector for $I \in [1 \, .. \, n]$. We construct the unit vector argument by using square span programs (SSP-s, [6], an especially efficient variant of the quadratic arithmetic programs of [11]).

Clearly, $\mathbf {a} \in \mathbb {Z}_p^n$ is a unit vector iff the following $n + 1$ conditions hold:

• $a_i \in \{0, 1\}$ for $i \in [1 \, .. \, n]$ (i.e., $\mathbf {a}$ is Boolean), and

• $\sum _{i = 1}^n a_i = 1$.

We use the methodology of [6] to obtain an efficient NIZK argument out of these conditions. Let $\{0, 2\}^{n + 1}$ denote the set of $(n + 1)$-dimensional vectors where every coefficient is from $\{0, 2\}$, let $\circ$ denote the Hadamard (entry-wise) product of two vectors, let and . Clearly, the above $n + 1$ conditions hold iff $V \mathbf {a} + \mathbf {b} \in \{0, 2\}^{n + 1}$, i.e.,

$$\begin{aligned} (V \mathbf {a} + \mathbf {b} - \mathbf {1}_{n + 1}) \circ (V \mathbf {a} + \mathbf {b} - \mathbf {1}_{n + 1}) = \mathbf {1}_{n + 1}. \end{aligned}$$

(1)

Let $\omega _i$, $i \in [1 \, .. \, n + 1]$ be $n + 1$ different values. Let $Z (X) := \prod _{i = 1}^{n + 1} (X - \omega _i)$ be the unique degree $n + 1$ monic polynomial, such that $Z (\omega _i) = 0$ for all $i \in [1 \, .. \, n + 1]$. Let the ith Lagrange basis polynomial $\ell _i (X) := \prod _{i, j \in [1 \, .. \, n + 1],\begin{array}{c} j \end{array} \ne i} ((X - \omega _j) / (\omega _i - \omega _j))$ be the unique degree n polynomial, s.t. $\ell _i (\omega _i) = 1$ and $\ell _i (\omega _j) = 0$ for $j \ne i$. For a vector $\mathbf {x} \in \mathbb {Z}_p^{n + 1}$, let $L_{\mathbf {x}} (X) = \sum _{i = 1}^{n + 1} x_i \ell _i (X)$ be a degree n polynomial that interpolates $\mathbf {x}$, i.e., $L_{\mathbf {x}} (\omega _i) = x_i$.

For $i \in [1 \, .. \, n]$, let $y_{i} (X)$ be the polynomial that interpolates the ith column of the matrix V. That is, $y_{i} (X) = 2 \ell _i (X) + \ell _{n + 1} (X)$ for $i \in [1 \, .. \, n]$. Let $y_{0} (X) = -1 + \ell _{n + 1} (X)$ be the polynomial that interpolates $\mathbf {b} - \mathbf {1}_{n + 1}$. We will use an instantiation of the polynomial commitment scheme with $\mathcal {F}_{\mathsf {com}}= (Z (X), (y_{i} (X))_{i = 1}^{n})$.

As in [6], we arrive at the polynomial $Q (X) = (\sum _{i = 1}^n a_i y_{i} (X) + y_{0} (X))^2 - 1 = \left( y_{I} (X) + y_{0} (X)\right) ^2 - 1$ (here, we used the fact that $\mathbf {a} = \mathbf {e_I}$ for some $I \in [1 \, .. \, n]$), such that $\mathbf {a}$ is a unit vector iff $Z (X) \mid Q (X)$. As in [6, 11], to obtain privacy, we now add randomness to Q (X), arriving at the degree $2 (n + 1)$ polynomial $Q_{wi} (X) = \left( r Z (X) + y_{I} (X) + y_{0} (X)\right) ^2 - 1$. By [6, 11], Eq. (1) holds iff

• (i) $Q_{wi} (X) = (A (X) + y_{0} (X))^2 - 1$, where $A (X) = r_a Z (X) + \sum _{i = 1}^n a_i y_{i} (X) \in {\text {span}}(\mathcal {F}_{\mathsf {com}})$, and

• (ii) $Z (X) \mid Q_{wi} (X)$.

An honest prover computes the degree $\le n + 1$ polynomial $\pi _{wi} (X) \leftarrow Q_{wi} (X) / Z (X)\in \mathbb {Z}_p [X]$, and sets the argument to be equal to $\pi ^*_{uv} := g_1^{\pi _{wi} (\chi )}$ for a secret $\chi$ that instantiates X. If it exists, $\pi _{wi} (X) := Q_{wi} (X) / Z (X)$ is equal to $r^2 Z (X) + r \cdot 2 (y_{I} (X) + y_{0} (X)) + \Pi _I (X)$, where for $i \in [1 \, .. \, n]$, $\Pi _i (X) := ((y_{i} (X) + y_{0} (X))^2 - 1) / Z (X)$ is a degree $\le n - 1$ polynomial and $Z (X) \mid ((y_{i} (X) + y_{0} (X))^2 - 1)$. Thus, computing $\pi ^*_{uv}$ uses two exponentiations.

We use a knowledge (PKE) assumption in a standard way to guarantee that A (X) is in the span of $\{X^i\}_{i = 0}^{n + 1}$. As in [6, 11], we then guarantee condition (i) by using a PCDH assumption and condition (ii) by using a TSDH assumption. Here, we use the same technique as in [11] and subsequent papers by introducing an additional secret, $\beta$, and adding one group element $A_1^{\beta }$ to the argument.

• System parameters: Let $\mathsf {com}$ be the polynomial commitment scheme and let $\mathcal {F}_{\mathsf {com}}= (Z (X), (y_{i} (X))_{i = 1}^{n})$.

• Setup $\mathsf {setup}_{uv} (1^\kappa , n)$ : Let $\mathsf {gk}\leftarrow \mathsf {BP}(1^\kappa , n)$.

• CRS generation $\mathsf {gencrs}_{uv} (\mathsf {gk})$ : Let $(g_1, g_2, \chi , \beta , \gamma ) \leftarrow _r\mathbb {G}_1^* \times \mathbb {G}_2^* \times \mathbb {Z}_p^{3}$, s.t. $Z (\chi ) \ne 0$. Set $\mathsf {ck}\leftarrow (g_1, g_2^{\gamma })^{\mathcal {F}_{\mathsf {com}}(\chi )}$, $\mathsf {crs}_{uv, p} \leftarrow (\mathsf {ck}, (g_1^{2 (y_{i} (\chi ) + y_{0} (\chi ))}, g_1^{\Pi _i (\chi )})_{i = 1}^n, g_1^{\beta \cdot \mathcal {F}_{\mathsf {com}}(\chi )})$, $\mathsf {crs}_{uv, v} \leftarrow (g_1, g_1^{y_{0} (\chi )}, g_2^{\gamma }, g_2^{\gamma y_{0} (\chi )}, g_2^{\gamma Z (\chi )}, g_2^{\gamma \beta }, \hat{e}(g_1, g_2^{\gamma })^{-1})$. Return $\mathsf {crs}_{uv} = (\mathsf {crs}_{uv, p}, \mathsf {crs}_{uv, v})$.

• Common input: $(A_1, A_2^{\gamma }) = ((g_1, g_2^{\gamma })^{Z (\chi )})^r (g_1, g_2^{\gamma })^{y_{I} (\chi )}$ where $I \in [1 \, .. \, n]$.

• Proving $\mathsf {pro}_{uv} (\mathsf {gk}, \mathsf {crs}_{uv, p}; A_1, A_2^{\gamma }; w_{uv} = (\mathbf {a} = \mathbf {e_I}, r))$ : Set $\pi ^*_{uv} \leftarrow (g_1^{Z (\chi )})^{r^2} \cdot (g_1^{2 (y_{I} (\chi ) + y_{0} (\chi ))})^r \cdot g_1^{\Pi _I (\chi )}$. Set $A_1^{\beta } \leftarrow (g_1^{\beta Z (\chi )})^r g_1^{\beta y_{I} (\chi )}$. Output $\pi _{uv} = (\pi ^*_{uv}, A_1^{\beta }) \in \mathbb {G}_1^2$.

• Verification $\mathsf {ver}_{uv} (\mathsf {gk}, \mathsf {crs}_{uv, v}; A_1, A_2^{\gamma }; \pi _{uv})$ : Parse $\pi _{uv}$ as $\pi _{uv} = (\pi ^*_{uv}, A_1^{\beta })$. Verify that (1) $\hat{e}(\pi ^*_{uv}, g_2^{\gamma Z (\chi )}) = \hat{e}(A_1 \cdot g_1^{y_{0} (\chi )}, A_2^{\gamma } \cdot g_2^{\gamma y_{0} (\chi )}) \cdot \hat{e}(g_1, g_2^{\gamma })^{-1}$, (2) $\hat{e}(g_1, A_2^{\gamma }) = \hat{e}(A_1, g_2^{\gamma })$, and (3) $\hat{e}(A_1, g_2^{\gamma \beta }) = \hat{e}(A_1^{\beta }, g_2^{\gamma })$.

Set $\mathcal {F}_{uv, 1} = \{1\} \cup \mathcal {F}_{\mathsf {com}}\cup X_\beta \mathcal {F}_{\mathsf {com}}$ and $\mathcal {F}_{uv, 2} = Y \mathcal {F}_{\mathsf {com}}\cup \{Y, Y X_\beta \}$. The formal variable $X_\beta$ (resp., Y) stands for the secret key $\beta$ (resp., $\gamma$). Since other elements of $\mathsf {crs}_{uv}$ are only needed for optimization, $\mathsf {crs}_{uv}$ can be computed from $\mathsf {crs}^*_{uv} = (g_1^{\mathcal {F}_{uv, 1} (\chi , \beta )}, g_2^{\mathcal {F}_{uv, 2} (\chi , \beta , \gamma )})$. If $n > 2$ then $1 \not \in {\text {span}}(\{Z (X)\} \cup \{y_{i} (X)\}_{i = 1}^n)$, and thus $\{1, Z (X)\} \cup \{y_{i} (X)\}_{i = 1}^n$ is a basis of all polynomials of degree at most $n+1$. Thus, $\mathcal {F}_{uv, 1}$ can be computed iff $\{X^i\}_{i = 0}^{n + 1} \cup \{X_\beta \mathcal {F}_{\mathsf {com}}\}$ can be computed.

Theorem 2

The new unit vector argument is perfectly complete and witness-indistinguishable. If $\mathsf {BP}$ is $(n + 1, 2 n + 3)$-PCDH secure, $(n + 1)$-TSDH secure, and $(n + 1, X_\beta \mathcal {F}_{\mathsf {com}}, \{Y X_\beta \})$-PKE secure, then this argument is an adaptive argument of knowledge.

Proposition 1

The computation of $(\pi ^*_{uv}, A_1^{\beta })$ takes one 2-wide multi-exponentiation and 1 exponentiation in $\mathbb {G}_1$. In addition, it takes 2 exponentiations (one in $\mathbb {G}_1$ and one in $\mathbb {G}_2$) in the master argument to compute $(A_1, A_2^{\gamma })$. The verifier computation is dominated by 6 pairings.

4 New Same-Message Argument

In a same-message argument, the prover aims to convince the verifier that he knows, given two commitment keys $\mathsf {ck}$ and $\widehat{\mathsf {ck}}$ (that correspond to two tuples of polynomials $(P_i (X))_{i = 0}^n$ and $(\hat{P}_i (X))_{i = 0}^n$, respectively), how to open $(A_1, A_2^{\gamma }) = \mathsf {com}(\mathsf {ck}; {{\varvec{m}}}; r)$ and $(\hat{A}_1, \hat{A}_2^{\hat{\gamma }}) = \mathsf {com}(\widehat{\mathsf {ck}}; {{\varvec{m}}}; \hat{r})$ as commitments (w.r.t. $\mathsf {ck}$ and $\widehat{\mathsf {ck}}$) to the same plaintext vector m (but not necessarily to the same randomizer r).

We propose an efficient same-message argument using $\mathcal {F}_{\mathsf {com}}= (Z (X), (y_{i} (X))_{i = 1}^n)$ as described in Sect. 3. In the shuffle argument, we need $(\hat{P}_i (X))_{i = 0}^n$ to satisfy some specific requirements w.r.t. $\mathcal {F}_{\mathsf {com}}$, see Sect. 5. We are free to choose $\hat{P}_i$ otherwise. We concentrate on a choice of $\hat{P}_i$ that satisfies those requirements yet enables us to construct an efficient same-message argument.

Denote $\hat{Z} (X) = \hat{P}_0 (X)$. For the same-message argument to be an argument of knowledge and efficient, we choose $\hat{P}_i$ such that $(\hat{P}_i (\omega _j))_{j = 1}^{n + 1} = (y_{i} (\omega _j))_{j = 1}^{n + 1} = 2 \mathbf {e_i} + \mathbf {e_{n + 1}}$ for $i \in [1 \, .. \, n]$. Moreover, $(\hat{Z} (\omega _j))_{j = 1}^{n + 1} = (Z (\omega _j))_{j = 1}^{n + 1} = \mathbf {0}_{n + 1}$.

Following similar methodology as in Sect. 3, define

$$\textstyle Q_{wi} (X) := (\hat{r} \hat{Z} (X) + \sum _{i = 1}^n \hat{m}_i \hat{P}_i (X)) - (r Z (X) + \sum _{i = 1}^n m_i y_{i} (X)). $$

Let $\hat{n}$ be the maximum degree of polynomials in $(y_{i} (X), \hat{P}_i (X))_{i = 0}^n$, thus $\deg Q_{wi} \le \hat{n}$. Since $Q_{wi} (\omega _j) = 2 (\hat{m}_j - m_j)$ for $j \in [1 \, .. \, n]$, $Q_{wi} (\omega _j) = 0$ iff $m_j = \hat{m}_j$. Moreover, if ${{\varvec{m}}} = \mathbf {\hat{m}}$ then $Q_{wi} (\omega _{n + 1}) = \sum _{i = 1}^n \hat{m}_i - \sum _{i = 1}^n m_i = 0$. Hence, ${{\varvec{m}}} = \mathbf {\hat{m}}$ iff

• (i) $Q_{wi} (X) = \hat{A} (X) - A (X)$, where $A (X) \in {\text {span}}(\{Z (X)\} \cup \{y_{i} (X)\}_{i = 1}^n)$, and $\hat{A} (X) \in {\text {span}}(\{\hat{Z} (X)\} \cup \{\hat{P}_i (X)\}_{i = 1}^n)$, and

• (ii) there exists a degree $\le \hat{n}- (n + 1)$ polynomial $\pi _{wi} (X) = Q_{wi} (X) / Z (X)$.

If the prover is honest, then $\pi _{wi} (X) = \hat{r} \hat{Z} (X) / Z (X) - r + \sum m_i \cdot ((\hat{P}_i (X) - y_{i} (X)) / Z (X))$. Note that we do not need that $Q_{wi} (X) = 0$ as a polynomial, we just need that $Q_{wi} (\omega _i) = 0$, which is a deviation from the strategy usually used in QAP/QSP-based arguments [11].

We guarantee the conditions similarly to Sect. 3. The description of the argument follows. (Since it is derived as in Sect. 3, we omit further explanations.)

• System parameters: Let $n = {\text {poly}}(\kappa )$. Let $\mathsf {com}$ be the polynomial commitment scheme and let $\mathcal {F}_{\mathsf {com}}= (Z (X), (y_{i})_{i = 1}^n)$ and $\hat{\mathcal {F}}_{\mathsf {com}}= (\hat{Z} (X), (\hat{P}_i)_{i = 1}^n)$, where $\hat{P}_i (X)$ is such that $y_{i} (\omega _j) = \hat{P}_i (\omega _j)$ for $i \in [0 \, .. \, n + 1]$ and $j \in [1 \, .. \, n + 1]$.

• Setup $\mathsf {setup}_{sm} (1^\kappa , n)$ : Let $\mathsf {gk}\leftarrow \mathsf {BP}(1^\kappa , n)$.

• CRS generation $\mathsf {gencrs}_{sm} (\mathsf {gk})$ : Let $(g_1, g_2, \chi , \beta , \gamma , \hat{\gamma }) \leftarrow _r\mathbb {G}_1^* \times \mathbb {G}_2^* \times \mathbb {Z}_p^4$ with $Z (\chi ) \ne 0$. Set $\mathsf {ck}\leftarrow (g_1, g_2^{\gamma })^{\mathcal {F}_{\mathsf {com}}(\chi )}$ and $\widehat{\mathsf {ck}} \leftarrow (g_1, g_2^{\hat{\gamma }})^{\hat{\mathcal {F}}_{\mathsf {com}}(\chi )}$. Let $\mathsf {crs}_{sm, p} \leftarrow (\mathsf {ck}, \widehat{\mathsf {ck}}, g_1^{\beta \cdot \mathcal {F}_{\mathsf {com}}(\chi )}, g_1^{\hat{Z} (\chi ) / Z (\chi )}, g_1, (g_1^{(\hat{P}_i (\chi ) - y_{i} (\chi )) / Z (\chi )})_{i = 1}^n)$, and $\mathsf {crs}_{sm, v} \leftarrow (g_1, g_2^{\gamma }, g_2^{\hat{\gamma }}, g_2^{\gamma \beta }, g_2^{\gamma Z (\chi )})$. Return $\mathsf {crs}_{sm} = (\mathsf {crs}_{sm, p}, \mathsf {crs}_{sm, v})$.

• Common input: $(A_1, A_2^{\gamma }) = \mathsf {com}(\mathsf {ck}; {{\varvec{m}}}; r), (\hat{A}_1, \hat{A}_2^{\hat{\gamma }}) = \mathsf {com}(\widehat{\mathsf {ck}}; {{\varvec{m}}}; \hat{r})$.

• Argument generation $\mathsf {pro}_{sm} (\mathsf {gk}, \mathsf {crs}_{sm, p}; A_1, A_2^{\gamma }, \hat{A}_1, \hat{A}_2^{\hat{\gamma }}; {{\varvec{m}}}, r, \hat{r})$ : Set $\pi ^*_{sm} \leftarrow g_1^{\pi _{wi} (\chi )} = (g_1^{\hat{Z} (\chi ) / Z (\chi )})^{\hat{r}} \cdot g_1^{-r} \cdot \prod _{i = 1}^n (g_1^{(\hat{P}_i (\chi ) - y_{i} (\chi )) / Z (\chi )})^{m_i}$. Set $A_1^{\beta } \leftarrow (g_1^{\beta Z (\chi )})^r \prod _{i=1}^n (g_1^{\beta y_{i}(\chi )})^{m_i}$. Output $\pi _{sm} = (\pi ^*_{sm}, A_1^{\beta }) \in \mathbb {G}_1^2$.

• Verification $\mathsf {ver}_{sm} (\mathsf {gk}, \mathsf {crs}_{sm, v}; (A_1, A_2^{\gamma }), (\hat{A}_1, \hat{A}_2^{\hat{\gamma }}); \pi _{sm})$ : Parse $\pi _{sm}$ as $\pi _{sm} = (\pi ^*_{sm}, A_1^{\beta })$. Verify that (1) $\hat{e}(g_1, A_2^{\gamma }) = \hat{e}(A_1, g_2^{\gamma })$, (2) $\hat{e}(A_1, g_2^{\gamma \beta }) = \hat{e}(A_1^{\beta }, g_2^{\gamma })$, (3) $\hat{e}(g_1, \hat{A}_2^{\hat{\gamma }}) = \hat{e}(\hat{A}_1, g_2^{\hat{\gamma }})$, and (4)$\hat{e}(\pi ^*_{sm}, g_2^{\gamma Z (\chi )}) = \hat{e}(\hat{A}_1 / A_1, g_2^{\gamma })$.

Let $\hat{Y}$ be the formal variable corresponding to $\hat{\gamma }$. In the following theorem, it suffices to take $\mathsf {crs}^* = (g_1^{\mathcal {F}_{sm, 1} (\chi , \beta )}, g_2^{\mathcal {F}_{sm, 2} (\chi , \beta , \gamma , \hat{\gamma })})$, where $\mathcal {F}_{sm, 1} = \{1\} \cup \mathcal {F}_{\mathsf {com}}\cup \hat{\mathcal {F}}_{\mathsf {com}}\cup X_\beta \mathcal {F}_{\mathsf {com}}\cup \{\hat{Z} (X) / Z (X)\} \cup \{(\hat{P}_i (X) - y_{i} (X)) / Z (X)\}_{i = 1}^n$ and $\mathcal {F}_{sm, 2} = Y \cdot (\{1, X_\beta \} \cup \mathcal {F}_{\mathsf {com}}) \cup \hat{Y} \cdot (\{1\} \cup \hat{\mathcal {F}}_{\mathsf {com}})$.

Theorem 3

The same-message argument is perfectly complete and witness-indistinguishable. Let $\hat{n}$ be as above. If $\mathsf {BP}$ is $(\hat{n}, \hat{n}+ n + 2)$-PCDH secure, $\hat{n}$-TSDH secure, $(n + 1, \mathcal {F}_{sm, 1} \setminus (\{1\} \cup \mathcal {F}_{\mathsf {com}}), \mathcal {F}_{sm, 2} \setminus Y \cdot (\{1\} \cup \mathcal {F}_{\mathsf {com}}), \gamma )$-PKE secure, and $(\hat{\mathcal {F}}_{\mathsf {com}}, \mathcal {F}_{sm, 1} \setminus \hat{\mathcal {F}}_{\mathsf {com}},\mathcal {F}_{sm, 2} \setminus \hat{Y} \hat{\mathcal {F}}_{\mathsf {com}}, \hat{\gamma })$-PKE secure, then this argument is an adaptive argument of knowledge.

Proposition 2

The prover’s computation is dominated by one $(W + 2)$-wide and one $(W + 1)$-wide multi-exponentiation in $\mathbb {G}_1$, where $0 \le W \le n$ is the number of elements in the vector ${{\varvec{m}}}$ that are not in $\{0, 1\}$. The verifier’s computation is dominated by 8 pairings.

In the shuffle argument below, the prover uses $r = \hat{r}$, so prover’s computation is $2 W + 2$ exponentiations. For a unit vector ${{\varvec{m}}}$, we additionally have $W = 0$ and computing $A_1^{\beta }$ and the first two verification steps are already done in the unit vector argument anyway, so the argument only adds 1 exponentiation for the prover, and 4 pairings for the verifier.

5 New Assumption: PSP

We will next describe a new computational assumption (PSP) that is needed in the shuffle argument. The PSP assumption is related to but not equal to the SP assumption from [15]. Interestingly, the generic group proof of the PSP assumption relies on the Schwartz-Zippel lemma, while in most of the known interactive shuffle arguments (like [20]), the Schwartz-Zippel lemma is used in the reduction from the shuffle security to some underlying assumption.

Let $d (n) > n$ be a function. Let $\hat{\mathcal {F}} = (\hat{P}_i (X))_{i = 0}^n$ be a tuple of polynomials. We say $(d (n), \hat{\mathcal {F}})$ is PSP-friendly, if the following set is linearly independent: $\hat{\mathcal {F}}_{d (n)} := \{X^i\}_{i = 0}^{2 d (n)} \cup \{X^i \cdot \hat{P}_j (X)\}_{0 \le i \le d (n), 0 \le j \le n} \cup \{\hat{P}_0 (X) \hat{P}_j (X)\}_{j = 0}^{n}$.

Let $(d (n), \hat{\mathcal {F}})$ be PSP-friendly. Let $\mathcal {F}= (P_i (X))_{i = 0}^n$ be a tuple of polynomials of degree $\le d (n)$. The $(\mathcal {F}, \hat{\mathcal {F}})$ -Power Simultaneous Product (PSP) assumption states that for any $n = {\text {poly}}(\kappa )$ and any NUPPT adversary $\mathsf {A}$,

$$ \Pr \left[ \begin{aligned}&\mathsf {gk}\leftarrow \mathsf {BP}(1^\kappa , n), (g_1, g_2, \chi ) \leftarrow _r\mathbb {G}_1^* \times \mathbb {G}_2^* \times \mathbb {Z}_p, \\ {}&\mathbb {G}_1^{n + 2} \ni (t, \hat{t}, (s_i)_{i = 1}^n) \leftarrow \mathsf {A}(\mathsf {gk}; ((g_1, g_2)^{\chi ^i})_{i = 0}^{d (n)}, (g_1, g_2)^{\hat{\mathcal {F}} (\chi )}): \\ {}&\textstyle t^{P_0 (\chi )} \cdot \prod _{i = 1}^n s_i^{P_i (\chi )} = \hat{t}\,^{\hat{P}_0 (\chi )} \cdot \prod _{i = 1}^n s_i^{\hat{P}_i (\chi )} = 1 \wedge \left( \exists i \in [1 \, .. \, n] : s_i \ne 1\right) \end{aligned} \right] \approx _\kappa 0. $$

In this section, we prove that the PSP assumption holds in the generic bilinear group model. PSP-friendliness and the PSP assumption are defined so that both the generic model proof and the reduction from the shuffle soundness to the PSP in Theorem 5 would go through. As in the case of SP, it is essential that two simultaneous products have to hold true; the simpler version of the PSP assumption with only one product (i.e., $t^{P_0 (\chi )} \cdot \prod _{i = 1}^n s_i^{P_i (\chi )} = 1$) does not hold in the generic bilinear group model. Differently from SP, the PSP assumption incorporates possibly distinct t and $\hat{t}$ since the same-message argument does not guarantee that the randomizers of two commitments are equal.

Generic Security of the PSP Assumption. We will briefly discuss the security of the PSP assumption in the generic bilinear group model. Similarly to [15], we start by picking a random asymmetric bilinear group $\mathsf {gk}:= (p, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, \hat{e}) \leftarrow \mathsf {BP}(1^\kappa )$. We now give a generic bilinear group model proof for the PSP assumption.

Theorem 4

Let $\mathcal {F}= (P_i (X))_{i = 0}^n$ be linearly independent with $1 \not \in {\text {span}}(\mathcal {F})$. Let $d = \max \{\deg P_i (X)\}$ and let $\hat{\mathcal {F}} =(\hat{P}_i (X))_{i = 0}^n$ be such that $(d, \hat{\mathcal {F}})$ is PSP-friendly. The $(\mathcal {F}, \hat{\mathcal {F}})$-PSP assumption holds in the generic bilinear group model.

Proof

Assume there exists a successful adversary $\mathsf {A}$. In the generic bilinear group model, $\mathsf {A}$ acts obliviously to the actual representation of the group elements and only performs generic bilinear group operations such as multiplying elements in $\mathbb {G}_i$ for $i \in \{1, 2, T\}$, pairing elements in $\mathbb {G}_1$ and $\mathbb {G}_2$, and comparing elements to see if they are identical. Hence it can only produce new elements in $\mathbb {G}_1$ by multiplying existing group elements together.

Recall that the $\mathsf {A}$’s input is $\mathsf {gk}$ and $\mathsf {crs}= (((g_1, g_2)^{\chi ^i})_{i = 0}^{d}, (g_1, g_2)^{\hat{\mathcal {F}} (\chi )})$. Hence, keeping track of the group elements we get that $\mathsf {A}$ outputs $t, \hat{t}, s_i \in \mathbb {G}_1$, where $\log _{g_1} t = \sum _{j = 0}^{d} t_{j} \chi ^j + \sum _{j = 0}^n t'_{j} \hat{P}_j (\chi )$, $\log _{g_1} \hat{t} = \sum _{j = 0}^{d} \hat{t}_{j} \chi ^j + \sum _{j = 0}^n \hat{t}'_{j} \hat{P}_j (\chi )$, and $\log _{g_1} s_i = \sum _{j = 0}^{d} s_{i j} \chi ^j + \sum _{j = 0}^n s'_{i j} \hat{P}_j (\chi )$, for known constants $t_j$, $t'_j$, $\hat{t}_j$, $\hat{t}'_j$, $s_{i j}$, $s'_{i j}$. Taking discrete logarithms of the PSP condition $t^{P_0 (\chi )} \cdot \prod _{i = 1}^n s_i^{P_i (\chi )} = \hat{t}^{\hat{P}_0 (\chi )} \cdot \prod _{i = 1}^n s_i^{\hat{P}_i (\chi )} = 1$, we get that the two polynomials (for known coefficients) $d_1 (X) := (\sum _{j = 0}^{d} t_{j} X^j + \sum _{j = 0}^n t'_{j} \hat{P}_j (X)) \cdot P_0 (X) + \sum _{i = 1}^n (\sum _{j = 0}^{d} s_{i j} X^j + \sum _{j = 0}^n s'_{i j} \hat{P}_j (X)) P_i (X), d_2 (X) := (\sum _{j = 0}^{d} \hat{t}_{j} X^j + \sum _{j = 0}^n \hat{t}'_{j} \hat{P}_j (X)) \cdot \hat{P}_0 (X) + \sum _{i = 1}^n (\sum _{j = 0}^{d} s_{i j} X^j + \sum _{j = 0}^n s'_{i j} \hat{P}_j (X)) \hat{P}_i (X)$ satisfy $d_1 (\chi ) = d_2 (\chi ) = 0$. Since the adversary is oblivious to the actual representation of the group elements it will do the same group operations no matter the actual value of $X (= \chi )$; so the values $t_{j}$, ..., $s'_{i j}$ are generated (almost²) independently of $\chi$. By the Schwartz-Zippel lemma there is a negligible probability that $d_i (\chi ) = 0$, for non-zero $d_i (X)$, when we choose $\chi$ randomly. Thus, with all but a negligible probability $d_1 (X)$ and $d_2 (X)$ are zero polynomials.

Since $\mathcal {F}$ and $\{X^i\}_{i = 0}^{2 d} \cup \{X^i \cdot \hat{P}_j (X)\}_{i \in [0 \, .. \, d], j \in [0 \, .. \, n]}$ are both linearly independent, $\{X^i\}_{i = 0}^{2 d} \cup \{P_i (X) \hat{P}_j (X)\}_{i, j \in [0 \, .. \, n]}$ is also linearly independent. We get from $d_1 (X) = 0$ that $\sum _{j = 0}^n t'_{j} P_0 (X) \hat{P}_j (X) + \sum _{i = 1}^n \sum _{j = 0}^n s'_{i j} P_i (X) \hat{P}_j (X) = 0$, which implies $s'_{i j} = 0$ for $i \in [1 \, .. \, n], j \in [0 \, .. \, n]$. Substituting these values into $d_2 (X) = 0$, we get that $\left( \sum _{j = 0}^{d} \hat{t}_{j} X^j + \sum _{j = 0}^n \hat{t}'_{j} \hat{P}_j (X)\right) \hat{P}_0 (X) + \sum _{i = 1}^n \sum _{j = 0}^{d} s_{i j} X^j \hat{P}_i (X) = 0$. Since $\hat{\mathcal {F}}_{d}$ is linearly independent, we get that all coefficients in the above equation are zero, and in particular $s_{i j} = 0$ for $i \in [1 \, .. \, n], j \in [0 \, .. \, n]$. Thus $s_i = 1$ for $i \in [1 \, .. \, n]$. Contradiction to the fact that the adversary is successful.   $\square$

6 New Shuffle Argument

Let Elgamal operate in $\mathbb {G}_1$ defined by $\mathsf {gk}$. In a shuffle argument, the prover aims to convince the verifier that, given the description of a group, a public key, and two vectors of ciphertexts, the second vector of the ciphertexts is a permutation of rerandomized versions of the ciphertexts from the first vector. However, to achieve better efficiency, we construct a shuffle argument that is only culpably sound with respect to the next relation (i.e., $\mathcal {R}^{\mathsf {guilt}}_{sh}$-sound:

$$ \mathcal {R}^{\mathsf {guilt}}_{sh, n} = \left\{ \begin{aligned}&(\mathsf {gk}, (\mathsf {pk}, (z_i)_{i = 1}^n, (z^\prime _i)_{i = 1}^n), \mathsf {sk}): \mathsf {gk}\in \mathsf {BP}(1^\kappa , n) \wedge \\ {}&(\mathsf {pk}, \mathsf {sk}) \in \mathsf {genpkc}(\mathsf {gk}) \wedge \left( \forall \psi \in S_n: \exists i: \mathsf {dec}_{\mathsf {sk}} (z^\prime _i) \ne \mathsf {dec}_{\mathsf {sk}} (z_{\psi (i)})\right) \end{aligned} \right\} . $$

The argument of [15] is proven to be $\mathcal {R}^{\mathsf {guilt}}_{sh}$-sound with respect to the same relation. See [15] or the introduction for an explanation why $\mathcal {R}^{\mathsf {guilt}}_{sh}$ is sufficient.

As noted in the introduction, we need to use same-message arguments and rely on the PSP assumption. Thus, we need polynomials $\hat{P}_j$ that satisfy two different requirements at once. First, to be able to use the same-message argument, we need that $y_{j} (\omega _k) = \hat{P}_j (\omega _k)$ for $k \in [1 \, .. \, n + 1]$. Second, to be able to use the PSP assumption, we need $(d, \hat{\mathcal {F}})$ to be PSP-friendly, and for this we need $\hat{P}_j (X)$ to have a sufficiently large degree. Recall that $y_{j}$ are fixed by the unit vector argument. We now show that such a choice for $\hat{P}_j$ exists.

Proposition 3

Let $\hat{y}_{j} (X) := (X Z (X) + 1)^{j - 1} (X^2 Z (X) + 1) y_{j} (X)$ for $j \in [1 \, .. \, n]$, and $\hat{Z} (X) = \hat{y}_{0} (X) := (X Z (X) + 1)^{n + 1} Z (X)$. Let $\hat{\mathcal {F}}_{\mathsf {com}}= (\hat{y}_{j} (X))_{j = 0}^n$. Then $\hat{y}_{j} (\omega _k) = y_{j} (\omega _k)$ for all j, k, and $(n + 1, \hat{\mathcal {F}}_{\mathsf {com}})$ is PSP-friendly.

Next, we will provide the full description of the new shuffle argument. Note that $(c_{i})_{i = 1}^{n}$ are commitments to the rows of the permutation matrix $\mathbf {\varPsi }$, proven by the n unit vector arguments $(\pi _{uv, i})_{i = 1}^{n}$ and by the implicit computation of $c_{n}$. We denote $\hat{E}((a, b), c) := (\hat{e}(a, c), \hat{e}(b, c))$.

• System parameters: Let $(\mathsf {genpkc}, \mathsf {enc}, \mathsf {dec})$ be the Elgamal cryptosystem. Let $\mathsf {com}$ be the polynomial commitment scheme. Consider polynomials $\mathcal {F}_{\mathsf {com}}= \{Z (X)\} \cup (y_{i} (X))_{i = 1}^n$ from Sect. 3. Let $\hat{\mathcal {F}}_{\mathsf {com}}= (\hat{y}_{i} (X))_{i = 0}^n$ be as in Proposition 3.

• Setup $\mathsf {setup}_{sh} (1^\kappa , n)$ : Let $\mathsf {gk}\leftarrow \mathsf {BP}(1^\kappa , n)$.

• CRS generation $\mathsf {gencrs}_{sh} (\mathsf {gk})$ : Let $(g_1, g_2, \chi , \beta , \gamma ) \leftarrow _r\mathbb {G}^*_1 \times \mathbb {G}^*_2 \times \mathbb {Z}_p^3$ with $Z (\chi ) \ne 0$. Let $(\mathsf {crs}_{uv, p}, \mathsf {crs}_{uv, v}) \leftarrow _r\mathsf {gencrs}_{uv} (\mathsf {gk}, n)$, $(\mathsf {crs}_{sm, p}, \mathsf {crs}_{sm, v}) \leftarrow _r\mathsf {gencrs}_{sm} (\mathsf {gk}, n)$, but by using the same $(g_1, g_2, \chi , \beta , \gamma )$ in both cases. Let $\mathsf {ck}\leftarrow (g_1, g_2^{\gamma })^{\mathcal {F}_{\mathsf {com}}(\chi )}$ and $\widehat{\mathsf {ck}} \leftarrow (g_1, g_2^{\hat{\gamma }})^{\hat{\mathcal {F}}_{\mathsf {com}}(\chi )}$. Set $(D_1, D_2^{\gamma }) \leftarrow \mathsf {com}(\mathsf {ck}; \mathbf {1_n}; 0)$, $(\hat{D}_1, \hat{D}_2^{\hat{\gamma }}) \leftarrow \mathsf {com}(\widehat{\mathsf {ck}}; \mathbf {1_n}; 0)$. Set $\mathsf {crs}_{sh, p} \leftarrow (\mathsf {crs}_{uv, p}, \widehat{\mathsf {ck}}, g_1^{\hat{Z} (\chi ) / Z (\chi )}, g_1, (g_1^{(\hat{y}_{i} (\chi ) - y_{i} (\chi )) / Z (\chi )})_{i = 1}^n, D_1, D_2^{\gamma }, \hat{D}_1, \hat{D}_2^{\hat{\gamma }})$, $\mathsf {crs}_{sh, v} \leftarrow (\mathsf {crs}_{uv, v}, g_2^{\hat{\gamma }}, \{g_2^{\gamma y_{i} (\chi )}, g_2^{\hat{\gamma } \hat{y}_{i} (\chi )}\}_{i = 0}^n, D_1, D_2^{\gamma }, \hat{D}_1, \hat{D}_2^{\hat{\gamma }})$, and $\mathsf {td}_{sh} \leftarrow \chi$. Return $((\mathsf {crs}_{sh, p}, \mathsf {crs}_{sh, v}), \mathsf {td}_{sh})$.

• Common input: $(\mathsf {pk}, (z_i, z^\prime _i)_{i = 1}^n)$, where $\mathsf {pk}= (g_1, h) \in \mathbb {G}_1^2$, $z_i \in \mathbb {G}_1^2$ and $z^\prime _i = z_{\psi (i)} \cdot \mathsf {enc}_{\mathsf {pk}} (1; t_i) \in \mathbb {G}_1^2$.

• Argument $\mathsf {pro}_{sh} (\mathsf {gk}, \mathsf {crs}_{sh, p}; \mathsf {pk}, (z_i, z^\prime _i)_{i = 1}^n; \psi , (t_i)_{i = 1}^n)$ :

  • (1) Let $\mathbf {\varPsi }= \mathbf {\varPsi }_{\psi ^{-1}}$ be the $n \times n$ permutation matrix corresponding to $\psi ^{-1}$.

  • (2) For $i \in [1 \, .. \, n - 1]$:

    • Set $r_i \leftarrow \mathbb {Z}_p$, $(c_{i 1}, c_{i 2}^{\gamma }) \leftarrow \mathsf {com}(\mathsf {ck}; \mathbf {\varPsi }_i; r_i)$, $(\hat{c}_{i 1}, \hat{c}_{i 2}^{\hat{\gamma }}) \leftarrow \mathsf {com}(\widehat{\mathsf {ck}}; \mathbf {\varPsi }_i; r_i)$.

  • (3) Set $r_n \leftarrow -\sum _{i = 1}^{n - 1}r _i$, $(c_{n 1}, c_{n 2}^{\gamma }) \leftarrow (D_1, D_2^{\gamma }) / \prod _{i = 1}^{n - 1} (c_{i 1}, c_{i 2}^{\gamma })$.

  • (4) Set $(\hat{c}_{n 1}, \hat{c}_{n 2}^{\hat{\gamma }}) \leftarrow (\hat{D}_1, \hat{D}_2^{\hat{\gamma }}) / \prod _{i = 1}^{n - 1} (\hat{c}_{i 1}, \hat{c}_{i 2}^{\hat{\gamma }})$.

  • (5) For $i \in [1 \, .. \, n]$: set $\pi _{uv, i} = (\pi ^*_{uv, i}, c_{i 1}^{\beta }) \leftarrow \mathsf {pro}_{uv} (\mathsf {gk}, \mathsf {crs}_{uv, p}; c_{i 1}, c_{i 2}^{\gamma }; \mathbf {\varPsi }_i, r_i)$.

  • (6) Set $r_t \leftarrow _r\mathbb {Z}_p$, $(d_1, d_2^{\gamma }) \leftarrow \mathsf {com}(\mathsf {ck}; {{\varvec{t}}}; r_t)$, and $(\hat{d}_1, \hat{d}_2^{\hat{\gamma }}) \leftarrow \mathsf {com}(\widehat{\mathsf {ck}}; {{\varvec{t}}}; r_t)$.

  • (7) For $i \in [1 \, .. \, n - 1]$:

    • Set $(\pi ^*_{sm, i}, c_{i 1}^{\beta }) \leftarrow \mathsf {pro}_{sm} (\mathsf {gk}, \mathsf {crs}_{sm, p}; c_{i 1}, c_{i 2}^{\gamma }, \hat{c}_{i 1},\hat{c}_{i 2}^{\hat{\gamma }}; \mathbf {\varPsi }_i, r_i, r_i)$.

  • (8) Set $\pi _{sm, d} \leftarrow \mathsf {pro}_{sm} (\mathsf {gk}, \mathsf {crs}_{sm, p}; d_1, d_2^{\gamma }, \hat{d}_1,\hat{d}_2^{\hat{\gamma }}; \mathbf {t}, r_t, r_t)$.

  • (9) Compute $U = (U_1, U_2) \leftarrow \mathsf {pk}^{r_t} \cdot \prod _{i = 1}^n z_i^{r_i} \in \mathbb {G}_1^2$. // The only online step

  • (10) Output $\pi _{sh} \leftarrow ((c_{i 1}, c_{i 2}^{\gamma }, \hat{c}_{i 1}, \hat{c}_{i 2}^{\hat{\gamma }})_{i = 1}^{n - 1}, d_1, d_2^{\gamma }, \hat{d}_1, \hat{d}_2^{\hat{\gamma }}, (\pi _{uv, i})_{i = 1}^n,$ $(\pi ^*_{sm, i})_{i = 1}^{n - 1}, \pi _{sm, d}, U)$

• Verification $\mathsf {ver}_{sh} (\mathsf {gk}, \mathsf {crs}_{sh, v}; \mathsf {pk}, (z_i, z^\prime _i)_{i = 1}^n, \pi _{sh})$ :

  • (1) Let $(c_{n 1}, c_{n 2}^{\gamma }) \leftarrow (D_1, D_2^{\gamma }) / \prod _{i = 1}^{n - 1} (c_{i 1}, c_{i 2}^{\gamma })$.

  • (2) Let $(\hat{c}_{n 1}, \hat{c}_{n 2}^{\hat{\gamma }}) \leftarrow (\hat{D}_1, \hat{D}_2^{\hat{\gamma }}) / \prod _{i = 1}^{n - 1} (\hat{c}_{i 1}, \hat{c}_{i 2}^{\hat{\gamma }})$.

  • (3) For $i \in [1 \, .. \, n]$: reject if $\mathsf {ver}_{uv} (\mathsf {gk}, \mathsf {crs}_{uv, v}; c_{i 1}, c_{i 2}^{\gamma }; \pi _{uv, i})$ rejects.

  • (4) For $i \in [1 \, .. \, n - 1]$: reject if $\mathsf {ver}_{sm} (\mathsf {gk}; \mathsf {crs}_{sm, v}; c_{i 1}, c_{i 2}^{\gamma }, \hat{c}_{i 1},\hat{c}_{i 2}^{\hat{\gamma }}; \pi _{sm, i})$ rejects.

  • (5) Reject if $\mathsf {ver}_{sm} (\mathsf {gk}, \mathsf {crs}_{sm, v}; d_1, d_2^{\gamma }, \hat{d}_1,\hat{d}_2^{\hat{\gamma }}; \pi _{sm, d})$ rejects.

  • (6) Check the PSP-related verification equations: // The only online step

    • (a) $\prod _{i = 1}^{n} \hat{E}(z^\prime _i, g_2^{\gamma y_{i} (\chi )}) / \prod _{i = 1}^n \hat{E}(z_i, c_{i 2}^{\gamma }) = \hat{E}((g_1, h), d_2^{\gamma }) / \hat{E}(U, g_2^{\gamma Z (\chi )})$,

    • (b) $\prod _{i = 1}^{n} \hat{E}(z^\prime _i, g_2^{\hat{\gamma } \hat{y}_{i} (\chi )}) / \prod _{i = 1}^n \hat{E}(z_i, \hat{c}_{i 2}^{\hat{\gamma }}) = \hat{E}((g_1, h), \hat{d}_2^{\hat{\gamma }}) / \hat{E}(U, g_2^{\hat{\gamma } \hat{Z} (\chi )})$.

Since $\mathsf {ck}, \widehat{\mathsf {ck}} \subset \mathsf {crs}_{sh, p}$, $(D_1, D_2^{\gamma }) = \mathsf {com}(\mathsf {ck}; \mathbf {1}_n; 0)$ and $(\hat{D}_1, \hat{D}_2^{\hat{\gamma }}) = \mathsf {com}(\widehat{\mathsf {ck}}; \mathbf {1}_n; 0)$ can be computed from the rest of the CRS. (These four elements are only needed to optimize the computation of $(c_{n 1}, c_{n 2}^{\gamma })$ and $(\hat{c}_{n 1}, \hat{c}_{n 2}^{\hat{\gamma }})$.) For security, it suffices to take $\mathsf {crs}^*_{sh} = (g_1^{\mathcal {F}_{sh, 1} (\chi , \beta )}, g_2^{\mathcal {F}_{sh, 2} (\chi , \beta , \gamma , \hat{\gamma })})$, where $\mathcal {F}_{sh, 1} = \mathcal {F}_{uv, 1} \cup \hat{\mathcal {F}}_{\mathsf {com}}\cup \{\hat{Z} (X) / Z (X)\} \cup \{(\hat{y}_{i} (X) - y_{i} (X)) / Z (X)\}_{i = 1}^n$ and $\mathcal {F}_{sh, 2} = \mathcal {F}_{uv, 2} \cup \hat{Y} \cdot (\{1\} \cup \hat{\mathcal {F}}_{\mathsf {com}})$.

Theorem 5

The new shuffle argument is a non-interactive perfectly complete and perfectly zero-knowledge shuffle argument for Elgamal ciphertexts. If the $(n + 1)$-TSDH, $(\hat{n}, \hat{n}+ n + 2)$-PCDH, $(\mathcal {F}_{\mathsf {com}}, \hat{\mathcal {F}}_{\mathsf {com}})$-PSP, $(n + 1, \mathcal {F}_{sh, 1} \setminus (\{1\} \cup \mathcal {F}_{\mathsf {com}}), \mathcal {F}_{sh, 2} \setminus Y \cdot (\{1\} \cup \mathcal {F}_{\mathsf {com}}), \gamma )$-PKE, $(\hat{\mathcal {F}}_{\mathsf {com}}, \mathcal {F}_{sh, 1} \setminus \hat{\mathcal {F}}_{\mathsf {com}}, \mathcal {F}_{sh, 2} \setminus \hat{Y} \hat{\mathcal {F}}_{\mathsf {com}}, \hat{\gamma })$-PKE assumptions hold, then the shuffle argument is adaptively computationally culpably sound w.r.t. the language $\mathcal {R}_{sh, n}^{\mathsf {guilt}}$ and an argument of knowledge.

When using a Barreto-Naehrig curve, exponentiations in $\mathbb {G}_1$ are three times cheaper than in $\mathbb {G}_2$. Moreover, a single $(N + 1)$-wide multi-exponentiations is considerably cheaper than $N + 1$ exponentiations. Hence, we compute separately the number of exponentiations and multi-exponentiations in both $\mathbb {G}_1$ and $\mathbb {G}_2$. For the sake of the simplicity, Proposition 4 only summarizes those numbers.

Proposition 4

The prover’s CRS consists of $6 n + 7$ elements of $\mathbb {G}_1$ and $2 n + 4$ elements of $\mathbb {G}_2$. The verifier’s CRS consists of 4 elements of $\mathbb {G}_1$, $2 n + 8$ elements of $\mathbb {G}_2$, and 1 element of $\mathbb {G}_T$. The total CRS is $6 n + 8$ elements of $\mathbb {G}_1$, $2 n + 8$ elements of $\mathbb {G}_2$, and 1 element of $\mathbb {G}_T$, in total $8 n + 17$ group elements. The communication complexity is $5 n + 2$ elements of $\mathbb {G}_1$ and 2 n elements of $\mathbb {G}_2$, in total $7 n + 2$ group elements. The prover’s and the verifier’s computational complexity are as in Table 1.

Importantly, both the proving and verification algorithm of the new shuffle argument can be divided into offline (independent of the common input $(\mathsf {pk}, (z_i, z'_i)_{i = 1}^n)$) and online (dependent on the common input) parts. The prover can precompute all elements of $\pi _{sh}$ except U (i.e., execute all steps of the proving algorithm, except step (9)), and send them to the verifier before the inputs are fixed. The verifier can verify $\pi _{sh} \setminus \{U\}$ (i.e., execute all steps of the verification algorithm, except step (6)) in the precomputation step. Thus, the online computational complexity is dominated by two $(n + 1)$-wide multi-exponentiations for the prover, and $8 n + 4$ pairings for the verifier (note that $\hat{E}((g_1, h), d_2^{\gamma })$ and $\hat{E}((g_1, h), \hat{d}_2^{\hat{\gamma }})$ can also be precomputed by the verifier).

Low online complexity is highly important in e-voting, where the online time (i.e., the time interval after the ballots are gathered and before the election results are announced) can be limited for legal reasons. In this case, the mix servers can execute all but step (9) of the proving algorithm and step (6) of the verification algorithm before the votes are even cast, assuming one is able to set a priori a reasonable upper bound on n, the number of votes. See [24] for additional motivation.