2022.08.12: Daniel J. Bernstein, "Fast norm computation in smooth-degree Abelian number fields", talk for refereed paper, Algorithmic Number Theory Symposium 2022 (ANTS-XV). [vertical slides] [horizontal slides] [video] Paper abstract:

This paper presents a fast method to compute algebraic norms of integral elements of smooth-degree cyclotomic fields, and, more generally, smooth-degree Galois number fields with commutative Galois groups. The typical scenario arising in S-unit searches (for, e.g., class-group computation) is computing a Theta(n log n)-bit norm of an element of weight n^{1/2+o(1)} in a degree-n field; this method then uses n(log n)^{3+o(1)} bit operations.

An n(log n)^{O(1)} operation count was already known in two easier special cases: norms from power-of-2 cyclotomic fields via towers of power-of-2 cyclotomic subfields, and norms from multiquadratic fields via towers of multiquadratic subfields. This paper handles more general Abelian fields by identifying tower-compatible integral bases supporting fast multiplication; in particular, there is a synergy between tower-compatible Gauss-period integral bases and a fast-multiplication idea from Rader.

As a baseline, this paper also analyzes various standard norm-computation techniques that apply to arbitrary number fields, concluding that all of these techniques use at least n^2(log n)^{2+o(1)} bit operations in the same scenario, even with fast subroutines for continued fractions and for complex FFTs. Compared to this baseline, algorithms dedicated to smooth-degree Abelian fields find each norm n/(log n)^{1+o(1)} times faster, and finish norm computations inside S-unit searches n^2/(log n)^{1+o(1)} times faster.

2022.08.11: Tanja Lange, "S-unit attacks", invited plenary talk, Algorithmic Number Theory Symposium 2022 (ANTS-XV). [slides] [video] Talk abstract:

Lattice-based cryptography is a strong contender for post-quantum cryptography, having scored three out of four announced winners in the NIST post-quantum competition. All three of those winners use structured lattices derived from cyclotomic fields. A standard argument for the security of structured lattices is a "worst-case-to-average-case reduction" proving that an attack would imply an attack against (approximate) Ideal-SVP, the problem of finding short nonzero elements of a nonzero ideal of the ring of integers of a cyclotomic field. This raises the question of whether Ideal-SVP is in fact hard. This talk explains S-unit attacks against Ideal-SVP, including some recent results.

2021.08.20: Daniel J. Bernstein, "S-unit attacks", invited plenary talk, SIAM Conference on Applied Algebraic Geometry 2021. [slides] [video] Talk abstract:

Within post-quantum cryptography, lattice-based cryptography has attracted attention for its efficiency. Typical proposals for lattice-based encryption systems fit public keys and ciphertexts into only about 1KB, and take very little CPU time. This efficiency relies on using systems built from algebraic number fields. The most common choices are cyclotomic number fields, such as the smallest field containing the complex number ζ=exp(πi/512), a 512th root of −1.

Lattice-based cryptosystems are frequently claimed to have proofs of security assuming the "worst-case" hardness of certain lattice problems. For a cyclotomic lattice system, the problem is to find a short nonzero element of I, given a nonzero ideal I of the smallest ring containing ζ. The conjecture that this problem is hard is frequently claimed to be well studied. However, the problem has in fact suffered dramatic security losses.

This talk will introduce the audience to recent advances in algorithms to solve this problem, with an emphasis on techniques to exploit multiplicative structure in general, automorphisms in the Galois case, extra subfields when they exist, and additional features of cyclotomic fields. The audience is not assumed to be familiar with algebraic number theory.

2021.01.15: Daniel J. Bernstein, "Valuations and S-units", invited talk, NIST 3rd Round Seminar Series. [vertical slides] [horizontal slides] [video] Talk abstract:

This talk reviews a standard infinite-dimensional number-theoretic lattice that simultaneously shows how large numbers are and how they factor. The ability to decode this lattice in some surprisingly large cases plays a critical role in a new wave of attacks against ideal-lattice problems. This talk will focus on defining the lattice, with many examples to illustrate.

This is an introductory talk aimed at a broad audience. Prerequisites: mathematics education up to and including a course in undergraduate abstract algebra (commutative rings and fields).