Computation of a 30750-bit binary field discrete logarithm

Granger, Robert; Kleinjung, Thorsten; Lenstra, Arjen; Wesolowski, Benjamin; Zumbrägel, Jens

doi:10.1090/mcom/3669

Computation of a 30750-bit binary field discrete logarithm
HTML articles powered by AMS MathViewer

by Robert Granger, Thorsten Kleinjung, Arjen K. Lenstra, Benjamin Wesolowski and Jens Zumbrägel HTML | PDF

Math. Comp. 90 (2021), 2997-3022 Request permission

Abstract:

This paper reports on the computation of a discrete logarithm in the finite field $\mathbb {F}_{2^{30750}}$, breaking by a large margin the previous record, which was set in January 2014 by a computation in $\mathbb {F}_{2^{9234}}$. The present computation made essential use of the elimination step of the quasi-polynomial algorithm due to Granger, Kleinjung and Zumbrägel, and is the first large-scale experiment to truly test and successfully demonstrate its potential when applied recursively, which is when it leads to the stated complexity. It required the equivalent of about $2900$ core years on a single core of an Intel Xeon Ivy Bridge processor running at 2.6 GHz, which is comparable to the approximately $3100$ core years expended for the discrete logarithm record for prime fields, set in a field of bit-length $795$, and demonstrates just how much easier the problem is for this level of computational effort. In order to make the computation feasible we introduced several innovative techniques for the elimination of small degree irreducible elements, which meant that we avoided performing any costly Gröbner basis computations, in contrast to all previous records since early 2013. While such computations are crucial to the $L(\frac 1 4 + o(1))$ complexity algorithms, they were simply too slow for our purposes. Finally, this computation should serve as a serious deterrent to cryptographers who are still proposing to rely on the discrete logarithm security of such finite fields in applications, despite the existence of two quasi-polynomial algorithms and the prospect of even faster algorithms being developed.

