0
$\begingroup$

KZG poly-commitment & QAP linear PCP can be proved sound under Knowledge of Exponent assumption or Generic Group Model (I take it for granted from lecture 6 and 9 of ZK-MOOC https://zk-learning.org/), and it seems to me GGM is the preferred one because it permits less trusted setup parameters.

If I have understood correctly, GGM core is about considering opaque the group elements encoding/labelling, requiring an oracle to derive a group element from previous ones by means of group operation.

Given its usage in the examples stated above, how can we assume that actually used groups respect this property? Is maybe about the group having a very high cardinality and its elements being very sparse in the container space (so it's almost impossible to get a group element just randomly picking up a point, or to pre-calculate all of them), or there's something else?

Trying to further explain my doubt: it seems a situation similar to Random Oracle Model: Fiat-Shamir works in ROM, and we use it "wanting to believe" an actual hash function is similar enough to a random oracle... which kind of (wrong but not too much wrong) concession are we making when we say we can work in generic group model?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Groups do simply not respect this property. The right way to think about it is to view these results as stating something about the algorithms: if a protocol is secure in the GGM, it means that no algorithms that uses the group operations in a blackbox way can break the protocol. Then, we simply use groups for which we do not see clear ways to attack common assumptions without using the group in a blackbox ways.

Finite fields are not like that, since we have index calculus algorithms. Elliptic curves tend to be like that, but it's purely heuristic: in the 90's, we had curves that seemed like that, but turned out not to be, because of the MOV attack (that uses a pairing to move the dlog problem to a finite field, where it can be solved via index calculus). But none of that is a property of the groups per se: it's a property of what's we've found so far about algorithms that use the group representation in a nontrivial way.

Improve this answer
$\endgroup$
9
  • $\begingroup$ thanks for the explanation! $\endgroup$
    – baro77
    Commented Mar 21, 2023 at 20:18
  • 2
    $\begingroup$ For additional reading, there's a great paper in the "Another look" series on the GGM: eprint.iacr.org/2006/230 $\endgroup$
    – rozbb
    Commented Mar 21, 2023 at 20:32
  • $\begingroup$ I'm thinking to your answer and I'm not sure to have understood how we exclude algos exploiting group elements representation in a non-blackbox way: could you elaborate more on "Then, we simply use groups for which we do not see clear ways to attack common assumptions without using the group in a blackbox ways." ... and why non-blackbox way is a trivial way (from the last line)? $\endgroup$
    – baro77
    Commented Mar 21, 2023 at 21:10
  • 1
    $\begingroup$ just for the sake of curiosity, do GGM counterexamples look "artificial" as CGH/MRH separation for ROM, having an input to be parsed like a program etc etc...? (blog.cryptographyengineering.com/2020/01/05/… is my source for that) $\endgroup$
    – baro77
    Commented Mar 24, 2023 at 11:38
  • 2
    $\begingroup$ Yes, they look very artificial :) $\endgroup$
    – Geoffroy Couteau
    Commented Mar 24, 2023 at 13:55

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.