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?


1 Answer 1


The lower bound for the generic group model is proved by Victor Shoup,

He showed in Lower bounds and Discrete Logarithm and Related Problems

Lower bounds on the complexity of these problems are proved that match the known upper bound: any generic algorithm must perform $\Omega(p^{1/2})$ group operations, where $p$ is the largest prime dividing the order of the group.

Generic Group model;

To process with a group we must present them with bit strings. This must be a bijection, 1-1 and onto. A generic algorithm works independently from the representation of the group. They are not allowed to work with efficient representation as field and rings instead they are working with an oracle with the random representation $\sigma$ of the group. The oracle executes the group operation $$\text{add}(\sigma(a),\sigma(b)) = \sigma(a+b)$$ and $$\text{inv}(\sigma(x)) = \sigma(-x) $$ The running time is measured by the number of oracle calls.

The importance of this model is providing an answer to the question

  • What is the fastest generic algorithm for breaking a cryptographic hardness assumption?

The lower bound for the generic group model is proved by Victor Shoup. It is proven that any algorithm with constant success probability has at least $\mathcal{O}(\sqrt{q})$-time where $q$ is the largest factor of the group size $n$. The generic algorithms are

  • Baby-step Giant-step needs an upper bound knowledge of the group size and has running time $\mathcal{O}(\sqrt{n} \log n)$.
  • The Pohlig-Hellman algorithm needs the prime factorization of $n$ and has $\mathcal{O}(\sqrt{q} \log q)$ complexity.

Generic Group model has the same problem as the Random Oracle model - Real model vs Ideal model. It can be shown that Cryptographic schemes can be secure under the generic group model but trivially broken if instantiated 1,2

  • 2
    $\begingroup$ Actually, in the 'generic group' model, where the only allowed operations are the group operation ("a+b"), inversion ("-a"), and checking for equality (does $a=b$?), you can prove that the best algorithm takes $O(\sqrt{n})$ time - he was asking for a write up of this. Of course, any implementation of a group will allow some operations beyond this (potentially not useful operations, but still, it makes the proof invalid). $\endgroup$
    – poncho
    Sep 1, 2019 at 16:18
  • $\begingroup$ @poncho I see now. Thanks. shoup.net/papers/dlbounds1.pdf $\endgroup$
    – kelalaka
    Sep 1, 2019 at 16:24
  • $\begingroup$ I'll sketch the proof later, or someone can do it... $\endgroup$
    – kelalaka
    Sep 1, 2019 at 21:48
  • $\begingroup$ @kelalaka Can you sketch the proof? $\endgroup$
    – Turbo
    Jun 5, 2023 at 19:25
  • 1
    $\begingroup$ @Turbo: are you asking if we include in our allowed operations a CDH Oracle (given the elements $G, xG, yG$, returns $xyG$), does it still takes $\Omega( \sqrt{n} )$ time? At first glance, I would think so - the general idea of "you're computing values of the form $xG + yH$ and can't tell where you are until you happen upon a collision, that is, $xG + yH = zG + wH$, still would appear to hold with the additional operation - however, something might come up with a more detailed proof. Obviously Shoup's original proof wouldn't apply... $\endgroup$
    – poncho
    Jan 8 at 13:42

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.