Paper 2018/967

Higher dimensional sieving for the number field sieve algorithms

Laurent Grémy

Abstract

Since 2016 and the introduction of the exTNFS (extended Tower Number Field Sieve) algorithm, the security of cryptosystems based on non- prime finite fields, mainly the paring and torus-based one, is being reassessed. The feasibility of the relation collection, a crucial step of the NFS variants, is especially investigated. It usually involves polynomials of degree one, i.e., a search space of dimension two. However, exTNFS uses bivariate polynomials of at least four coefficients. If sieving in dimension two is well described in the literature, sieving in higher dimension received significantly less attention. We describe and analyze three different generic algorithms to sieve in any dimension for the NFS algorithms. Our implementation shows the practicability of dimension four sieving, but the hardness of dimension six sieving.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Contact author(s)
laurent gremy @ ens-lyon fr
History
2018-10-14: received
Short URL
https://ia.cr/2018/967
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/967,
      author = {Laurent Grémy},
      title = {Higher dimensional sieving for the number field sieve algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2018/967},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/967}},
      url = {https://eprint.iacr.org/2018/967}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.