White-Box Weak SE of Groth16#

This section shows that Groth16 is white-box weakly simulation extractable.

Theorem (Groth16 is WB-W-SE)

Assume that \(\left\{u_i(x)\right\}_{i=0}^l\) are linearly independent and \(\operatorname{Span}\left\{u_i(x)\right\}_{i=0}^l \cap \operatorname{Span}\left\{u_i(x)\right\}_{i=l+1}^m=\emptyset\).

Then Groth16 achieves weak white-box SE against algebraic adversaries under the \((2 n-1, n-1)\)-dlog assumption.

Tip

The proof splits in two branches:

We show that either \(\mathcal{A}\) uses simulated elements, and in this case it can only use them for a single simulation query \(k\), or it does not use them at all. In particular, this implies that \(\mathcal{A}\) cannot combine several elements from different queries algebraically for the \(\pi\) it submits.

We then argue that the non-simulation case reduces to knowledge soundness, and in the simulation case we show that \(\mathcal{A}\) supplies \(\phi\) that is equal to one of the simulated instances, which proves that \(\mathcal{A}\) reuses a simulated proof, potentially randomized.

Proof. Let \(q\) denote the number of simulation queries of \(\mathcal{A}\), and \(\left\{a_{i, j}\right\}_{j=0}^l\) denote the instance for the \(i\) th query. We now add the three proof elements \(\left[\tilde{a}_i\right]_1,\left[\tilde{b}_i\right]_2,\left[\tilde{c}_i\right]_1\) revealed in each simulation to the list of elements that \(\mathcal{A}\) can use as an algebraic extraction basis: \(\tilde{a}_i=\mu_i, \tilde{b}_i=\nu_i\), and \(\tilde{c}_i=\left(\mu_i \nu_i-\alpha \beta-\sum_{j=0}^l a_{i, j}\left(\beta u_j(x)+\alpha v_j(x)+\right.\right.\) \(\left.\left.w_j(x)\right)\right) / \delta\). We write out the representation of \(A\) and \(B(C\) follows the same pattern as \(A)\) from the verification equation as the linear combination of the public CRS and new simulated proof elements:

\[\begin{split} \begin{aligned} &A=\cdots+\sum_{i=1}^q A_{8, i} \mu_i+\sum_{i=1}^q A_{9, i} \frac{\mu_i \nu_i-\alpha \beta-\sum_{j=0}^l a_{i, j}\left(\beta u_j(x)+\alpha v_j(x)+w_j(x)\right)}{\delta} \\ &B=\cdots+\sum_{i=1}^q B_{5, i} \nu_i \end{aligned} \end{split}\]

Our goal is to reduce the theorem to the knowledge-soundness case by restricting the coefficients related to the new simulated proofs variables, namely \(A_{8, i}, A_{9, i}, B_{5, i}, C_{8, i}, C_{9, i}\).

We will show that a successful \(\mathcal{A}\) must either reuse one of the simulated proofs (potentially randomizing it), or it must not have used any simulation-related variables, thus allowing for the reuse of the extraction argument from knowledge soundness.

We start by inspecting coefficients of the following monomials (affected by simulated proofs):

\[\begin{split} \begin{array}{cc} \alpha \beta \text { in } A B-C \delta: A_1 B_1-\sum_{i=1}^q A_{9, i} B_3+\sum_{i=1}^q C_{9, i}=1 & \mu_i \beta \text { in } A B: A_{8, i} B_1=0 \\ \mu_i \nu_j(i \neq j) \text { in } A B: A_{8, i} B_{5, j}=0 & \mu_i \gamma \text { in } A B: A_{8, i} B_2=0 \\ \mu_i \nu_i \text { in } A B-C \delta: A_{9, i} B_3+A_{8, i} B_{5, i}-C_{9, i}=0 & \mu_i \delta \text { in } A B-C \delta: A_{8, i} B_3-C_{8, i}=0 \\ \mu_i \nu_i \nu_j / \delta \text { in } A B: A_{9, i} B_{5, j}=0 & \nu_i \alpha \text { in } A B: B_{5, i} A_1=0 \\ \mu_i \nu_i \beta / \delta \text { in } A B: A_{9, i} B_1=0 & \nu_i \beta \text { in } A B: B_{5, i} A_2=0 \\ & \nu_i \delta \text { in } A B: B_{5, i} A_3=0 \end{array} \end{split}\]

