# 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.

9 questions
Filter by
Sorted by
Tagged with
75 views

### Reduction from factoring to RSA and the Oracle RSA problem

Recently I read some papers related to RSA Brown16,AM09,BNPS01 and I learned that there is a variant problem of RSA is The oracle RSA problem (or one more RSA Problem) is $m+1$ copies of the classic ...
• 311
159 views

### 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....
• 730
115 views

### 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 ...
1 vote
125 views

### 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 ...
• 930
1 vote
331 views

### 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 ...
• 379
511 views

### 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 ...
• 379
711 views

### 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 ...
1 vote