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

Question

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?

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.