Vol. 2, 2019

Download this article
Download this article For screen
For printing
Recent Volumes
2: ANTS XIII
1: ANTS X
The Open Book Series
About the Series
Ethics Statement
 
Other MSP Publications
Higher-dimensional sieving for the number field sieve algorithms

Laurent Grémy

Vol. 2 (2019), No. 1, 275–291
Abstract

Since 2016 and the introduction of the exTNFS (extended tower number field sieve) algorithm, the security of cryptosystems based on nonprime finite fields, mainly the pairing- and torus-based ones, 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 1, i.e., a search space of dimension 2. However, exTNFS uses bivariate polynomials of at least four coefficients. If sieving in dimension 2 is well described in the literature, sieving in higher dimensions has 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-4 sieving, but the hardness of dimension-6 sieving.

Keywords
discrete logarithm, finite fields, sieve algorithms, medium characteristic
Mathematical Subject Classification 2010
Primary: 11T71
Milestones
Received: 2 March 2018
Revised: 18 May 2018
Accepted: 7 September 2018
Published: 13 February 2019
Authors
Laurent Grémy
Univ Lyon, CNRS, ENS de Lyon, Inria, Université Claude Bernard Lyon 1, LIP UMR 5668, F-69007
Lyon
France