Algebraic Group Model

Algebraic Group Model (AGM[1]) is a group-specific cryptographic model for assessing hardness assumptions in cryptography. Most well-known scheme is Standard Model[2], such as Factorization, Discrete Logarithm Problem, etc. For hardness assumptions, similar to Random Oracle Model for idealized hash function, GGM(Generic Group Model)[3] is often used to interacts with a black-box with hidden internal state variables which allows to perform a certain set of operations on the internal state variables, and which provides output only by allowing to check whether some state variables satisfy certain relations(like pairing operation). But the cons of GGM include representation-based exploits, and hard to deriving low bounds.

Before diving into Algebraic Group Model, we give a brief intro to the Algebraic Algorithm. Algebraic Algorithm, depicted as below, An algorithm A executed in an algebraic game G is called algebraic if for all groups elements Z that A outputs, it provides the representation of Z relative to all the previous received elements, which means A must provide a vector {z_i}, such that

if L is a list of group elements

So in the AGM, all the algorithms are modeled as algebraic, including the adversaries in the security experiments, and this for sure gives a weaker model assumption than GGM.

Take CDH Game as an example. For CDH, given (g, g^a, g^b), a and b is randomly selected from Z_q, g is group’s generator, and then calculate g^{ab}.
A CDH assumption is strongly related to the discrete logarithm assumption(given g^u, calculate u), since computing the discrete logarithm is the only known method for solving the CDH problem.

So does this “equivalence” kept in AGM? the answer is yes, and explained by CDH game as below.

The Algebraic Algorithm calculates the g^{xy}, and meanwhile returns z = {a, b, c} since a Algebraic Adversary assumption is given.

So applying the Algebraic Algorithm, the problem reduces to whether

, and the equivalent problem should be xy = xa + yb + c mod (p). Hence Challenger can only solve x unless the equation a = y mod (p) set by adversary. If so, constraints c = -ab should be satisfied, and the representation of Z is also valid.

If a doesn’t equal to y by modular p, x can be calculated by

So the challenger can set U = g^x (hide discrete logarithm x in G) or U = g^y(hide y in G) and choose the other uniform randomly, so the algorithm/adversary will not be able to distinguish that, and has only 1/2 probability to find the correct solution x by testing against U = g^x.

In this way, it’s shown that breaking CDH algebraically is as hard as solving DLP.

By AGM, paper[5] also observes that Strong DH, LRSW, and Tight BLS can also be reduced to DLP in AGM, EIGamal to DDH. And the most important work is to prove that the Groth16 scheme, a most efficient SNARK system, is secure under DLG assumption in AGM. This work has a big influence on and also is cited by the latest ZKP related works, like Plonk.

Reference

1. https://link.springer.com/chapter/10.1007/978-3-319-96881-0_2, https://www.youtube.com/watch?v=AKJh_NPOkD8
2. https://en.wikipedia.org/wiki/Standard_model_(cryptography)
3. Ueli Maurer(2005), Abstract Models of Computation in Cryptography
4. On Instantiating the Algebraic Group Model from
   Falsifiable Assumptions, https://eprint.iacr.org/2020/070.pdf