1
$\begingroup$

I understand that in the non-interactive linear form (page 15 of Groth16: https://eprint.iacr.org/2016/260.pdf), given $A$ and $B$ in the proof $(A,B,C)$, the simulator can compute the $C$ by: $C =\frac{AB-\alpha\beta-D}{\delta} $ where $D = \sum^{l}_{i=0} {a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x))} $.

However, I don't get how the simulator would work when the scheme is compiled to SNARK.Here, when all keys are raised to power form, we have: $e(A,B) = e(C, g^\delta) e(g^\alpha, g^\beta) e(D, g)$. I see that $e(C, g^\delta) = e(A,B)/(e(g^\alpha, g^\beta) e(D, g))$, but how could the simulator extract the $G_1$ element $C$ from the $G_t$ element $e(C, g^\delta)$?

$\endgroup$

1 Answer 1

1
+50
$\begingroup$

The simulator would not generate random elements of $\mathbb G_T$, but would as before generate uniform random values $A,B\in\mathbb Z/p\mathbb Z$ and compute $C$ per your equation. They would then SNARK-ify these numbers by $[A]=g^A\in\mathbb G_1$, $[B]=h^B\in\mathbb G_2$ and $[C]=g^C\in\mathbb G_1$ per the bottom of page 6 (note that these SNARK-ified elements are all uniformly distributed in their respective groups).

The equation $e([A],[B])=e([C],h^\delta) e(g^\alpha,h^\beta)e(g,h)^D$ would then automatically be true by the bilinearity property of $e$.

$\endgroup$
5
  • $\begingroup$ Many thanks for the response. What's intriguing to me is that: why would one allow the simulator to know the trap door (the toxic values such as the $\delta$ - shouldn't they be "forgotten" by the set up process)? In another word, why would the scheme allow the simulator to be "super-power" like a set-up? $\endgroup$
    – Sean
    Commented Jun 14, 2022 at 16:59
  • $\begingroup$ I don't think of values such as $\delta$ as "toxic" values; they're provided to verifiers as part of $\mathbf\sigma$ and I think of verifier information as public. $\endgroup$
    – Daniel S
    Commented Jun 14, 2022 at 17:08
  • $\begingroup$ But on page 17 0f Groth16 (eprint.iacr.org/2016/260.pdf), the trapdoor $\tau$ is defined as $\tau = (\alpha, \beta, \gamma, \delta, x)$. The verifier key $\sigma$ is raised to power in group $G_1$ and $G_2$. I don't think the $\delta$ is visible to verifier (i.e., the verifier can only see $g^\delta$), if I'm understanding it right. $\endgroup$
    – Sean
    Commented Jun 15, 2022 at 1:43
  • $\begingroup$ Apologies, you are correct. Providing the simulator with $\tau$ is part of the defined rules of section 2.2; I would interpret this as the simulator being able to come up with the exact same proof if exactly the same blinding values were chosen at random. $\endgroup$
    – Daniel S
    Commented Jun 15, 2022 at 5:46
  • $\begingroup$ Thanks again for clarification! $\endgroup$
    – Sean
    Commented Jun 15, 2022 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.