Discrete Logarithm Factory

Haetham Al Aswad; Emmanuel Thomé; Cécile Pierrot

doi:10.62056/ah2ip2fgx

Discrete Logarithm Factory

Authors

Haetham Al Aswad, Emmanuel Thomé, Cécile Pierrot

Haetham Al Aswad

Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
haetham dot al-aswad at inria dot fr

Emmanuel Thomé

Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
emmanuel dot thome at inria dot fr

Cécile Pierrot

Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
cecile dot pierrot at inria dot fr

Abstract

The Number Field Sieve and its variants are the best algorithms to solve the discrete logarithm problem in finite fields (except for the weak small characteristic case). The Factory variant accelerates the computation when several prime fields are targeted. This article adapts the Factory variant to non-prime finite fields of medium and large characteristic. A precomputation, solely dependent on an approximate finite field size and an extension degree, allows to efficiently compute discrete logarithms in a constant proportion of the finite fields of the given approximate size and extension degree. We combine this idea with two other variants of NFS, namely the tower and special variant. This combination improves the asymptotic complexity. We also notice that combining our approach with the MNFS variant would be an unnecessary complication as all the potential gain of MNFS is subsumed by our Factory variant anyway. Furthermore, we demonstrate how Chebotarev's density theorem allows to compute the density of finite fields that can be solved with a given precomputation. Finally, we provide experimental data in order to assess the practical reach of our approach.

References

[AAP23]

Haetham Al Aswad and Cécile Pierrot. Individual discrete logarithm with sublattice reduction. Designs, Codes and Cryptography, 2023. DOI: 10.1007/s10623-023-01282-w

Google Scholar ePrint

[ABD⁺15]

David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-Béguelin, and Paul Zimmermann. Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. In 22nd ACM Conference on Computer and Communications Security. 2015. DOI: 10.1145/2810103.2813707

Google Scholar ePrint

[Bar13]

Razvan Barbulescu. Algorithmes de logarithmes discrets dans les corps finis. PhD thesis, Université de Lorraine, 2013.

Google Scholar ePrint

[BGG⁺20]

Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann. Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II, volume 12171 of LNCS, pages 62–91. August 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-56880-1_3

Google Scholar ePrint

[BGGM15]

Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, and François Morain. Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 129–155. April 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-46800-5_6

Google Scholar ePrint

[BGJT14]

Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, and Emmanuel Thomé. A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 1–16. May 2014. Springer, Heidelberg. DOI: 10.1007/978-3-642-55220-5_1

Google Scholar ePrint

[BL14]

Daniel J. Bernstein and Tanja Lange. Batch NFS. In Antoine Joux and Amr M. Youssef, editors, SAC 2014, volume 8781 of LNCS, pages 38–58. August 2014. Springer, Heidelberg. DOI: 10.1007/978-3-319-13051-4_3

Google Scholar ePrint

[BLP93]

J. P. Buhler, A. K. Lenstra, and C. Pomerance. Factoring integers with the number field sieve. In A. K. Lenstra and Jr. H. W. Lenstra, editors, The development of the number field sieve, volume 1554 of Lecture Notes in Math., pages 50–94. 1993. Springer–Verlag. DOI: 10.1007/BFb0091539

Google Scholar ePrint

[BP14]

Razvan Barbulescu and Cécile Pierrot. The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields. LMS Journal of Computation and Mathematics, 17:230–246, 2014. DOI: 10.1112/S1461157014000369

Google Scholar ePrint

[CEP83]

E. Rodney Canfield, Paul Erdős, and Carl Pomerance. On a problem of Oppenheim concerning “factorisatio numerorum”. Journal of Number Theory, 17(1):1–28, 1983. DOI: 10.1016/0022-314X(83)90002-1

Google Scholar ePrint

[CHM⁺20]

Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, and Nicholas P. Ward. Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 738–768. May 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-45721-1_26

Google Scholar ePrint

[Cop93]

Don Coppersmith. Modifications to the Number Field Sieve. Journal of Cryptology, 6(3):169–180, March 1993. DOI: 10.1007/BF00198464

Google Scholar ePrint

[Cop94]

Don Coppersmith. Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm. Math. Comp., 62(205):333-350, 1994. DOI: 10.1090/S0025-5718-1994-1192970-7

Google Scholar ePrint

[DGP21]

Gabrielle De Micheli, Pierrick Gaudry, and Cécile Pierrot. Lattice Enumeration for Tower NFS: A 521-Bit Discrete Logarithm Computation. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part I, volume 13090 of LNCS, pages 67–96. December 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-92062-3_3

Google Scholar ePrint

[DM21]

Gabrielle De Micheli. Discrete Logarithm Cryptanalyses : Number Field Sieve and Lattice Tools for Side-Channel Attacks. PhD thesis, Université de Lorraine, May 2021.

Google Scholar ePrint

[FGHT17]

Joshua Fried, Pierrick Gaudry, Nadia Heninger, and Emmanuel Thomé. A Kilobit Hidden SNFS Discrete Logarithm Computation. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part I, volume 10210 of LNCS, pages 202–231. 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-56620-7_8

Google Scholar ePrint

