August  2022, 16(3): 449-464. doi: 10.3934/amc.2020119

New discrete logarithm computation for the medium prime case using the function field sieve

1. 

Applied Statistics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata, India 700108

2. 

Electrical Engineering & Computer Science, Indian Institute of Science Education and Research Bhopal, Bhopal 462066, Madhya Pradesh, India

3. 

Université de Lorraine, CNRS, INRIA, Nancy, France

* Corresponding author: Madhurima Mukhopadhyay

Received  February 2020 Revised  July 2020 Published  August 2022 Early access  December 2020

The present work reports progress in discrete logarithm computation for the general medium prime case using the function field sieve algorithm. A new record discrete logarithm computation over a 1051-bit field having a 22-bit characteristic was performed. This computation builds on and implements previously known techniques. Analysis indicates that the relation collection and descent steps are within reach for fields with 32-bit characteristic and moderate extension degrees. It is the linear algebra step which will dominate the computation time for any discrete logarithm computation over such fields.

Citation: Madhurima Mukhopadhyay, Palash Sarkar, Shashank Singh, Emmanuel Thomé. New discrete logarithm computation for the medium prime case using the function field sieve. Advances in Mathematics of Communications, 2022, 16 (3) : 449-464. doi: 10.3934/amc.2020119
References:
[1]

G. Adj, A. Menezes, T. Oliveira and Francisco Rodrıguez-Henrıquez, Computing discrete logarithms in F36· 137 and F36· 163 using magma, Arithmetic of Finite Fields (WAIFI 2014) (Çetin Kaya Koç, Sihem Mesnager, and Erkay Savas, eds.), 9061, Springer, Heidelberg, 2014. doi: 10.1007/978-3-319-16277-5_1.

[2]

G. AdjA. MenezesT. Oliveira and F. Rodríguez-Henríquez, Weakness of $\mathbb{F}_{6^{6\cdot 1429}}$ and $\mathbb{F}_{2^{4\cdot 3041}}$ for discrete logarithm cryptography, Finite Fields and Their Applications, 32 (2015), 148-170.  doi: 10.1016/j.ffa.2014.10.009.

[3]

L. M. Adleman, The function field sieve, in (L. M. Adleman and M.-D. A. Huang, eds.), ANTS, Lecture Notes in Computer Science, 877, Springer, 1994,108–121. doi: 10.1007/3-540-58691-1_48.

[4]

L. M. Adleman and M.-D. A. Huang, Function field sieve method for discrete logarithms over finite fields, Inf. Comput., 151 (1999), 5-16.  doi: 10.1006/inco.1998.2761.

[5]

D. Adrian, et al., Imperfect forward secrecy: How Diffie-Hellman fails in practice, Commun. ACM, 62 (2019), 106–114.

[6]

R. BarbulescuP. GaudryA. Joux and E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, Lecture Notes in Computer Science, 8441 (2014), 1-16.  doi: 10.1007/978-3-642-55220-5_1.

[7]

F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé, and P. Zimmermann, Comparing the difficulty of factorization and discrete logarithm: A240-digit experiment, IACR Cryptol. ePrint Arch., 697 (2020).

[8]

D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Transactions on Information Theory, 30 (1984), 587-594.  doi: 10.1109/TIT.1984.1056941.

[9]

J. Detrey, P. Gaudry and M. Videau, Relation collection for the function field sieve, in (A. Nannarelli, P.-M. Seidel, and P. T. P. Tang, eds.) IEEE Symposium on Computer Arithmetic, IEEE Computer Society, 2013,201–210. doi: 10.1109/TC.2014.2331711.

[10]

W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Information Theory, 22 (1976), 644–654. doi: 10.1109/tit.1976.1055638.

[11]

F. GölogluR. GrangerG. McGuire and J. Zumbrägel, On the function field sieve and the impact of higher splitting probabilities - application to discrete logarithms in $\mathbb{F}_{2^1971}$ and $\mathbb{F}_{2^3164}$, Lecture Notes in Computer Science, 8043 (2013), 109-128.  doi: 10.1007/978-3-642-40084-1_7.

[12]

F. GölogluR. GrangerG. McGuire and J. Zumbrägel, Solving a $6120$-bit DLP on a desktop computer, Lecture Notes in Computer Science, 8282 (2013), 136-152.  doi: 10.1007/978-3-662-43414-7.

[13]

D. M. Gordon, Discrete logarithms in $ {\rm{GF }}(p)$ using the number field sieve, SIAM J. Discrete Math., 6 (1993), 124-138.  doi: 10.1137/0406010.

[14]

R. GrangerT. Kleinjung and J. Zumbrägel, Breaking '128-bit secure' supersingular binary curves – (or how to solve discrete logarithms in $\mathbb{F}_{2^{4\cdot 1223}}$ and $\mathbb{F}_{2^{12\cdot 367}}$), Lecture Notes in Computer Science, 8617 (2014), 126-145.  doi: 10.1007/978-3-662-44381-1_8.