First, we show that all \(A_{9, i}=0\). Assume the contrary: \(A_{9, k} \neq 0\) for some \(k\). Then from Equation \(\left(\mu_k \nu_k \nu_j / \delta\right)\) for all \(j: B_{5, j}=0\). From Equation \(\left(\mu_i \nu_i\right)\) for all \(i\) we have that \(C_{9, i}=\) \(A_{9, i} B_3\), which, substituted into Equation \((\alpha \beta)\) give us \(A_1 B_1=1\). Hence \(B_1 \neq 0\), but from Equation \(\left(\mu_k \nu_k \beta / \delta\right)\) we see that \(A_{9, k} B_1=0\), but neither \(A_{9, k}\) nor \(B_1\) is zero, a contradiction.

Thus, all \(A_{9, i}=0\), and furthermore Equation \((\alpha \beta)\) simplifies to \(A_1 B_1+\sum_{i=1}^q C_{9, i}=1\) and Equation \(\left(\mu_i \nu_i\right)\) simplifies to \(A_{8, i} B_{5, i}=C_{9, i}\).

We now show, that if at least one \(A_{8, k} \neq 0\), then \(\mathcal{A}\) reuses the \(k\) th simulated proof, and otherwise if all \(A_{8, i}=0\) it does not use any simulation-related elements.

  • Assume, first, that all \(A_{8, i}=0\) : From Equation \(\left(\mu_i \nu_i\right)\) all \(C_{9, i}=0\). Then, \(A_1 B_1=1\) by Equation \((\alpha \beta)\), so from Equation \(\left(\nu_i \alpha\right)\) all \(B_{5, i}=0\) (since \(A_1 \neq 0\) ), and from Equation \(\left(\mu_i \delta\right)\) all \(C_{8, i}=0\) because all \(A_{8, i}=0\). We now have cancelled all the simulation-related variables, and thus \(\mathcal{A}\) does not use simulation queries when constructing its proof, and we can reduce the proof to the knowledge soundness case.

  • Assume, otherwise, that at least one \(A_{8, k} \neq 0\) : Then \(B_1=B_2=0\) from Equation \(\left(\mu_k \beta\right)\) and Equation \(\left(\mu_k \gamma\right.\) ). For all \(j \neq k\) from Equation \(\left(\mu_k \nu_j\right)\) we have \(B_{5, j}=0\), and since \(C_{9, j}=B_{5, j} A_{8, j}\), all \(C_{9, j}=0\) for \(j \neq k\) too. From Equation \((\alpha \beta)\) we obtain \(C_{9, k}=1\), thus \(B_{5, k}=1 / A_{8, k}\) by Equation \(\left(\mu_i \nu_i\right)\). Since now \(B_{5, k} \neq 0\), from the Equations \(\left(\nu_k \alpha\right),\left(\nu_k \beta\right)\), \(\left(\nu_k \delta\right)\) we have \(A_1=A_2=A_3=0\). Thus, we are only left with exactly one nonzero triple \(\left(A_{8, k}, B_{5, k}, C_{9, k}\right)\), which means \(\mathcal{A}\) has used at most one simulated proof number \(k\), not being able to combine several simulated proofs into one. We next look at additional coefficients related to monomials that include \(\nu_k\) and \(\mu_k\). From Equations \(\left(\nu_i \beta / \delta\right),\left(\nu_i \alpha / \delta\right),\left(\nu_i / \delta\right)\) we have \(\sum_{i=l+1}^m A_{6, i}\left(\beta u_i(x)+\alpha v_i(x)+w_i(x)\right) / \delta+\sum_{i=0}^{n-2} A_{7, i} x^i t(x) / \delta=\) 0 (related terms of \(A\) are the only terms matching this \(\nu_i\) in \(B\) ):

