Paper 2020/329

Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields

Gabrielle De Micheli, Pierrick Gaudry, and Cécile Pierrot

Abstract

We study the discrete logarithm problem at the boundary case between small and medium characteristic finite fields, which is precisely the area where finite fields used in pairing-based cryptosystems live. In order to evaluate the security of pairing-based protocols, we thoroughly analyze the complexity of all the algorithms that coexist at this boundary case: the Quasi-Polynomial algorithms, the Number Field Sieve and its many variants, and the Function Field Sieve. We adapt the latter to the particular case where the extension degree is composite, and show how to lower the complexity by working in a shifted function field. All this study finally allows us to give precise values for the characteristic asymptotically achieving the highest security level for pairings. Surprisingly enough, there exist special characteristics that are as secure as general ones.

Note: This version is the version of our article published at Crypto 2020 to which we added 4 pages of appendix.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2020
Keywords
discrete logarithm problempairingnumber field sievefunction field sieve
Contact author(s)
pierrick gaudry @ loria fr
cecile pierrot @ inria fr
gabrielle de-micheli @ inria fr
History
2020-11-05: last of 4 revisions
2020-03-17: received
See all versions
Short URL
https://ia.cr/2020/329
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/329,
      author = {Gabrielle De Micheli and Pierrick Gaudry and Cécile Pierrot},
      title = {Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields},
      howpublished = {Cryptology ePrint Archive, Paper 2020/329},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/329}},
      url = {https://eprint.iacr.org/2020/329}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.