[15]

R. Granger, T. Kleinjung and J. Zumbrägel, Discrete logarithms in $GF(2^9234)$, NMBRTHRY List, (2014).

[16]

R. Granger, T. Kleinjung, and J. Zumbrägel, Discrete logarithms in $GF(2^30750)$., NMBRTHRY List, (2019).

[17]

A. Joux, Algorithmic Cryptanalysis, Cryptography and Network Security, Chapman & Hall/CRC, 2009. doi: 10.1201/9781420070033.

[18]

A. Joux, Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt, Springer, 2013,177–193. doi: 10.1007/978-3-642-38348-9_11.

[19]

A. Joux and R. Lercier, The function field sieve is quite special, in (C. Fieker and D. R. Kohel, eds.), ANTS, Lecture Notes in Computer Science, 2369, Springer, 2002,431–445. doi: 10.1007/3-540-45455-1_34.

[20]

A. Joux and R. Lercier, The function field sieve in the medium prime case, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt, Springer, 2006,254–270. doi: 10.1007/11761679_16.

[21]

T. Lange, Digital signature: DSA with medium fields, Available from: https://www.mysterytwisterc3.org/images/challenges/mtc3-lange-01-dsasig-en.pdf, 2011.

[22]

G. De Micheli, P. Gaudry and C. Pierrot, Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields, IACR Cryptol. ePrint Arch., 329, 2020.

[23]

National Institute of Standards and Technology, Digital Signature Algorithm, https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf, 2013.

[24]

P. Sarkar and S. Singh, Fine tuning the function field sieve algorithm for the medium prime case, IEEE Transactions on Information Theory, 62 (2016), 2233-2253.  doi: 10.1109/TIT.2016.2528996.

[25]

P. Sarkar and S. Singh, Fine tuning the function field sieve algorithm for the medium prime case, IACR Cryptol. ePrint Arch., 2014: 65 (2020). http://eprint.iacr.org/2014/065. doi: 10.1109/TIT.2016.2528996.

[26]

W. A. Stein, et al., Sage Mathematics Software, The Sage Development Team, (2013). http://www.sagemath.org.

[27]

The CADO-NFS Development Team, CADO-NFS, an implementation of the number field sieve algorithm, Development version, (2019).

show all references

References:
[1]

G. Adj, A. Menezes, T. Oliveira and Francisco Rodrıguez-Henrıquez, Computing discrete logarithms in F36· 137 and F36· 163 using magma, Arithmetic of Finite Fields (WAIFI 2014) (Çetin Kaya Koç, Sihem Mesnager, and Erkay Savas, eds.), 9061, Springer, Heidelberg, 2014. doi: 10.1007/978-3-319-16277-5_1.

[2]

G. AdjA. MenezesT. Oliveira and F. Rodríguez-Henríquez, Weakness of $\mathbb{F}_{6^{6\cdot 1429}}$ and $\mathbb{F}_{2^{4\cdot 3041}}$ for discrete logarithm cryptography, Finite Fields and Their Applications, 32 (2015), 148-170.  doi: 10.1016/j.ffa.2014.10.009.

[3]

L. M. Adleman, The function field sieve, in (L. M. Adleman and M.-D. A. Huang, eds.), ANTS, Lecture Notes in Computer Science, 877, Springer, 1994,108–121. doi: 10.1007/3-540-58691-1_48.

[4]

L. M. Adleman and M.-D. A. Huang, Function field sieve method for discrete logarithms over finite fields, Inf. Comput., 151 (1999), 5-16.  doi: 10.1006/inco.1998.2761.

[5]

D. Adrian, et al., Imperfect forward secrecy: How Diffie-Hellman fails in practice, Commun. ACM, 62 (2019), 106–114.

[6]

R. BarbulescuP. GaudryA. Joux and E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, Lecture Notes in Computer Science, 8441 (2014), 1-16.  doi: 10.1007/978-3-642-55220-5_1.

[7]

F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé, and P. Zimmermann, Comparing the difficulty of factorization and discrete logarithm: A240-digit experiment, IACR Cryptol. ePrint Arch., 697 (2020).

[8]

D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Transactions on Information Theory, 30 (1984), 587-594.  doi: 10.1109/TIT.1984.1056941.

[9]

J. Detrey, P. Gaudry and M. Videau, Relation collection for the function field sieve, in (A. Nannarelli, P.-M. Seidel, and P. T. P. Tang, eds.) IEEE Symposium on Computer Arithmetic, IEEE Computer Society, 2013,201–210. doi: 10.1109/TC.2014.2331711.

[10]

W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Information Theory, 22 (1976), 644–654. doi: 10.1109/tit.1976.1055638.

[11]

