7
$\begingroup$

The security of the EC25519 is given as 128 bits, but since the order of the group is 252 bits shouldn't the security be 126 bits? Given as half the magnitude of the underlying field, since DLP algorithms such as Baby-Step-Giant-Step and Pollard-Rho generally have a complexity of O(sqrt(n)), n being the order of group. At least in theoretical terms. What am I missing?

$\endgroup$
5
$\begingroup$

In the usual definition of security of Elliptic Curves, curve25519 security is in fact 126 bits.

If look at safecurves's rho page you can see the rho complexity for curve25519 is $2^{125.8}$ in accordance to what you say.

Curve25519 author basically doesn't accept that definition of security. In the Curve25519 paper he states in section 1:

Every known attack is more expensive than performing a brute-force search on a typical 128-bit secret-key cipher

Which, accordingly to the usual definition of security, would provide 128 bit security.

He provides a little bit more details in Section 3, subsection "Generic discrete logarithms by the rho and kangaroo methods". But the best paper describing his critics to standard definition of security is Non-uniform cracks in the concrete: the power of free precomputation.

$\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.