Ideal-SVP

Cyclotomic Ideal-SVP is a lattice problem of foundational importance in the security analysis of lattice-based cryptography. There are "very strong hardness guarantees" stating, roughly, that Ring-LWE is secure if cyclotomic Ideal-SVP with polynomial approximation factor is secure. This was the explicit source of high-profile proposals of Ring-LWE/Module-LWE cryptosystems for standardization and deployment.

Saying that one lattice problem is secure if another lattice problem is secure begs the question of whether the problems are in fact secure. These proposals assume that the best lattice attacks take exponential time, specifically time 2^((0.292...+o(1)) beta) where beta is the required "BKZ block size". (This is the time without quantum computers; otherwise 0.292 is replaced by something smaller.)

If Ring-LWE is in fact breakable much more efficiently than this, then it will not be surprising for the public development of a break to follow a path that includes a break of Ideal-SVP. After all, the "very strong hardness guarantees" say that a Ring-LWE attack implies an Ideal-SVP attack. Similar comments apply to Module-LWE.

S-unit attacks

Traditional attacks against lattice problems, including cyclotomic Ideal-SVP, rely solely on the additive structure of lattices to search for short lattice vectors. S-unit attacks exploit the multiplicative structure of the lattices used in these specific lattice problems. This multiplicative structure is reflected in an auxiliary lattice, a standard number-theoretic lattice called the "S-unit lattice".

Unit attacks are an early special case of S-unit attacks. A quantum polynomial-time unit attack broke the "h^+=1" cyclotomic case of Gentry's original STOC 2009 system for fully homomorphic encryption using ideal lattices. Various "barriers" were claimed for this line of attacks and then broken by subsequent developments, illustrating the importance of looking more closely at this area.

Short-S-unit attacks

The attack against Gentry's system starts by very efficiently writing down a short basis for the unit lattice. The introduction of S-unit attacks in 2016 included asking whether one could find "a short enough basis for the S-unit lattice". A massive new research project on S-unit attacks began in early 2020, centered around the idea that one can quickly find short S-units beyond short units.

This project led to a variety of advances in S-unit attacks against cyclotomic Ideal-SVP. Highlights were presented in a talk "S-unit attacks" (60 minutes, 2021.08.20), and extensive further resources are now available regarding five different aspects of the talk:

• The special analytic features of S-unit lattices. First paper released by the project: "Non-randomness of S-unit lattices" (58 pages, 2021.10.23). This paper shows that standard heuristics in the literature on lattice-based cryptography, when applied to S-unit lattices as in 2019 Pellet-Mary–Hanrot–Stehlé (presented more concisely in 2021 Ducas–Pellet-Mary), are highly inaccurate. Trusting the standard heuristics led the 2019 paper to see only a small corner of the power of S-unit attacks.

• Experimental evidence regarding the performance of S-unit attacks. First software package released by the project: filtered-s-unit (6883 lines, 2021.12.17). This software collects data regarding the tradeoffs between database size and output length in filtered-S-unit attacks for a range of cyclotomic fields. Filtered-S-unit attacks are S-unit attacks that obtain S-units by filtering small ring elements, as in traditional class-group computations and the number-field sieve for integer factorization.

• Conjecturally subexponential scalability for S-unit attacks against polynomial-approximation-factor cyclotomic Ideal-SVP. The filtered-s-unit documentation reviews the rationale for the standard subexponential-time conjectures for previous S-unit algorithms, quantifies this rationale for filtered-S-unit attacks against cyclotomic fields, and, from this perspective, evaluates the quantitative phase transitions visible in the data collected by filtered-s-unit.

• Faster norm computations for smooth-degree cyclotomic fields. Second paper released by the project: "Fast norm computation in smooth-degree Abelian number fields" (59 pages, 2022.07.31); accompanying software packages: abelianfields (3725 lines, 2022.07.11) and cyclo2power (487 lines, 2022.05.30); also overview material. Computing norms of many small ring elements is one of the central bottlenecks in traditional class-group computations and in filtered-S-unit attacks; this paper shows that algorithms for smooth-degree cyclotomic fields are much faster than the best techniques known for general number fields.

• Faster p-unit constructions for the case of cyclotomics. The talk's detailed construction of the full p-unit group via Jacobi sums and square roots (p-units are a useful intermediate step between units and S-units) was, after the talk, also described in two papers from other people: "A short basis of the Stickelberger ideal of a cyclotomic field" (20 pages, 2021.09.27) and "Log-S-unit lattices using explicit Stickelberger generators to solve Approx Ideal-SVP" (54 pages, 2021.10.13, updated 2021.11.29). Beware that those papers take limited smoothness bounds (following the standard lattice heuristics) and omit filtering; the approximation factors reached in those papers are a step backwards from the concrete examples given in the talk and from the conjecture of polynomial approximation factors in subexponential time.

Structurally, S-unit attacks are applicable to general Ideal-SVP, not just cyclotomic Ideal-SVP. However, many speedups in S-unit attacks rely on automorphisms, subfields, and specific structures of cyclotomic fields.