Score:0

Crypto

assumption needed to work in Generic Group Model

baro77

3/21/24, 3:09 PM

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?

1 + 0

ggm

Score:5

Crypto

Geoffroy Couteau

3/21/24, 6:34 PM

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.

+ 9

baro77

3/21/24, 8:18 PM

thanks for the explanation!

rozbb

3/21/24, 8:32 PM

For additional reading, there's a great paper in the "Another look" series on the GGM: https://eprint.iacr.org/2006/230

baro77

3/21/24, 9:10 PM

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)?

Geoffroy Couteau

3/22/24, 1:35 PM

The last line talks about algorithms that use the group representation in a nontrivial way, which is by definition "non GGM" algorithms. You can directly view the GGM as a definition of what it means to exclude algos exploiting group elements in a nonblackbox way: we say that an algorithm uses the group representation in a blackbox way *if* the algorithm can be implemented in the GGM

Geoffroy Couteau

3/22/24, 1:36 PM

For example, index calculus uses the representation of group elements in a nonblackbox way because it needs a notion of "smallness" of the elements. For that reason (and others), it cannot be implemented in the GGM. On the other hand, baby step giant step does nothing on the sort and manipulates group elements in a blackbox way, and it can be implemented in the GGM.

baro77

3/23/24, 11:07 AM

Ok, so if I understand correctly, it seems a proof in GGM is as "reasonable" as we are confident that the actually used group cannot be exploited by non-trivial use of its representation (by "a non-GGM algo"); and in case of EC group, the curve choice is a critical mortgage on the proof actual validity. That said, any easy way to distinguish good curves from bad ones? And -given I have met them as alternatives- what's more "hazardous" in your opinion? GGM or KoE?

Geoffroy Couteau

3/23/24, 1:52 PM

I don't know of an easy way to distinguish good ones from bad ones, beyond extensive cryptanalysis, validation by the community, and (ideally) standardization. Regarding what's more hazardous: technically, GGM is, since KoE can be proven unconditionally true in the GGM, so KoE cannot be worse than GGM. Also, note that we have counterexamples to the GGM: schemes secure in the GGM which are broken with *any* concrete choice of group (even "good" ones!). We don't have anything like that for KoE: it's 'merely' a pretty bad assumption (but a really, really bad one).

baro77

3/24/24, 11:38 AM

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...? (https://blog.cryptographyengineering.com/2020/01/05/what-is-the-random-oracle-model-and-why-should-you-care-part-5/ is my source for that)

Geoffroy Couteau

3/24/24, 1:55 PM

Yes, they look very artificial :)

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: assumption needed to work in Generic Group Model

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.