References

Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, and Emmanuel Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, Advances in cryptology—EUROCRYPT 2014, Lecture Notes in Comput. Sci., vol. 8441, Springer, Heidelberg, 2014, pp. 1–16. MR 3213210, DOI 10.1007/978-3-642-55220-5_{1}
Antonia W. Bluher, On $x^{q+1}+ax+b$, Finite Fields Appl. 10 (2004), no. 3, 285–305. MR 2067599, DOI 10.1016/j.ffa.2003.08.004
Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann, 795-Bit factoring and discrete logarithms, NMBRTHRY listserv, December 2, 2019. Available at https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;fd743373.1912.
Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann, Factorization of RSA-250, NMBRTHRY listserv, February 28, 2020. Available at https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;dc42ccd1.2002.
Anne Canteaut, Sergiu Carpov, Caroline Fontaine, Tancrède Lepoint, María Naya-Plasencia, Pascal Paillier, and Renaud Sirdey, Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression, J. Cryptology 31 (2018), no. 3, 885–916. MR 3807972, DOI 10.1007/s00145-017-9273-9
Don Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory 30 (1984), no. 4, 587–594. MR 755785, DOI 10.1109/TIT.1984.1056941
Don Coppersmith, Modifications to the number field sieve, J. Cryptology 6 (1993), no. 3, 169–180. MR 1233462, DOI 10.1007/BF00198464
Andreas Enge and Pierrick Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith. 102 (2002), no. 1, 83–103. MR 1884958, DOI 10.4064/aa102-1-6
Faruk Göloğlu, Robert Granger, Gary McGuire, and Jens Zumbrägel, On the function field sieve and the impact of higher splitting probabilities: application to discrete logarithms in $\Bbb F_{2^{1971}}$ and $\Bbb F_{2^{3164}}$, Advances in cryptology—CRYPTO 2013. Part II, Lecture Notes in Comput. Sci., vol. 8043, Springer, Heidelberg, 2013, pp. 109–128. MR 3126472, DOI 10.1007/978-3-642-40084-1_{7}
Faruk Göloğlu, Robert Granger, Gary McGuire, and Jens Zumbrägel, Solving a 6120-bit DLP on a desktop computer, Selected areas in cryptography—SAC 2013, 2014, pp. 136–152.
Faruk Göloğlu, Robert Granger, Gary McGuire, and Jens Zumbrägel, Discrete logarithms in $GF(2^{6120})$, NMBRTHRY listserv, April 11, 2013. Available at https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;fe9605d9.1304.
Faruk Göloğlu, Robert Granger, Gary McGuire, and Jens Zumbrägel, Discrete logarithms in $GF(2^{1971})$, NMBRTHRY listserv, February 19, 2013. Available at https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;f7755cbe.1302.
Robert Granger, Philipp Jovanovic, Bart Mennink, and Samuel Neves, Improved masking for tweakable blockciphers with applications to authenticated encryption, Advances in cryptology—EUROCRYPT 2016. Part I, Lecture Notes in Comput. Sci., vol. 9665, Springer, Berlin, 2016, pp. 263–293. MR 3516373, DOI 10.1007/978-3-662-49890-3_{1}1
Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel, Breaking ‘128-bit secure’ supersingular binary curves (or how to solve discrete logarithms in $\Bbb F_{2^{4\cdot 1223}}$ and $\Bbb F_{2^{12\cdot 367}}$), Advances in cryptology—CRYPTO 2014. Part II, Lecture Notes in Comput. Sci., vol. 8617, Springer, Heidelberg, 2014, pp. 126–145. MR 3239465, DOI 10.1007/978-3-662-44381-1_{8}
Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel, On the discrete logarithm problem in finite fields of fixed characteristic, Trans. Amer. Math. Soc. 370 (2018), no. 5, 3129–3145. MR 3766844, DOI 10.1090/tran/7027
Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel, On the powers of 2, Cryptology ePrint Archive, April 29, 2014. Available at https://eprint.iacr.org/2014/300.
Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel, Discrete logarithms in the Jacobian of a genus 2 supersingular curve over $GF(2^{367})$, NMBRTHRY listserv, January 30, 2014. Available at https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;23651c2.1401.
Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel, Discrete logarithms in $GF(2^{9234})$, NMBRTHRY listserv, January 31, 2014. Available at https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;9aa2b043.1401.
Antoine Joux, A new index calculus algorithm with complexity $L(1/4+o(1))$ in small characteristic, Selected areas in cryptography—SAC 2013, Lecture Notes in Comput. Sci., vol. 8282, Springer, Heidelberg, 2014, pp. 355–379. MR 3218492, DOI 10.1007/978-3-662-43414-7_{1}8
Antoine Joux, Discrete logarithms in $GF(2^{1778})$, NMBRTHRY listserv, February 11, 2013. Available at https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;7d4dd9a6.1302.
Antoine Joux, Discrete logarithms in $GF(2^{6168})$, NMBRTHRY listserv, May 21, 2013. Available at https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;49bb494e.1305.
Antoine Joux, Discrete logarithms in $GF(2^{4080})$, NMBRTHRY listserv, March 22, 2013. Available at https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;71e65785.1303.
Antoine Joux and Cécile Pierrot, Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms: simplified setting for small characteristic finite fields, Advances in cryptology—ASIACRYPT 2014. Part I, Lecture Notes in Comput. Sci., vol. 8873, Springer, Heidelberg, 2014, pp. 378–397. MR 3297559, DOI 10.1007/978-3-662-45611-8_{2}0
Thorsten Kleinjung, Discrete logarithms in $GF(2^{1279})$, NMBRTHRY listserv, October 17, 2014. Available at https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;256db68e.1410.
Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé, Joppe W. Bos, Pierrick Gaudry, Alexander Kruppa, Peter L. Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, and Paul Zimmermann, Factorization of a 768-bit RSA modulus, Advances in cryptology—CRYPTO 2010, Lecture Notes in Comput. Sci., vol. 6223, Springer, Berlin, 2010, pp. 333–350. MR 2725602, DOI 10.1007/978-3-642-14623-7_{1}8
Thorsten Kleinjung, Joppe W. Bos, and Arjen K. Lenstra, Mersenne factorization factory, Advances in cryptology—ASIACRYPT 2014. Part I, Lecture Notes in Comput. Sci., vol. 8873, Springer, Heidelberg, 2014, pp. 358–377. MR 3297558, DOI 10.1007/978-3-662-45611-8_{1}9
Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra, Christine Priplata, and Colin Stahlke, Computation of a 768-bit prime field discrete logarithm, Advances in cryptology—EUROCRYPT 2017. Part I, Lecture Notes in Comput. Sci., vol. 10210, Springer, Cham, 2017, pp. 185–201. MR 3652103, DOI 10.1007/978-3-319-56620-7_{7}
Thorsten Kleinjung and Benjamin Wesolowski, Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic, Cryptology ePrint Archive, June 25, 2019. Available at https://eprint.iacr.org/2019/751, to appear in J. Amer. Math. Soc.
Brian A. LaMacchia and Andrew M. Odlyzko, Solving large sparse linear systems over finite fields, Advances in cryptology—CRYPTO ’90, 1991, pp. 109–133.
Cornelius Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Research Nat. Bur. Standards 45 (1950), 255–282. MR 0042791, DOI 10.6028/jres.045.026
H. W. Lenstra Jr., Finding isomorphisms between finite fields, Math. Comp. 56 (1991), no. 193, 329–347. MR 1052099, DOI 10.1090/S0025-5718-1991-1052099-2