Lattice Enumeration for Tower NFS: a 521-bit Discrete Logarithm Computation

Gabrielle De Micheli (UCSD)

10-Feb-2022, 22:00-23:00 (2 years ago)

Abstract: The Tower variant of the Number Field Sieve (TNFS) is known to be asymptotically the most efficient algorithm to solve the discrete logarithm problem in finite fields of medium characteristics, when the extension degree is composite. A major obstacle to an efficient implementation of TNFS is the collection of algebraic relations, as it happens in dimensions greater than 2. This requires the construction of new sieving algorithms which remain efficient as the dimension grows. In this talk, I will present how we overcome this difficulty by considering a lattice enumeration algorithm which we adapt to this specific context. We also consider a new sieving area, a high-dimensional sphere, whereas previous sieving algorithms for the classical NFS considered an orthotope. Our new sieving technique leads to a much smaller running time, despite the larger dimension of the search space, and even when considering a larger target, as demonstrated by a record computation we performed in a 521-bit finite field GF(p^6). The target finite field is of the same form as finite fields used in recent zero-knowledge proofs in some blockchains. This is the first reported implementation of TNFS.

In the pre-talk, I will briefly present the core ideas of the quadratic sieve algorithm and its evolution to the Number Field Sieve algorithm.

number theory

Audience: researchers in the topic

Comments: pre-talk at 1:20pm


UCSD number theory seminar

Series comments: Most talks are preceded by a pre-talk for graduate students and postdocs. The pre-talks start 40 minutes prior to the posted time (usually at 1:20pm Pacific) and last about 30 minutes.

Organizers: Kiran Kedlaya*, Alina Bucur, Aaron Pollack, Cristian Popescu, Claus Sorensen
*contact for this listing

Export talk to