F. GölogluR. GrangerG. McGuire and J. Zumbrägel, On the function field sieve and the impact of higher splitting probabilities - application to discrete logarithms in $\mathbb{F}_{2^1971}$ and $\mathbb{F}_{2^3164}$, Lecture Notes in Computer Science, 8043 (2013), 109-128.  doi: 10.1007/978-3-642-40084-1_7.

[12]

F. GölogluR. GrangerG. McGuire and J. Zumbrägel, Solving a $6120$-bit DLP on a desktop computer, Lecture Notes in Computer Science, 8282 (2013), 136-152.  doi: 10.1007/978-3-662-43414-7.

[13]

D. M. Gordon, Discrete logarithms in $ {\rm{GF }}(p)$ using the number field sieve, SIAM J. Discrete Math., 6 (1993), 124-138.  doi: 10.1137/0406010.

[14]

R. GrangerT. Kleinjung and J. Zumbrägel, Breaking '128-bit secure' supersingular binary curves – (or how to solve discrete logarithms in $\mathbb{F}_{2^{4\cdot 1223}}$ and $\mathbb{F}_{2^{12\cdot 367}}$), Lecture Notes in Computer Science, 8617 (2014), 126-145.  doi: 10.1007/978-3-662-44381-1_8.

[15]

R. Granger, T. Kleinjung and J. Zumbrägel, Discrete logarithms in $GF(2^9234)$, NMBRTHRY List, (2014).

[16]

R. Granger, T. Kleinjung, and J. Zumbrägel, Discrete logarithms in $GF(2^30750)$., NMBRTHRY List, (2019).

[17]

A. Joux, Algorithmic Cryptanalysis, Cryptography and Network Security, Chapman & Hall/CRC, 2009. doi: 10.1201/9781420070033.

[18]

A. Joux, Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt, Springer, 2013,177–193. doi: 10.1007/978-3-642-38348-9_11.

[19]

A. Joux and R. Lercier, The function field sieve is quite special, in (C. Fieker and D. R. Kohel, eds.), ANTS, Lecture Notes in Computer Science, 2369, Springer, 2002,431–445. doi: 10.1007/3-540-45455-1_34.

[20]

A. Joux and R. Lercier, The function field sieve in the medium prime case, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt, Springer, 2006,254–270. doi: 10.1007/11761679_16.

[21]

T. Lange, Digital signature: DSA with medium fields, Available from: https://www.mysterytwisterc3.org/images/challenges/mtc3-lange-01-dsasig-en.pdf, 2011.

[22]

G. De Micheli, P. Gaudry and C. Pierrot, Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields, IACR Cryptol. ePrint Arch., 329, 2020.

[23]

National Institute of Standards and Technology, Digital Signature Algorithm, https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf, 2013.

[24]

P. Sarkar and S. Singh, Fine tuning the function field sieve algorithm for the medium prime case, IEEE Transactions on Information Theory, 62 (2016), 2233-2253.  doi: 10.1109/TIT.2016.2528996.

[25]

P. Sarkar and S. Singh, Fine tuning the function field sieve algorithm for the medium prime case, IACR Cryptol. ePrint Arch., 2014: 65 (2020). http://eprint.iacr.org/2014/065. doi: 10.1109/TIT.2016.2528996.

[26]

W. A. Stein, et al., Sage Mathematics Software, The Sage Development Team, (2013). http://www.sagemath.org.

[27]

The CADO-NFS Development Team, CADO-NFS, an implementation of the number field sieve algorithm, Development version, (2019).

Table 1.  A comparison of the difficulty of computing discrete logarithms for the medium prime case using the function field sieve algorithm
Ref $ \lceil\log_2 p\rceil $ $ n $ $ \lceil\log_2 p^n \rceil $ $ \lceil \log_2 \#\mathbb{B}\rceil $ $ \Lambda $
JL [20] 17 25 401 18 3.79
SS [24] 16 37 592 17 0.11
SS [24] 19 40 728 20 0.08
This work 22 50 1051 23 0.07
Ref $ \lceil\log_2 p\rceil $ $ n $ $ \lceil\log_2 p^n \rceil $ $ \lceil \log_2 \#\mathbb{B}\rceil $ $ \Lambda $
JL [20] 17 25 401 18 3.79
SS [24] 16 37 592 17 0.11
SS [24] 19 40 728 20 0.08
This work 22 50 1051 23 0.07
Table 2.  A comparison of the difficulty of computing discrete logarithms for the medium prime case using the function field sieve algorithm for Kummer extensions, i.e., for fields $\mathbb{F}_{p^n}$ satisfying $n\mathrel| (p-1)$
Ref $\lceil\log_2 p\rceil$ $n$ $\lceil\log_2 p^n \rceil$ $\lceil \log_2 \#\mathbb{B}\rceil$ $\Lambda$
JL[20]1930556184.29
Joux[18]25471175200.77
Joux[18]25571425200.13
Ref $\lceil\log_2 p\rceil$ $n$ $\lceil\log_2 p^n \rceil$ $\lceil \log_2 \#\mathbb{B}\rceil$ $\Lambda$
JL[20]1930556184.29
Joux[18]25471175200.77
Joux[18]25571425200.13
[1]

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

