Faster individual discrete logarithms in finite fields of composite extension degree

Guillevic, Aurore

doi:10.1090/mcom/3376

Faster individual discrete logarithms in finite fields of composite extension degree
HTML articles powered by AMS MathViewer

by Aurore Guillevic HTML | PDF

Math. Comp. 88 (2019), 1273-1301 Request permission

Abstract:

Computing discrete logarithms in finite fields is a main concern in cryptography. The best algorithms in large and medium characteristic fields (e.g., $\rm {GF}(p^2)$, $\rm {GF}(p^{12})$) are the Number Field Sieve and its variants (special, high-degree, tower). The best algorithms in small characteristic finite fields (e.g., $\rm {GF}(3^{6 \cdot 509})$) are the Function Field Sieve, Joux’s algorithm, and the quasipolynomial-time algorithm. The last step of this family of algorithms is the individual logarithm computation. It computes a smooth decomposition of a given target in two phases: an initial splitting, then a descent tree. While new improvements have been made to reduce the complexity of the dominating relation collection and linear algebra steps, resulting in a smaller factor basis (database of known logarithms of small elements), the last step remains at the same level of difficulty. Indeed, we have to find a smooth decomposition of a typically large element in the finite field. This work improves the initial splitting phase and applies to any nonprime finite field. It is very efficient when the extension degree is composite. It exploits the proper subfields, resulting in a much more smooth decomposition of the target. This leads to a new trade-off between the initial splitting step and the descent step in small characteristic. Moreover it reduces the width and the height of the subsequent descent tree.

References

