Paper 2014/065

Fine Tuning the Function Field Sieve Algorithm for the Medium Prime Case

Palash Sarkar and Shashank Singh

Abstract

This work builds on the variant of the function field sieve (FFS) algorithm for the medium prime case introduced by Joux and Lercier in 2006. We make several contributions. The first contribution uses a divisibility and smoothness technique and goes on to develop a sieving method based on the technique. This leads to significant practical efficiency improvements in the descent phase and also provides improvement to Joux's pinpointing technique. The second contribution is a detailed analysis of the degree of freedom and the use of a walk technique in the descent phase of the algorithm. Such analysis shows that it is possible to compute discrete logarithms over certain fields which are excluded by the earlier analyses performed by Joux and Lercier (2006) and Joux (2013). In concrete terms, we present computations of discrete logs for fields with 16 and 19-bit prime characteristic. We also provide concrete analysis of the effectiveness of the FFS algorithm for certain fields of characteristic ranging from 16-bit to 32-bit primes. The final contribution is to perform a complete asymptotic analysis of the FFS algorithm for fields $\mathbb{F}_Q$ with $p=L_Q(1/3,c)$. This closes gaps and corrects errors in the analysis earlier performed by Joux-Lercier and Joux and also provides new insights into the asymptotic behaviour of the algorithm.

Note: A rounding error in the published version in IEEE.IT has been corrected.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. IEEE Transactions on Information Theory
DOI
10.1109/TIT.2016.2528996
Keywords
discrete logarithm problem
Contact author(s)
sha2nk singh @ gmail com
History
2020-03-04: last of 4 revisions
2014-01-29: received
See all versions
Short URL
https://ia.cr/2014/065
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/065,
      author = {Palash Sarkar and Shashank Singh},
      title = {Fine Tuning the Function Field Sieve Algorithm for the Medium Prime Case},
      howpublished = {Cryptology ePrint Archive, Paper 2014/065},
      year = {2014},
      doi = {10.1109/TIT.2016.2528996},
      note = {\url{https://eprint.iacr.org/2014/065}},
      url = {https://eprint.iacr.org/2014/065}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.