[2]

Josu Doncel, Nicolas Gast, Bruno Gaujal. Discrete mean field games: Existence of equilibria and convergence. Journal of Dynamics and Games, 2019, 6 (3) : 221-239. doi: 10.3934/jdg.2019016

[3]

Grégory Berhuy, Jean Fasel, Odile Garotta. Rank weights for arbitrary finite field extensions. Advances in Mathematics of Communications, 2021, 15 (4) : 575-587. doi: 10.3934/amc.2020083

[4]

Yves Achdou, Victor Perez. Iterative strategies for solving linearized discrete mean field games systems. Networks and Heterogeneous Media, 2012, 7 (2) : 197-217. doi: 10.3934/nhm.2012.7.197

[5]

Fabio Camilli, Francisco Silva. A semi-discrete approximation for a first order mean field game problem. Networks and Heterogeneous Media, 2012, 7 (2) : 263-277. doi: 10.3934/nhm.2012.7.263

[6]

Juan Pablo Maldonado López. Discrete time mean field games: The short-stage limit. Journal of Dynamics and Games, 2015, 2 (1) : 89-101. doi: 10.3934/jdg.2015.2.89

[7]

Theresa Lange, Wilhelm Stannat. Mean field limit of Ensemble Square Root filters - discrete and continuous time. Foundations of Data Science, 2021, 3 (3) : 563-588. doi: 10.3934/fods.2021003

[8]

Laura Aquilanti, Simone Cacace, Fabio Camilli, Raul De Maio. A Mean Field Games model for finite mixtures of Bernoulli and categorical distributions. Journal of Dynamics and Games, 2021, 8 (1) : 35-59. doi: 10.3934/jdg.2020033

[9]

Angela Aguglia, Antonio Cossidente, Giuseppe Marino, Francesco Pavese, Alessandro Siciliano. Orbit codes from forms on vector spaces over a finite field. Advances in Mathematics of Communications, 2022, 16 (1) : 135-155. doi: 10.3934/amc.2020105

[10]

Jaime Gutierrez. Reconstructing points of superelliptic curves over a prime finite field. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022022

[11]

Santos González, Llorenç Huguet, Consuelo Martínez, Hugo Villafañe. Discrete logarithm like problems and linear recurring sequences. Advances in Mathematics of Communications, 2013, 7 (2) : 187-195. doi: 10.3934/amc.2013.7.187

[12]

Juan Li, Wenqiang Li. Controlled reflected mean-field backward stochastic differential equations coupled with value function and related PDEs. Mathematical Control and Related Fields, 2015, 5 (3) : 501-516. doi: 10.3934/mcrf.2015.5.501

[13]

Andrew Comech. Weak attractor of the Klein-Gordon field in discrete space-time interacting with a nonlinear oscillator. Discrete and Continuous Dynamical Systems, 2013, 33 (7) : 2711-2755. doi: 10.3934/dcds.2013.33.2711

[14]

Marita Thomas, Sven Tornquist. Discrete approximation of dynamic phase-field fracture in visco-elastic materials. Discrete and Continuous Dynamical Systems - S, 2021, 14 (11) : 3865-3924. doi: 10.3934/dcdss.2021067

[15]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[16]

Keisuke Hakuta, Hisayoshi Sato, Tsuyoshi Takagi. On tameness of Matsumoto-Imai central maps in three variables over the finite field $\mathbb F_2$. Advances in Mathematics of Communications, 2016, 10 (2) : 221-228. doi: 10.3934/amc.2016002

[17]

Farzane Amirzade, Mohammad-Reza Sadeghi, Daniel Panario. QC-LDPC construction free of small size elementary trapping sets based on multiplicative subgroups of a finite field. Advances in Mathematics of Communications, 2020, 14 (3) : 397-411. doi: 10.3934/amc.2020062

[18]

Tetsuya Ishiwata, Kota Kumazaki. Structure preserving finite difference scheme for the Landau-Lifshitz equation with applied magnetic field. Conference Publications, 2015, 2015 (special) : 644-651. doi: 10.3934/proc.2015.0644

[19]

Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089

[20]

Yi Shi, Kai Bao, Xiao-Ping Wang. 3D adaptive finite element method for a phase field model for the moving contact line problems. Inverse Problems and Imaging, 2013, 7 (3) : 947-959. doi: 10.3934/ipi.2013.7.947

2020 Impact Factor: 0.935

Article outline

Figures and Tables

[Back to Top]