[GGM16]

Pierrick Gaudry, Aurore Guillevic, and François Morain. Discrete logarithm record in $\operatorname{{GF}}(p^3)$ of 592 bits (180 decimal digits). August 2016.

Google Scholar ePrint

[GGM17]

Laurent Grémy, Aurore Guillevic, and François Morain. Breaking DLP in $GF(p^5)$ using 3-dimensional sieving. working paper or preprint. July 2017.

Google Scholar ePrint

[GKZ18]

Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel. On the discrete logarithm problem in finite fields of fixed characteristic. Transactions of the American Mathematical Society, 370(5):3129–3145, 2018. DOI: 10.1090/tran/7027

Google Scholar ePrint

[GMT16]

Aurore Guillevic, François Morain, and Emmanuel Thomé. Solving Discrete Logarithms on a 170-Bit MNT Curve by Pairing Reduction. In Roberto Avanzi and Howard M. Heys, editors, SAC 2016, volume 10532 of LNCS, pages 559–578. August 2016. Springer, Heidelberg. DOI: 10.1007/978-3-319-69453-5_30

Google Scholar ePrint

[Gor93]

Daniel M. Gordon. Discrete Logarithms in GF(P) Using the Number Field Sieve. SIAM J. Discret. Math., 6(1):124–138, 1993. DOI: 10.1137/0406010

Google Scholar ePrint

[Gr{\'{e}}17]

Laurent Grémy. Computations of discrete logarithms sorted by date. https://dldb.loria.fr/. 2017.

Google Scholar ePrint

[Gro16]

Jens Groth. On the Size of Pairing-Based Non-interactive Arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 305–326. May 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-49896-5_11

Google Scholar ePrint

[GS19]

Aurore Guillevic and Shashank Singh. On the alpha value of polynomials in the tower number field sieve algorithm. https://eprint.iacr.org/2019/885. Cryptology ePrint Archive, Report 2019/885. 2019.

Google Scholar ePrint

[GS21]

Aurore Guillevic and Shashank Singh. On the alpha value of polynomials in the Tower Number Field Sieve Algorithm. Mathematical Cryptology, 1(1):1–39, 2021.

Google Scholar ePrint

[Gui19]

Aurore Guillevic. Faster individual discrete logarithms in finite fields of composite extension degree. Mathematics of Computation, 88(317):1273–1301, January 2019. DOI: 10.1090/mcom/3376

Google Scholar ePrint

[GWC19]

Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. https://eprint.iacr.org/2019/953. Cryptology ePrint Archive, Report 2019/953. 2019.

Google Scholar ePrint

[HAKT14]

Kenichiro Hayasaka, Kazumaro Aoki, Tetsutaro Kobayashi, and Tsuyoshi Takagi. An experiment of number field sieve for discrete logarithm problem over $\text{GF}(p^n)$. JSIAM Letters, 6:53-56, 2014. DOI: 10.14495/jsiaml.6.53

Google Scholar ePrint

[JLSV06]

Antoine Joux, Reynald Lercier, Nigel Smart, and Frederik Vercauteren. The Number Field Sieve in the Medium Prime Case. In Cynthia Dwork, editor, CRYPTO 2006, volume 4117 of LNCS, pages 326–344. August 2006. Springer, Heidelberg. DOI: 10.1007/11818175_19

Google Scholar ePrint

[JP14]

Antoine Joux and Cécile Pierrot. The Special Number Field Sieve in $\mathbb{F}_{p^n}$ - Application to Pairing-Friendly Constructions. In Zhenfu Cao and Fangguo Zhang, editors, PAIRING 2013, volume 8365 of LNCS, pages 45–61. November 2014. Springer, Heidelberg. DOI: 10.1007/978-3-319-04873-4_3

Google Scholar ePrint

[KB16]

Taechan Kim and Razvan Barbulescu. Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part I, volume 9814 of LNCS, pages 543–571. August 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-53018-4_20

Google Scholar ePrint

[KBL14]

Thorsten Kleinjung, Joppe W. Bos, and Arjen K. Lenstra. Mersenne Factorization Factory. In Palash Sarkar and Tetsu Iwata, editors, ASIACRYPT 2014, Part I, volume 8873 of LNCS, pages 358–377. December 2014. Springer, Heidelberg. DOI: 10.1007/978-3-662-45611-8_19

Google Scholar ePrint

[KJ17]

Taechan Kim and Jinhyuck Jeong. Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree. In Serge Fehr, editor, PKC 2017, Part I, volume 10174 of LNCS, pages 388–408. March 2017. Springer, Heidelberg. DOI: 10.1007/978-3-662-54365-8_16

Google Scholar ePrint

[KW22]

Thorsten Kleinjung and Benjamin Wesolowski. Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic. Journal of the American Mathematical Society, 35:581-624, 2022. DOI: 10.1090/jams/985

Google Scholar ePrint

[LGST21]

Aude Le Gluher, Pierre-Jean Spaenlehauer, and Emmanuel Thomé. Refined Analysis of the Asymptotic Complexity of the Number Field Sieve. Mathematical Cryptology, 1(1):71–88, 2021.

Google Scholar ePrint

[LL93]

A. K. Lenstra and Jr. H. W. Lenstra, editors. The development of the number field sieve, volume 1554 of Lecture Notes in Math. Springer–Verlag 1993. DOI: 10.1007/BFb0091534

Google Scholar ePrint

[LLMP90]

Arjen K. Lenstra, Hendrik W. Lenstra Jr., Mark S. Manasse, and John M. Pollard. The Number Field Sieve. In 22nd ACM STOC, pages 564–572. May 1990. ACM Press. DOI: 10.1145/100216.100295

Google Scholar ePrint

[LO77]

J. C. Lagarias and A. M. Odlyzko. Effective versions of the Chebotarev density theorem. In A. Fröhlich, editor, Algebraic Number Fields: $L$ functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975), pages 409–464. 1977. Academic Press.

Google Scholar ePrint

[LV01]

Arjen K. Lenstra and Eric R. Verheul. Selecting Cryptographic Key Sizes. Journal of Cryptology, 14(4):255–293, September 2001. DOI: 10.1007/s00145-001-0009-4

Google Scholar ePrint

[Mat03]

Dimitry Matyukhin. On asymptotic complexity of computing discrete logarithms over GF(p). Discrete Mathematics and Applications, 13:27-50, 2003. DOI: 10.1515/156939203321669546

Google Scholar ePrint

[Mil20]

James S. Milne. Algebraic Number Theory (v3.08). 2020.

Google Scholar ePrint

[Pie15]

Cécile Pierrot. The Multiple Number Field Sieve with Conjugation and Generalized Joux-Lercier Methods. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 156–170. April 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-46800-5_7

Google Scholar ePrint

[Pol93]

John M. Pollard. The Lattice Sieve. In A. K. Lenstra and Jr. H. W. Lenstra, editors, The development of the number field sieve, volume 1554 of Lecture Notes in Math., pages 43–49. 1993. Springer–Verlag. DOI: doi.org/10.1007/BFb0091538

Google Scholar ePrint

[Rob22]

Oisín Robinson. An Implementation of the Extended Tower Number Field Sieve using 4d Sieving in a Box and a Record Computation in $\mathbb{F}_{p^4}$. arXiv preprint 2212.04999. 2022.

Google Scholar ePrint

[SS16a]

Palash Sarkar and Shashank Singh. A General Polynomial Selection Method and New Asymptotic Complexities for the Tower Number Field Sieve Algorithm. In Jung Hee Cheon and Tsuyoshi Takagi, editors, ASIACRYPT 2016, Part I, volume 10031 of LNCS, pages 37–62. December 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-53887-6_2

Google Scholar ePrint

[SS16b]

Palash Sarkar and Shashank Singh. New Complexity Trade-Offs for the (Multiple) Number Field Sieve Algorithm in Non-Prime Fields. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part I, volume 9665 of LNCS, pages 429–458. May 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-49890-3_17

Google Scholar ePrint

[SS19]

Palash Sarkar and Shashank Singh. A unified polynomial selection method for the (tower) number field sieve algorithm. Advances in Mathematics of Communications, 13(3):435-455, 2019. DOI: 10.3934/amc.2019028

Google Scholar ePrint

[TCG19]

Trusted Platform Module. The Trusted Computing Group, 2019.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ah2ip2fgx

History

Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07

How to cite

Haetham Al Aswad, Emmanuel Thomé, and Cécile Pierrot, Discrete Logarithm Factory. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ah2ip2fgx.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-3-23,
    author = "Aswad, Haetham Al and Thomé, Emmanuel and Pierrot, Cécile",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Discrete Logarithm Factory",
    volume = "1",
    number = "3",
    date = "2024-10-07",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/ah2ip2fgx"
}

