Questions tagged [ggm]

The Generic Group Model is one where the adversary can only perform group operations thru an oracle, which is hypothetized to respect the group axioms. Attacks that apply in the Generic Group Model thus apply to actual groups, but not necessarily the other way around.

Filter by
Sorted by
Tagged with
10 votes
2 answers

Is the one-more discrete log problem hard in the Generic Group Model?

In the Generic Group Model (GGM), a concrete cyclic group of (known) order $n$ is replaced with an idealized version: a random encoding for group elements is chosen, and the adversary only gets access ...
Pieter Wuille's user avatar
7 votes
1 answer

Difference between Generic Group Models

I'm trying to understand the difference between the (classical) Generic Group Model as it is described by Shoup [Shoup] and the somewhat restricted Generic Group Model as it is described by Schnorr ...
einsteinwein's user avatar
6 votes
1 answer

Polynomial Breakdown in proof of lower bounds on Discrete Log in the Generic Group

In Shoup's proof of the hardness of discrete log in the generic group in this paper, he mentions that: At any step in the game, the algorithm has computed a list $F_1,\dots,F_k$ of linear polynomials ...
Poseidon23's user avatar
5 votes
1 answer

Generic group model: use of polynomials in the proof of the master theorem

I've been looking at the paper of Boneh, Boyen, Goh Hierarchical Identity Based Encryption with Constant Size Ciphertext which contains a general theorem (Theorem A.2) about the advantage of an ...
JT1's user avatar
  • 375
1 vote
1 answer

Discrete Logarithm in the generic group model is hard - Theorem by Shoup

In Shoups well-known paper Lower bounds for Discrete Logarithms and Related Problems he proves that the Discrete Logarithm Problem is hard in the generic group model (if group operation and inverse ...
einsteinwein's user avatar
1 vote
1 answer

Proof Dlog is hard in generic group model

I want to know a proof for why the dlog problem is hard in the generic group model. But i can't find any resources online. Can someone please provide me a link or an explanation?
SuppenGeist's user avatar
1 vote
1 answer

Does generic group black box model prohibit MSB of discrete logarithm?

Black box generic models prohibit calculation of discrete logarithm in groups of order $q=2p+1$ where $p,q$ are random primes to $\Omega(\sqrt{p})$ steps (refer Discrete Logarithm in the generic group ...
Turbo's user avatar
  • 908
0 votes
1 answer

assumption needed to work in Generic Group Model

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....
baro77's user avatar
  • 720