Moving SNARKs from the generic to algebraic group model
The most efficient zk-SNARK construction known, due to Jens Groth, has a security proof written in what’s called the generic group model.
What that essentially boils down to is — an adversary needs to choose in advance a set of coefficients, before seeing the common reference string; and as their candidate proof must output elements that are a combination of the CRS elements with these cofficients, *chosen in advance*.
(To be 1000% precise the GGM allows the adversary in principle a bit more power, but it boils down to exactly this when the CRS comprises of uniform elements evaluated in the exponent on fixed low degree polynomials — low being negligible in the field size; see [Groth 16] for details and also an attempt to formalize this in Section 5 of https://eprint.iacr.org/2018/187.)
As a concrete and typical example; say the CRS is
g^x ,…,g^{x^q},
for an unknown uniform x∈F.
A GGM adversary A as described, would have to output (in the exponent) an evaluation P(x) of a degree q polynomial P for a polynomial P he chose in advance.
The intuitive justification for the GGM here being, when the discrete log is hard, seeing this CRS shouldn’t give the adversary A any information, so he loses nothing by choosing P in advance.
Still, here’s a “silly” thing A could do that isn’t allowed in the GGM:
Look at the value of the first bit of g^x; choose a polynomial P according to that value, and output P(x) for that P.
This corresponds to choosing a linear combination of the CRS as your output, but not choosing it in advance, rather, adaptively according to the CRS.
The algebraic group model (AGM) exactly captures this ability:
An AGM adversary A is allowed to output any element they want, but must output along with it coefficients of a combination of the CRS that produces this element.
Fuchsbauer, Kiltz and Loss, who introduced the model, show that Groth’s zk-SNARK is also safe against AGM adversaries. In fact, their statement can be easily generalized to the following:
Define the q-power discrete log assumption for a group G:
Given g^x ,…,g^{x^q}, for an unknown uniform x∈F and uniform generator g∈G, the probability of an efficient A to find x is negligible.
Say a SNARK has a degree q-crs if its CRS consist of elements g^F(z) for fixed, possibly multivariate polynomials F of degree at most q, at a uniform point z.
Then we have
“Thm”: Whenever a SNARK, with a degree q-CRS is safe against GGM adversaries, it is also safe against AGM adversaries assuming the q-power DLA.
Proof sketch: Given the q-DLA challenge, we can construct a CRS of the right form and distribution (with some re-randomizing if the CRS is multivariate polynomials)
Given this CRS, an AGM adversary’s proof elements will correspond to polynomials of degree q in x.
And the verifier’s checks will corresponds (say if it’s a pairing based SNARK) to some degree 2q polynomials in x.
We now have two options: This polynomial of the verifier equation is identically zero. In this case, the adversary’s polynomials succeed against any CRS (also one not previously seen), and can be used to construct an attack of a GGM adversary (whose probability of success is negligible by assumption of the theorem).
Otherwise the verifier’s equation polynomial is a polynomial Q of degree at most 2q, that is zero at x, but not identically 0. So factoring this polynomial we can find x, and solve the q-power DL!