TY - JOUR
AU - Al Aswad, Haetham
AU - Thomé, Emmanuel
AU - Pierrot, Cécile
PY  - 2024
TI  - Discrete Logarithm Factory
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 3
DO  - 10.62056/ah2ip2fgx
UR  - https://doi.org/10.62056/ah2ip2fgx
AB  - <p>The Number Field Sieve and its variants are the best     algorithms to solve the discrete logarithm problem in finite fields     (except for the weak small characteristic case). The Factory variant accelerates the computation when several prime fields are targeted. This article adapts the Factory variant to non-prime finite fields of medium and large characteristic. A precomputation, solely dependent on an approximate finite field size and an extension degree, allows to efficiently compute discrete logarithms in a constant proportion of the finite fields of the given approximate size and extension degree. We combine this idea with two other variants of NFS, namely the tower and special variant.     This combination improves the asymptotic complexity.     We also notice     that combining our approach with the MNFS variant would be an     unnecessary complication as all the potential gain of MNFS is     subsumed by our Factory variant anyway. Furthermore,     we demonstrate how Chebotarev's density theorem allows to compute the     density of finite fields that can be solved with a given precomputation. Finally, we provide experimental data in order to assess the practical reach of our approach. </p>
ER  -

Haetham Al Aswad, Emmanuel Thomé, and Cécile Pierrot, Discrete Logarithm Factory. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ah2ip2fgx.