{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,4]],"date-time":"2023-11-04T13:08:46Z","timestamp":1699103326312},"reference-count":27,"publisher":"American Institute of Mathematical Sciences (AIMS)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AMC"],"published-print":{"date-parts":[[2022]]},"abstract":"<p style='text-indent:20px;'>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.<\/p><\/jats:p>","DOI":"10.3934\/amc.2020119","type":"journal-article","created":{"date-parts":[[2021,1,8]],"date-time":"2021-01-08T11:45:31Z","timestamp":1610106331000},"page":"449","source":"Crossref","is-referenced-by-count":1,"title":["New discrete logarithm computation for the medium prime case using the function field sieve"],"prefix":"10.3934","volume":"16","author":[{"given":"Madhurima","family":"Mukhopadhyay","sequence":"first","affiliation":[{"name":"Applied Statistics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata, India 700108"}]},{"given":"Palash","family":"Sarkar","sequence":"additional","affiliation":[{"name":"Applied Statistics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata, India 700108"}]},{"given":"Shashank","family":"Singh","sequence":"additional","affiliation":[{"name":"Electrical Engineering & Computer Science, Indian Institute of Science Education and Research Bhopal, Bhopal 462066, Madhya Pradesh, India"}]},{"given":"Emmanuel","family":"Thom\u00e9","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, INRIA, Nancy, France"}]}],"member":"2321","reference":[{"key":"key-10.3934\/amc.2020119-1","doi-asserted-by":"publisher","unstructured":"G. Adj, A. Menezes, T. Oliveira and Francisco Rodr\u0131guez-Henr\u0131quez, Computing discrete logarithms in F36\u00b7 137 and F36\u00b7 163 using magma, Arithmetic of Finite Fields (WAIFI 2014)<\/i> (\u00c7etin Kaya Ko\u00e7, Sihem Mesnager, and Erkay Savas, eds.), 9061, Springer, Heidelberg, 2014.","DOI":"10.1007\/978-3-319-16277-5_1"},{"key":"key-10.3934\/amc.2020119-2","doi-asserted-by":"publisher","unstructured":"G. Adj, A. Menezes, T. Oliveira, F. Rodr\u00edguez-Henr\u00edquez.Weakness of $\\mathbb{F}_{6^{6\\cdot 1429}}$ and $\\mathbb{F}_{2^{4\\cdot 3041}}$ for discrete logarithm cryptography, Finite Fields and Their Applications<\/i>, 32<\/b> (2015), 148-170.","DOI":"10.1016\/j.ffa.2014.10.009"},{"key":"key-10.3934\/amc.2020119-3","doi-asserted-by":"publisher","unstructured":"L. M. Adleman, The function field sieve, in (L. M. Adleman and M.-D. A. Huang, eds.), ANTS, Lecture Notes in Computer Science<\/i>, 877, Springer, 1994,108\u2013121.","DOI":"10.1007\/3-540-58691-1_48"},{"key":"key-10.3934\/amc.2020119-4","doi-asserted-by":"publisher","unstructured":"L. M. Adleman, M.-D. A. Huang.Function field sieve method for discrete logarithms over finite fields, Inf. Comput.<\/i>, 151<\/b> (1999), 5-16.","DOI":"10.1006\/inco.1998.2761"},{"key":"key-10.3934\/amc.2020119-5","doi-asserted-by":"crossref","unstructured":"D. Adrian, et al., Imperfect forward secrecy: How Diffie-Hellman fails in practice, Commun. ACM<\/i>, 62<\/b> (2019), 106\u2013114.","DOI":"10.1145\/3292035"},{"key":"key-10.3934\/amc.2020119-6","doi-asserted-by":"publisher","unstructured":"R. Barbulescu, P. Gaudry, A. Joux, E. Thom\u00e9.A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, Lecture Notes in Computer Science<\/i>, 8441<\/b> (2014), 1-16.","DOI":"10.1007\/978-3-642-55220-5_1"},{"key":"key-10.3934\/amc.2020119-7","doi-asserted-by":"crossref","unstructured":"F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thom\u00e9, and P. Zimmermann, Comparing the difficulty of factorization and discrete logarithm: A240-digit experiment, IACR Cryptol. ePrint Arch.<\/i>, 697<\/b> (2020).","DOI":"10.1007\/978-3-030-56880-1_3"},{"key":"key-10.3934\/amc.2020119-8","doi-asserted-by":"publisher","unstructured":"D. Coppersmith.Fast evaluation of logarithms in fields of characteristic two, IEEE Transactions on Information Theory<\/i>, 30<\/b> (1984), 587-594.","DOI":"10.1109\/TIT.1984.1056941"},{"key":"key-10.3934\/amc.2020119-9","doi-asserted-by":"publisher","unstructured":"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<\/i>, IEEE Computer Society, 2013,201\u2013210.","DOI":"10.1109\/TC.2014.2331711"},{"key":"key-10.3934\/amc.2020119-10","doi-asserted-by":"publisher","unstructured":"W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Information Theory<\/i>, 22<\/b> (1976), 644\u2013654.","DOI":"10.1109\/tit.1976.1055638"},{"key":"key-10.3934\/amc.2020119-11","doi-asserted-by":"publisher","unstructured":"F. G\u00f6loglu, R. Granger, G. McGuire, J. Zumbr\u00e4gel.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<\/i>, 8043<\/b> (2013), 109-128.","DOI":"10.1007\/978-3-642-40084-1_7"},{"key":"key-10.3934\/amc.2020119-12","doi-asserted-by":"publisher","unstructured":"F. G\u00f6loglu, R. Granger, G. McGuire, J. Zumbr\u00e4gel.Solving a $6120$-bit DLP on a desktop computer, Lecture Notes in Computer Science<\/i>, 8282<\/b> (2013), 136-152.","DOI":"10.1007\/978-3-662-43414-7"},{"key":"key-10.3934\/amc.2020119-13","doi-asserted-by":"publisher","unstructured":"D. M. Gordon.Discrete logarithms in $ {\\rm{GF }}(p)$ using the number field sieve, SIAM J. Discrete Math.<\/i>, 6<\/b> (1993), 124-138.","DOI":"10.1137\/0406010"},{"key":"key-10.3934\/amc.2020119-14","doi-asserted-by":"publisher","unstructured":"R. Granger, T. Kleinjung, J. Zumbr\u00e4gel.Breaking '128-bit secure' supersingular binary curves \u2013 (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<\/i>, 8617<\/b> (2014), 126-145.","DOI":"10.1007\/978-3-662-44381-1_8"},{"key":"key-10.3934\/amc.2020119-15","unstructured":"R. Granger, T. Kleinjung and J. Zumbr\u00e4gel, Discrete logarithms in $GF(2^9234)$, NMBRTHRY List<\/i>, (2014)."},{"key":"key-10.3934\/amc.2020119-16","unstructured":"R. Granger, T. Kleinjung, and J. Zumbr\u00e4gel, Discrete logarithms in $GF(2^30750)$., NMBRTHRY List<\/i>, (2019)."},{"key":"key-10.3934\/amc.2020119-17","doi-asserted-by":"publisher","unstructured":"A. Joux, Algorithmic Cryptanalysis<\/i>, Cryptography and Network Security, Chapman & Hall\/CRC, 2009.","DOI":"10.1201\/9781420070033"},{"key":"key-10.3934\/amc.2020119-18","doi-asserted-by":"publisher","unstructured":"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<\/i>, Springer, 2013,177\u2013193.","DOI":"10.1007\/978-3-642-38348-9_11"},{"key":"key-10.3934\/amc.2020119-19","doi-asserted-by":"publisher","unstructured":"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<\/i>, 2369, Springer, 2002,431\u2013445.","DOI":"10.1007\/3-540-45455-1_34"},{"key":"key-10.3934\/amc.2020119-20","doi-asserted-by":"publisher","unstructured":"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<\/i>, Springer, 2006,254\u2013270.","DOI":"10.1007\/11761679_16"},{"key":"key-10.3934\/amc.2020119-21","unstructured":"T. Lange, Digital signature: DSA with medium fields, Available from: https:\/\/www.mysterytwisterc3.org\/images\/challenges\/mtc3-lange-01-dsasig-en.pdf<\/a>, 2011."},{"key":"key-10.3934\/amc.2020119-22","doi-asserted-by":"crossref","unstructured":"G. De Micheli, P. Gaudry and C. Pierrot, Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields, IACR Cryptol. ePrint Arch.<\/i>, 329<\/b>, 2020.","DOI":"10.1007\/978-3-030-56880-1_2"},{"key":"key-10.3934\/amc.2020119-23","unstructured":"National Institute of Standards and Technology, Digital Signature Algorithm, https:\/\/nvlpubs.nist.gov\/nistpubs\/FIPS\/NIST.FIPS.186-4.pdf<\/a>, 2013."},{"key":"key-10.3934\/amc.2020119-24","doi-asserted-by":"publisher","unstructured":"P. Sarkar, S. Singh.Fine tuning the function field sieve algorithm for the medium prime case, IEEE Transactions on Information Theory<\/i>, 62<\/b> (2016), 2233-2253.","DOI":"10.1109\/TIT.2016.2528996"},{"key":"key-10.3934\/amc.2020119-25","doi-asserted-by":"publisher","unstructured":"P. Sarkar and S. Singh, Fine tuning the function field sieve algorithm for the medium prime case, IACR Cryptol. ePrint Arch.<\/i>, 2014: 65<\/b> (2020). http:\/\/eprint.iacr.org\/2014\/065<\/a>.","DOI":"10.1109\/TIT.2016.2528996"},{"key":"key-10.3934\/amc.2020119-26","unstructured":"W. A. Stein, et al., Sage Mathematics Software<\/i>, The Sage Development Team, (2013). http:\/\/www.sagemath.org<\/a>."},{"key":"key-10.3934\/amc.2020119-27","unstructured":"The CADO-NFS Development Team, CADO-NFS, an implementation of the number field sieve algorithm, Development version, (2019)."}],"container-title":["Advances in Mathematics of Communications"],"original-title":[],"link":[{"URL":"http:\/\/aimsciences.org\/\/article\/doi\/10.3934\/amc.2020119?viewType=html","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T09:26:23Z","timestamp":1656494783000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.aimsciences.org\/article\/doi\/10.3934\/amc.2020119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022]]}},"alternative-id":["1930-5346_2022_3_449"],"URL":"https:\/\/doi.org\/10.3934\/amc.2020119","relation":{},"ISSN":["1930-5346","1930-5338"],"issn-type":[{"value":"1930-5346","type":"print"},{"value":"1930-5338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]}}}