0
$\begingroup$

Consider NIST 192 elliptic curve group https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf. What is the time complexity of discrete log problem of it? Is it Pollard $\rho$ i.e $\sqrt{N}$, where $N$ is the size of the group?

$\endgroup$
4
  • 1
    $\begingroup$ Welcome to Cryptography.SE What did you search 1? Also, the question is lack of knowledge on $N$, is it prime or smooth number, or ...? $\endgroup$
    – kelalaka
    May 29 at 19:18
  • $\begingroup$ P-192 is dead $\endgroup$
    – kelalaka
    May 29 at 19:37
  • $\begingroup$ How? What is the attack complexity? $\endgroup$
    – Sanu
    May 29 at 20:19
  • $\begingroup$ Parallel Pollard's $\rho$ did you read the necessary part on the links? $\endgroup$
    – kelalaka
    May 30 at 9:25
1
$\begingroup$

Yes, Pollard's rho, in it's distributed version, is the best known method to break the DLP in the Elliptic Curve groups in NIST's SP 800-186 (draft) section 4 linked in the question, and NIST's FIPS 186-4 appendix D which specifies the P-192 curve alluded to in the question. It's also the method used in most¹ similar record attacks.

Work complexity is $\mathcal O(\sqrt n\,\log^2(n))$ where $n$ is the group order². Time for attack is $\mathcal O(\sqrt n\,\log^2(n)/d)$, where $d$ the number of devices running in parallel. Each device needs little memory.

The standard reference is Paul C. van Oorschot & Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications, in JOC, 1999.


¹ An exception is attacks where the secret private exponent thought is in an known interval, where Pollard's kangaroo has an edge. That can be viewed as a variant of Pollard's rho, and the asymptotic cost is not improved for the general case.

² The term $\log^2(n)$ reflects the cost of a group operation. That would be $\log^2(h\,n)$ in general, where $h$ is the cofactor. But $h=1$ for P-192, and $h\le8$ in all curves in the two NIST documents, so we can remove it from the equations.

$\endgroup$

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.