\[\begin{split} \begin{aligned} \nu_k \beta / \delta \text { in } A B: &\left(\sum_{j=l+1}^m A_{6, j} u_j(x)-\sum_{i=1}^q \underline{A_{9, i}} \sum_{j=0}^l u_j(x)\right) B_{5, k}=0 \Longrightarrow \sum_{j=l+1}^m A_{6, j} u_j(x)=0 \\ \nu_k \alpha / \delta \text { in } A B: &\left(\sum_{j=l+1}^m A_{6, j} v_j(x)-\sum_{i=1}^q \underline{A_{9, i}} \sum_{j=0}^l v_j(x)\right) B_{5, k}=0 \Longrightarrow \sum_{j=l+1}^m A_{6, j} v_j(x)=0 \\ \nu_k / \delta \text { in } A B &\left(\sum_{j=l+1}^m A_{6, j} w_j(x)+\sum_{i=0}^{n-2} A_{7, i} x^i t(x)-\sum_{i=1}^q \underline{A_{9, i}} \sum_{j=0}^l w_j(x)\right) B_{5, k}=0 \\ &\left.\Longrightarrow \sum_{j=l+1}^m A_{6, j} w_j(x)=0 \wedge \sum_{i=0}^{n-2} A_{7, i} x^i t(x)=0 \text { (different powers of } x\right) \end{aligned} \end{split}\]

Similarly, from Equations \(\left(\nu_i \beta / \gamma\right),\left(\nu_i \alpha / \gamma\right),\left(\nu_i / \gamma\right)\) we have \(\sum_{i=0}^l A_{5, i}\left(\beta u_i(x) / \gamma\right)=\sum_{i=0}^l A_{5, i}\left(\alpha v_i(x) / \gamma\right)=\) \(\sum_{i=0}^l A_{5, i}\left(w_i(x) / \gamma\right)=0(\) the coefficients are also extracted from \(A B)\).

\[\begin{split} \begin{aligned} &\nu_k \beta / \gamma \text { in } A B:\left(\sum_{j=0}^l A_{5, j} u_j(x)\right) B_{5, k}=0 \Longrightarrow \sum_{j=0}^l A_{5, j} u_j(x)=0 \\ &\nu_k \alpha / \gamma \text { in } A B:\left(\sum_{j=0}^l A_{5, j} v_j(x)\right) B_{5, k}=0 \Longrightarrow \sum_{j=0}^l A_{5, j} v_j(x)=0 \\ &\nu_k / \gamma \text { in } A B:\left(\sum_{j=0}^m A_{5, j} w_j(x)\right) B_{5, k}=0 \Longrightarrow \sum_{j=l+1}^m A_{5, j} w_j(x)=0 \end{aligned} \end{split}\]

Because of Equation \(\left(\nu_k\right)\) and Equation \(\left(\mu_k\right)\) we have \(\sum_{i=0}^{n-1} A_{4, i} x^i=0\) and \(\sum_{i=0}^{n-1} B_{4, i} x^i=0\) related terms cancelled as well:

\[ \nu_k \text { in } A B:\left(\sum_{i=0}^n A_{4, i} x^i\right) B_{5, k}=0 \Longrightarrow \sum_{i=0}^n A_{4, i} x^i=0 \]
\[ \mu_k \text { in } A B:\left(\sum_{i=0}^{n-1} B_{4, i} x^i\right) A_{8, k}=0 \Longrightarrow \sum_{i=0}^{n-1} B_{4, i} x^i=0 \]

Which also implies \(A_{4, i}=B_{4, i}=0\) for all \(i\). We now focus on the first critical equation, \(\beta\), which has the same elements as in the KS case, except for the additional \(C_{9, i}\). Its left side vanishes completely, and on the right we have exactly one additional simulated instance wires set corresponding to \(C_{9, k}=1\) :

\[ 0=\sum_{i=0}^l a_i u_i(x)+\sum_{i=l+1}^m C_{6, i} u_i(x)-\sum_{i=0}^l a_{k, i} u_i(x) \]

Because of disjointness \({ }^{11}\) between \(u_i(x)\) for witness and instance sets of indices we have both \(\sum_{i=0}^l\left(a_i-a_{k, i}\right) u_i(x)=0\) and \(\sum_{i=l+1}^m C_{6, i} u_i(x)=0\), thus also \(a_i=a_{k, i}\) because of the linear independence of the first set. Then \(\mathcal{A}\) has reused the simulated instance \(\phi_k=\left\{a_{k, i}\right\}_{i=0}^l\), which concludes the proof.

BKSV21

Karim Baghery, Markulf Kohlweiss, Janno Siim, and Mikhail Volkhov. Another look at extraction and randomization of groth's zk-snark. In Financial Cryptography. 2021.