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  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, 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

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

[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.  Google Scholar

[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). Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

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

[16]

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

[17]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[21]

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

[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. Google Scholar

[23]

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

[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.  Google Scholar

[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.  Google Scholar

[26]

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

[27]

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

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

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

[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.  Google Scholar

[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). Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

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

[16]

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

[17]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[21]

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

[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. Google Scholar

[23]

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

[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.  Google Scholar

[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.  Google Scholar

[26]

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

[27]

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

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]

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 & Games, 2020  doi: 10.3934/jdg.2020033

[2]

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

[3]

Wenya Qi, Padmanabhan Seshaiyer, Junping Wang. A four-field mixed finite element method for Biot's consolidation problems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020127

[4]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[5]

Illés Horváth, Kristóf Attila Horváth, Péter Kovács, Miklós Telek. Mean-field analysis of a scaling MAC radio protocol. Journal of Industrial & Management Optimization, 2021, 17 (1) : 279-297. doi: 10.3934/jimo.2019111

[6]

Josselin Garnier, Knut Sølna. Enhanced Backscattering of a partially coherent field from an anisotropic random lossy medium. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1171-1195. doi: 10.3934/dcdsb.2020158

[7]

Matúš Tibenský, Angela Handlovičová. Convergence analysis of the discrete duality finite volume scheme for the regularised Heston model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1181-1195. doi: 10.3934/dcdss.2020226

[8]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

[9]

Jann-Long Chern, Sze-Guang Yang, Zhi-You Chen, Chih-Her Chen. On the family of non-topological solutions for the elliptic system arising from a product Abelian gauge field theory. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3291-3304. doi: 10.3934/dcds.2020127

[10]

Daniele Bartolucci, Changfeng Gui, Yeyao Hu, Aleks Jevnikar, Wen Yang. Mean field equations on tori: Existence and uniqueness of evenly symmetric blow-up solutions. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3093-3116. doi: 10.3934/dcds.2020039

[11]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025

[12]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026

[13]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076

[14]

Xiaoli Lu, Pengzhan Huang, Yinnian He. Fully discrete finite element approximation of the 2D/3D unsteady incompressible magnetohydrodynamic-Voigt regularization flows. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 815-845. doi: 10.3934/dcdsb.2020143

[15]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[16]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443

[17]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[18]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[19]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[20]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021011

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (19)
  • HTML views (30)
  • Cited by (0)

[Back to Top]