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 are the only computations that can be performed on group elements). Theorem 1 in the paper says that the probability that a generic algorithm $A$ solves this problem is bounded by $\mathcal{O}(m^2/p)$ (m is the number of oracle queries, p the prime group order). The part that I don't understand is the following:

If we insist that $A$ succeed with probability bounded by a positive constant (e.g., 1/2) to the below, this theorem translates into a lower bound $\Omega(\sqrt{p})$ of the number of group operations queried by $A$.

Can someone explain this conclusion to me?


1 Answer 1


Let $K$ be the constant (which doesn't depend of $p$) such that the probability is bounded by $K\frac{m^2}{p}$. (a such $K$ exists by definition of $\mathcal{O}$).

It means that if an adversary solves the discrete logarithm problem with probability more than $\frac{1}{2}$, we obtain.

$$K\frac{m^2}{p}\geq \frac{1}{2}$$.

It implies that

$$m\geq \sqrt{\frac{p}{2K}} $$

Thus we deduce that $m$ -which is in fact a function of $p$, is lower bounded by $K'\sqrt{p}$, with $K':=\sqrt{\frac{1}{2K}}$ a constant which doesn't depend of $p$.

It's equivalent to write $m\in \Omega(\sqrt{p})$ (according to the Knuth notation).

Notice now that $\sqrt{p}$ is exponential in the size of the input, and you will deduce that any generic adversary is not efficient against DLog.

  • $\begingroup$ Thank you very much! :-) $\endgroup$ Commented Oct 20, 2021 at 14:05

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.