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
