114-bit ECDLP solved on a curve with automorphisms over a prime field

There was a new ECDLP record that I missed last year. There was a press release on August 23, 2017. Now there is more information.

The details are published in the paper Solving 114-bit ECDLP for a Barreto-Naehrig Curve by Takuya Kusaka, Sho Joichi, Ken Ikuta, Md Al-Amin Khandaker, Yasuyuki Nogami, Satoshi Uehara, Nariyoshi Yamai and Sylvain Duquesne (appeared in proceedings of ICISC 2017).

The curve is a pairing-friendly BN curve over a prime field $F_p$. The curve has $j$-invariant 0, and so has an automorphism group of size 6. Hence, it is possible to perform the Pollard rho algorithm using equivalence classes of size 6.

I got a few more details from the authors. They used $n = 1024$ partitions for the random walk, and the “hash function” $\eta$ was chosen to be the least significant $\log_2(n)$ bits of the $x$-coordinate of the current curve point.

The paper writes that “The parallel implementation of the rho method by adopting a client-server model, using 2000 CPU cores took about 6 months”. They seem to have been lucky to get a collision earlier than expected: “the result of the authors attack is little bit better than the average number of rational points where a simple collision attack stops.”

The previous ECDLP record (due to Bos, Kaihara, Kleinjung, Lenstra and Montgomery) in the $F_p$ case was a 112-bits group size, published in 2012.

— Steven Galbraith

PS. It has been pointed out in the comments that there are other recent ECDLP records, such as the 118 bit record computation by Bernstein, Engels, Lange, Niederhagen, Paar, Schwabe and Zimmermann. This is a characteristic 2 computation, whereas I was focussed in this blog post on the $F_p$ case. But still it is a notable computation and should be celebrated.

This entry was posted in Uncategorized. Bookmark the permalink.

1 Response to 114-bit ECDLP solved on a curve with automorphisms over a prime field

1. Tanja Lange says:

Small nitpick regarding records:
We (in particular Ruben Niederhagen) have broken 117.35-bit ECDL in 2016 https://eprint.iacr.org/2016/382.pdf