G. Adj, Discrete logarithms in the cryptographically-interesting field GF$(3^{6*509})$, Elliptic Curve Cryptography Conference (ECC), Invited talk, September 2016, slides available at http://ecc2016.yasar.edu.tr/slides/ecc2016-gora.pdf.
G. Adj, Logaritmo discreto en campos finitos de característica pequeña: atacando la criptogrfía basada en emparejamientos de tipo 1, Phd thesis, Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional, Mexico, July 2016, http://delta.cs.cinvestav.mx/~francisco/Thesis_Gora_adj.pdf.
G. Adj, I. Canales-Martínez, N. Cruz-Cortés, A. Menezes, T. Oliveira, L. Rivera-Zamarripa, and F. Rodríguez-Henríquez, Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields, Cryptology ePrint Archive, Report 2016/914, 2016, http://eprint.iacr.org/2016/914.
G. Adj, I. Canales-Martinez, N. Cruz-Cortes, A. Menezes, T. Oliveira, F. Rodriguez-Henriquez, and L. Rivera-Zamarripa, Discrete logarithms in GF$(3^{6*509})$, Number Theory list, item 004923, July 18 2016, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;65bedfc8.1607.
G. Adj, A. Menezes, T. Oliveira, and F. Rodríguez-Henríquez, Computing discrete logarithms in $\mathbb {F}_{3^{6 \cdot 137}}$ and $\mathbb {F}_{3^{6 \cdot 163}}$ using Magma, Arithmetic of Finite Fields (WAIFI 2014) (Çetin Kaya Koç, Sihem Mesnager, and Erkay Savas, eds.), LNCS, vol. 9061, Springer, Heidelberg, 2014, https://eprint.iacr.org/2014/057, pp. 3–22.
Gora Adj, Alfred Menezes, Thomaz Oliveira, and Francisco Rodríguez-Henríquez, Weakness of $\Bbb F_{3^{6\cdot 509}}$ for discrete logarithm cryptography, Pairing-based cryptography—Pairing 2013, Lecture Notes in Comput. Sci., vol. 8365, Springer, Cham, 2014, pp. 20–44. MR 3174852, DOI 10.1007/978-3-319-04873-4_{2}
Gora Adj, Alfred Menezes, Thomaz Oliveira, and Francisco Rodríguez-Henríquez, Weakness of $\Bbb {F}_{3^{6\cdot 1429}}$ and $\Bbb {F}_{2^{4\cdot 3041}}$ for discrete logarithm cryptography, Finite Fields Appl. 32 (2015), 148–170. MR 3293408, DOI 10.1016/j.ffa.2014.10.009
Leonard M. Adleman, The function field sieve, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 108–121. MR 1322716, DOI 10.1007/3-540-58691-1_{4}8
Leonard M. Adleman and Ming-Deh A. Huang, Function field sieve method for discrete logarithms over finite fields, Inform. and Comput. 151 (1999), no. 1-2, 5–16. MR 1692254, DOI 10.1006/inco.1998.2761
R. Barbulescu, Algorithmes de logarithmes discrets dans les corps finis, thèse de doctorat, Université de Lorraine, Nancy, France, 2013, https://tel.archives-ouvertes.fr/tel-00925228.
R. Barbulescu, An appendix for a recent paper of Kim, Cryptology ePrint Archive, Report 2015/1076, 2015, http://eprint.iacr.org/2015/1076.
Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, and François Morain, Improving NFS for the discrete logarithm problem in non-prime finite fields, Advances in cryptology—EUROCRYPT 2015. Part I, Lecture Notes in Comput. Sci., vol. 9056, Springer, Heidelberg, 2015, pp. 129–155. MR 3344923, DOI 10.1007/978-3-662-46800-5_{6}
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}
Razvan Barbulescu, Pierrick Gaudry, and Thorsten Kleinjung, The tower number field sieve, Advances in cryptology—ASIACRYPT 2015. Part II, Lecture Notes in Comput. Sci., vol. 9453, Springer, Heidelberg, 2015, pp. 31–55. MR 3487762, DOI 10.1007/978-3-662-48800-3_{2}
I. F. Blake, R. Fuji-Hara, R. C. Mullin, and S. A. Vanstone, Computing logarithms in finite fields of characteristic two, SIAM Journal on Algebraic Discrete Methods 5 (1984), no. 2, 276–285, http://epubs.siam.org/doi/abs/10.1137/0605029, https://doi.org/10.1137/0605029.
I. F. Blake, R. C. Mullin, and S. A. Vanstone, Computing logarithms in $\text {GF}(2^n)$, CRYPTO’84 (G. R. Blakley and David Chaum, eds.), LNCS, vol. 196, Springer, Heidelberg, August 1984, https://doi.org/10.1007/3-540-39568-7_8, pp. 73–82.
I. Andrés Canales-Martínez, Implementación eficiente de prueba de suavidad para polinomios, Master thesis, Centro de Investigación y de Estudios Avanzados del Instituto, Politécnico Nacional, Departamento de Computación, México, Distrito Federal, Diciembre 2015, http://delta.cs.cinvestav.mx/~francisco/Thesis_IAC.pdf.
An Commeine and Igor Semaev, An algorithm to solve the discrete logarithm problem with the number field sieve, Public key cryptography—PKC 2006, Lecture Notes in Comput. Sci., vol. 3958, Springer, Berlin, 2006, pp. 174–190. MR 2423189, DOI 10.1007/11745853_{1}2
Don Coppersmith, Andrew M. Odlzyko, and Richard Schroeppel, Discrete logarithms in $\textrm {GF}(p)$, Algorithmica 1 (1986), no. 1, 1–15. MR 833115, DOI 10.1007/BF01840433
R. Cosset, Applications of theta functions for hyperelliptic curve cryptography, Thèse de doctorat, Université Henri Poincaré - Nancy I, Nancy, France, November 2011, https://tel.archives-ouvertes.fr/tel-00642951.
Whitfield Diffie and Martin E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), no. 6, 644–654. MR 437208, DOI 10.1109/tit.1976.1055638
Michael Drmota and Daniel Panario, A rigorous proof of the Waterloo algorithm for the discrete logarithm problem, Des. Codes Cryptogr. 26 (2002), no. 1-3, 229–241. In honour of Ronald C. Mullin. MR 1919879, DOI 10.1023/A:1016521712726
J.-G. Dumas and C. Pernet, Handbook of finite fields, ch. Computational linear algebra over finite fields, pp. 520–535, CRC Press Taylor & Francis Group, 2013.
P. Flajolet, X. Gourdon, and D. Panario, The complete analysis of a polynomial factorization algorithm over finite fields, J. Algorithms 40 (2001), no. 1, 37–81. MR 1841252, DOI 10.1006/jagm.2001.1158
Joshua Fried, Pierrick Gaudry, Nadia Heninger, and Emmanuel Thomé, A kilobit hidden SNFS discrete logarithm computation, Advances in cryptology—EUROCRYPT 2017. Part I, Lecture Notes in Comput. Sci., vol. 10210, Springer, Cham, 2017, pp. 202–231. MR 3652104, DOI 10.1007/978-3-319-56620-7_{8}
F. Göloglu, R. Granger, G. McGuire, and J. Zümbragel, Discrete logarithms in GF$(2^6120)$, Number Theory list, April 11 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;fe9605d9.1304.
Daniel M. Gordon, Discrete logarithms in $\textrm {GF}(p)$ using the number field sieve, SIAM J. Discrete Math. 6 (1993), no. 1, 124–138. MR 1201995, DOI 10.1137/0406010
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}
R. Granger, T. Kleinjung, and J. Zumbragel, Discrete logarithms in GF$(2^{9234})$, Number Theory list, item 004666, January 31 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;9aa2b043.1401.
R. Granger, T. Kleinjung, and J. Zumbragel, Discrete logarithms in the Jacobian of a genus 2 supersingular curve over GF$(2^{367})$ (DL in GF$(2^{4404})$), Number Theory list, item 004665, January 30, 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;23651c2.1401.
R. Granger, T. Kleinjung, and J. Zumbrägel, On the powers of 2, Cryptology ePrint Archive, Report 2014/300, 2014, http://eprint.iacr.org/2014/300.
Laurent Grémy, Aurore Guillevic, François Morain, and Emmanuel Thomé, Computing discrete logarithms in $\Bbb F_{p^6}$, Selected areas in cryptography—SAC 2017, Lecture Notes in Comput. Sci., vol. 10719, Springer, Cham, 2018, pp. 85–105. MR 3775580, DOI 10.1007/978-3-319-72565-9_{5}
Aurore Guillevic, Computing individual discrete logarithms faster in $\textrm {GF}(p^n)$ with the NFS-DL algorithm, Advances in cryptology—ASIACRYPT 2015. Part I, Lecture Notes in Comput. Sci., vol. 9452, Springer, Heidelberg, 2015, pp. 149–173. MR 3487734, DOI 10.1007/978-3-662-48797-6_{7}
A. Joux, Discrete logarithms in GF$(2^{6168})=$ GF$((2^{257})^{24})$, Number Theory list, May 21, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;49bb494e.1305.
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 and Reynald Lercier, The function field sieve is quite special, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 431–445. MR 2041102, DOI 10.1007/3-540-45455-1_{3}4
Antoine Joux and Reynald Lercier, Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method, Math. Comp. 72 (2003), no. 242, 953–967. MR 1954978, DOI 10.1090/S0025-5718-02-01482-5
Antoine Joux, Reynald Lercier, Nigel Smart, and Frederik Vercauteren, The number field sieve in the medium prime case, Advances in cryptology—CRYPTO 2006, Lecture Notes in Comput. Sci., vol. 4117, Springer, Berlin, 2006, pp. 326–344. MR 2422170, DOI 10.1007/11818175_{1}9
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
A. Joux and C. Pierrot, The special number field sieve in $\mathbb {F}_{p^n}$ - application to pairing-friendly constructions, PAIRING 2013 (Zhenfu Cao and Fangguo Zhang, eds.), LNCS, vol. 8365, Springer, Heidelberg, November 2014, pp. 45–61.
A. Joux and C. Pierrot, Discrete logarithm record in characteristic 3, GF$(3^{5\cdot 479})$ a 3796-bit field, Number Theory list, item 004745, September 15 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;1ff78abb.1409.
Michael Kalkbrener, An upper bound on the number of monomials in determinants of sparse matrices with symbolic entries, Math. Pannon. 8 (1997), no. 1, 73–82. MR 1439187
T. Kim, Extended tower number field sieve: A new complexity for medium prime case, Cryptology ePrint Archive, Report 2015/1027, 2015, http://eprint.iacr.org/2015/1027.
Taechan Kim and Razvan Barbulescu, Extended tower number field sieve: a new complexity for the medium prime case, Advances in cryptology—CRYPTO 2016. Part I, Lecture Notes in Comput. Sci., vol. 9814, Springer, Berlin, 2016, pp. 543–571. MR 3565295, DOI 10.1007/978-3-662-53018-4_{2}0
Taechan Kim and Jinhyuck Jeong, Extended tower number field sieve with application to finite fields of arbitrary composite extension degree, Public-key cryptography—PKC 2017. Part I, Lecture Notes in Comput. Sci., vol. 10174, Springer, Berlin, 2017, pp. 388–408. MR 3649119, DOI 10.1007/978-3-662-54365-8_{1}6
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}
B. A. LaMacchia and A. M. Odlyzko, Computation of discrete logarithms in prime fields, Des. Codes Cryptogr. 1 (1991), no. 1, 47–62. MR 1110012, DOI 10.1007/BF00123958
A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
Arjen K. Lenstra and Eric R. Verheul, The XTR public key system, Advances in cryptology—CRYPTO 2000 (Santa Barbara, CA), Lecture Notes in Comput. Sci., vol. 1880, Springer, Berlin, 2000, pp. 1–19. MR 1850033, DOI 10.1007/3-540-44598-6_{1}
H. W. Lenstra Jr., J. Pila, and Carl Pomerance, A hyperelliptic smoothness test. I, Philos. Trans. Roy. Soc. London Ser. A 345 (1993), no. 1676, 397–408. MR 1253501, DOI 10.1098/rsta.1993.0138
H. W. Lenstra Jr., J. Pila, and Carl Pomerance, A hyperelliptic smoothness test. II, Proc. London Math. Soc. (3) 84 (2002), no. 1, 105–146. MR 1863397, DOI 10.1112/plms/84.1.105
D. Matyukhin, Effective version of the number field sieve for discrete logarithms in the field GF$(p^k)$ (in Russian), Trudy po Discretnoi Matematike 9 (2006), 121–151, http://m.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=tdm&paperid=144&option_lang=eng.
A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Advances in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp. 224–314. MR 825593, DOI 10.1007/3-540-39757-4_{2}0
C. Pomerance, Analysis and comparison of some integer factoring algorithms, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 89–139. MR 700260
F. Rodríguez-Henríquez, Another initial splitting in small characteristic finite fields, Personal communication, November 30, 2015.
Palash Sarkar and Shashank Singh, A general polynomial selection method and new asymptotic complexities for the tower number field sieve algorithm, Advances in cryptology—ASIACRYPT 2016. Part I, Lecture Notes in Comput. Sci., vol. 10031, Springer, Berlin, 2016, pp. 37–62. MR 3598073, DOI 10.1007/978-3-662-53887-6_{2}
P. Sarkar and S. Singh, A generalisation of the conjugation method for polynomial selection for the extended tower number field sieve algorithm, Cryptology ePrint Archive, Report 2016/537, 2016, http://eprint.iacr.org/.
P. Sarkar and S. Singh, New complexity trade-offs for the (multiple) number field sieve algorithm in non-prime fields, EUROCRYPT 2016, Part I (Marc Fischlin and Jean-Sébastien Coron, eds.), LNCS, vol. 9665, Springer, Heidelberg, May 2016, https://eprint.iacr.org/2015/944, pp. 429–458.
P. Sarkar and S. Singh, Tower number field sieve variant of a recent polynomial selection method, Cryptology ePrint Archive, Report 2016/401, 2016, http://eprint.iacr.org/.
Oliver Schirokauer, Discrete logarithms and local units, Philos. Trans. Roy. Soc. London Ser. A 345 (1993), no. 1676, 409–423. MR 1253502, DOI 10.1098/rsta.1993.0139
Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, and David Woodruff, Practical cryptography in high dimensional tori, Advances in cryptology—EUROCRYPT 2005, Lecture Notes in Comput. Sci., vol. 3494, Springer, Berlin, 2005, pp. 234–250. MR 2352191, DOI 10.1007/11426639_{1}4
Marten van Dijk and David Woodruff, Asymptotically optimal communication for torus-based cryptography, Advances in cryptology—CRYPTO 2004, Lecture Notes in Comput. Sci., vol. 3152, Springer, Berlin, 2004, pp. 157–178. MR 2147501, DOI 10.1007/978-3-540-28628-8_{1}0
Y. Zhu, J. Zhuang, C. Lv, and D. Lin, Improvements on the individual logarithm step in extended tower number field sieve, Cryptology ePrint Archive, Report 2016/727, 2016, http://eprint.iacr.org/2016/727.