Lattice Reduction Bkz Sieving Attacks

Short answer: Lattice-based post-quantum schemes are judged by how expensive the best known attacks are, and those attacks rest on lattice reduction algorithms such as BKZ and on sieving. Different cost models for these algorithms give different security estimates for the same scheme. Research papers from 2011 and 2019 show that improved implementations and models can shift those estimates, which is why the cryptanalysis of lattices is tracked as closely as the schemes themselves. This is classical cryptanalysis, not a quantum attack.

BKZ in security estimates

A paper presented at Asiacrypt 2011 describes BKZ, from Schnorr and Euchner, as the best lattice reduction algorithm known in practice for high dimension, and says all security estimates of lattice cryptosystems at that time were based on an old implementation of it. Progress in lattice enumeration suggested that implementation was no longer optimal, with unclear impact on estimates. The authors ran extensive experiments with BKZ 2.0, a state-of-the-art implementation that includes improvements such as Gama-Nguyen-Regev pruning. They propose a simulation algorithm to model BKZ in high dimension with block size at least 50, predicting output quality and running time approximately. As an example, they report that their simulation suggests the smallest NTRUSign parameter set, claimed to give at least 93-bit security against key-recovery lattice attacks, actually offers at most 65-bit security. This is the authors' own estimate for that older scheme.

Cost models disagree

A paper on estimating the security of lattice schemes considers all LWE- and NTRU-based encryption, key encapsulation and signature schemes proposed in the NIST post-quantum process. It notes that of 69 complete and proper submissions, 23 are based on LWE or NTRU. The authors say techniques for solving these problems are well known but there are different views on the asymptotic cost of BKZ, which combines shortest-vector (SVP) calls in blocks of a projected lattice. A cost model combines the cost of solving SVP in a given dimension and the number of SVP calls BKZ needs. The paper says these differences can lead to the same scheme being given several security levels depending on the model, and that a major source of divergence is whether sieving or enumeration is used to instantiate the SVP oracle. The authors estimate primal and dual attack costs for every LWE-based scheme under every model proposed in a submission, and primal attack costs for the NTRU-based schemes.

Sieving in practice

The General Sieve Kernel (G6K), described in a 2019 paper, is an abstract stateful machine supporting many lattice reduction strategies based on sieving. The authors give formulations of earlier sieving strategies and propose new ones, a light variant of BKZ, and techniques to reduce the sieving work needed such as recycling vectors between sieves and on-the-fly lifting. They provide an open-source, optimised implementation. They report solving previously unsolved instances of the Darmstadt SVP challenges (151, 153, 155) and an LWE challenge, with the SVP-151 solution found 400 times faster than the time reported for the previous record SVP-150. For exact SVP they observe a performance crossover with an enumeration implementation at dimension 70.

What this does not tell you

These papers do not say the NIST-selected lattice schemes are broken, and none of them describes a quantum attack. They show that estimates depend on the implementation and the cost model, so parameter choices rely on continued analysis. The security figures quoted for older schemes should not be applied to current standards.

FAQ

What is BKZ?

A lattice reduction algorithm that combines shortest-vector calls on blocks of a lattice, central to attacks on LWE and NTRU schemes.

What is sieving?

A family of algorithms for the shortest-vector problem, an alternative to enumeration as the SVP step in BKZ.

Why do security estimates differ?

Different cost models for BKZ, including sieving or enumeration as the SVP step, can give one scheme several security levels.

Did these papers break a standard?

No. The 2019 paper solves challenge instances, and the 2011 paper revises estimates for an older scheme.

Are these quantum attacks?

No. They are classical algorithms.