0
$\begingroup$

so I'm reading everywhere that the Pollard Rho for Dlog's complexity of $g^a \pmod{n}$ is $\mathcal O(\sqrt{n})$.

Shouldn't it be $\mathcal{O}(\sqrt{q})$ with $q$ the order of $g$?

$\endgroup$
8
  • 1
    $\begingroup$ Note that of course $\mathcal O(\sqrt q)\subseteq\mathcal O(\sqrt n)$ since $q\leq n$, hence claiming the algorithm to be in $\mathcal O(\sqrt n)$ is not wrong, it is just not a tight bound. In the typical context of "safe primes", Geoffroy Couteau's answer applies and we even have $\mathcal O(\sqrt q)=\mathcal O(\sqrt n)$. $\endgroup$
    – yyyyyyy
    Feb 27 '16 at 15:48
  • $\begingroup$ well, even $\mathcal{O}(\sqrt{q}) = \mathcal{O}(\sqrt{n})$ for what is worth. I don't understand why we keep using these asymptotic notations in cryptography... they convey no practical meaning. $\endgroup$ Feb 27 '16 at 19:18
  • 1
    $\begingroup$ I do not agree; although benchmarks convey more "practical meanings", they are heavily dependent of the particular computer that was used. In particular for DLOG attacks on finite fields, asymptotic complexities (written with the L() function for subexponential complexities) translate quite accurately to efficiency improvements. Knowing that the complexity of the best attack on some DLOG on a group is $O(\sqrt{q})$ suggests taking q twice bigger (in bit-length) than your desired security parameter, and it gives you a quite good estimation on the size of the modulus. $\endgroup$ Feb 28 '16 at 0:34
  • $\begingroup$ the fact that some cryptosystem could be broken if the algorithm would work in $\sqrt{q}$ operations instead of $\sqrt{n}$ operations shows how important some distinctions are no? (I guess from this is especially important from the point of view of the attacker) $\endgroup$ Feb 28 '16 at 4:43
  • 1
    $\begingroup$ That section doesn't say n is the modulus. ​ ​ $\endgroup$
    – user991
    Feb 29 '16 at 17:22
4
$\begingroup$

The complexity of Pollard-Rho is indeed $O(\sqrt{\text{ord}(g)})$, but even though $n$ refers to the modulus, their statement might be correct depending of the context. If the modulus considered in your situation is a "classical" modulus in crypto (e.g. $n = (2q+1)^k$ for a prime $q$ and a small $k$, etc), as the modulus will be in general chosen so that ord$(g)$ is big, $n = t\cdot \text{ord}(g)$ for a small constant $t$ so $O(\sqrt{\text{ord}(g)}) = O(\sqrt{n})$.

$\endgroup$
0
2
$\begingroup$

It should be $\;\; O\Big(\hspace{-0.07 in}\sqrt{\text{order of g}}\hspace{-0.02 in}\Big) \:$ group exponentiations $\;\;$ .

When $q$ is the order of $g$, that will be $\;\; O\hspace{-0.04 in}\left(\hspace{-0.04 in}\sqrt{q}\hspace{-0.02 in}\right) \:$ group exponentiations $\;\;$ .

When $n$ is the order of $g$, that will be $\;\; O\hspace{-0.04 in}\left(\hspace{-0.04 in}\sqrt{n}\hspace{-0.02 in}\right) \:$ group exponentiations $\;\;$ .

Were they still using $n$ for [the modulus from which one
takes the multiplicative group] when they wrote $\hspace{.02 in}O\hspace{-0.04 in}\left(\hspace{-0.04 in}\sqrt{n}\hspace{-0.02 in}\right)\hspace{.02 in}$?

$\endgroup$
2
  • $\begingroup$ yes, from the wikipedia page: en.wikipedia.org/wiki/… $\endgroup$ Feb 27 '16 at 15:03
  • $\begingroup$ I just made the question more precise. ​ ​ $\endgroup$
    – user991
    Feb 27 '16 at 15:15

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.