0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 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 at 16:18
  • $\begingroup$ @poncho I see now. Thanks. shoup.net/papers/dlbounds1.pdf $\endgroup$ – kelalaka Sep 1 at 16:24
  • $\begingroup$ I'll sketch the proof later, or someone can do it... $\endgroup$ – kelalaka Sep 1 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.