Solving 94-bit ECDLP with 70 Computers in Parallel

Authors: Shunsuke Miyoshi, Yasuyuki Nogami, Takuya Kusaka, Nariyoshi Yamai

Abstract:

Elliptic curve discrete logarithm problem(ECDLP) is one of problems on which the security of pairing-based cryptography is based. This paper considers Pollard’s rho method to evaluate the security of ECDLP on Barreto-Naehrig(BN) curve that is an efficient pairing-friendly curve. Some techniques are proposed to make the rho method efficient. Especially, the group structure on BN curve, distinguished point method, and Montgomery trick are well-known techniques. This paper applies these techniques and shows its optimization. According to the experimental results for which a large-scale parallel system with MySQL is applied, 94-bit ECDLP was solved about 28 hours by parallelizing 71 computers.

Keywords: Pollard’s rho method, BN curve, Montgomery multiplication.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1108905

References:

[1] F. Vercauteren, “Optimal pairings,” IEEE Transactions on Information Theory, Vol. 56, No.1, pp. 455-461, 2010.
[2] Y. Nogami, Y. Sakemi, H. Kato, M. Akane, and Y.Morikawa, “Integer Variable χ-based Cross Twisted Ate Pairing and Its Optimization for Barreto-Naehrig Curve,” IEICE Transactions on Fundamentals of Electronics, IEICE Transactions, Vol. 2009, No. 8, pp. 1859-1867, 2009.
[3] P. S. L. M. Barreto and M. Naehrig,“Pairing–Friendly Elliptic Curves of Prime Order,” SAC 2005, LNCS, vol. 3897, pp. 319–331, 2006.
[4] H. Cohen and G. Frey ed., “Handbook of Elliptic and Hyperelliptic Curve Cryptography, ” Chapman & Hall, 2006.
[5] J. Pollard, “Monte Carlo Methods for Index Computation (mod p),” Math. Comp, vol. 32, pp. 918–924, 1978.
[6] P. L. Montgomery, “Speeding the Pollard and Elliptic Curve Methods of Factorization,” MATH. OF COMPUT., vol. 48, no. 177, pp. 243–264, 1987.
[7] Joppe W. Bos, Craig Costello, and Andrea Miele, “Elliptic and Hyperelliptic Curves: a Practical Security Analysis,” PKC 2014, vol. 8383, pp. 203–220, 2014