S-unit attacks

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 four different aspects of the talk:

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.


Version: This is version 2021.12.17 of the "Intro" web page.