Security Proofs and Reductions in Lattice Schemes

A security proof for a cryptographic scheme is a formal mathematical argument showing that breaking the scheme implies solving an underlying hard problem. The proof does not guarantee absolute security; it shows that any efficient adversary against the scheme can be converted into an efficient solver for the hard problem. If the hard problem is intractable, the scheme is secure.

Regev's seminal 2005 proof shows that a polynomial-time algorithm solving decisional LWE can be used to solve worst-case GapSVP (Gap Shortest Vector Problem) on n-dimensional lattices. The reduction is quantum: it uses a quantum sampling procedure to convert an LWE solver into a lattice solver. This means LWE is at least as hard as worst-case lattice problems under quantum computation.

Regev's reduction is not tight: the polynomial factors in the reduction mean that the security level guaranteed by the proof is somewhat weaker than the best known attacks suggest. For practical parameter selection, cryptographers use the concrete security provided by the best known attacks (via lattice estimator) rather than the theoretical reduction bound, since the reduction is conservative.

An LWE-based encryption scheme is proven IND-CPA (indistinguishable under chosen plaintext attack) via a hybrid argument. The proof shows that an IND-CPA distinguisher implies an LWE distinguisher. In the first hybrid, the real ciphertext is replaced with a uniform random string; indistinguishability follows from the LWE assumption. This gives a clean security proof for basic lattice encryption.

IND-CPA security is not sufficient for key encapsulation mechanisms used in TLS: they need IND-CCA2 (chosen ciphertext attack) security. The Fujisaki-Okamoto (FO) transform converts any IND-CPA scheme into an IND-CCA2 KEM in the Random Oracle Model (ROM). ML-KEM applies a variant of the FO transform to the underlying Module-LWE encryption, providing the CCA2 security required for real-world deployment.

The Random Oracle Model (ROM) models hash functions as truly random functions. Many security proofs, including those for the FO transform, require the ROM. In practice, hash functions like SHA-3 are not truly random oracles, so ROM proofs do not guarantee security in the standard model. However, ROM proofs are widely accepted in the cryptographic community as strong evidence of security.

A standard model proof makes no idealization about hash functions and is strictly stronger than a ROM proof. Most practical lattice schemes use ROM proofs because standard model CCA2 proofs for lattice-based KEMs are much more complex and yield worse concrete parameters. NIST accepted ROM-based proofs for ML-KEM, viewing them as sufficient for the security levels targeted.

The ML-KEM security proof proceeds in two steps. First, the underlying Module-LWE encryption is shown to be IND-CPA secure under the M-LWE assumption. Second, the Fujisaki-Okamoto transform (specifically the T and U transforms used in Kyber) upgrades this to IND-CCA2 in the quantum ROM (QROM), which handles adversaries that query the random oracle in superposition.

The lattice estimator by Albrecht, Player, and Scott is the standard tool for computing concrete security of LWE-based schemes. It models the cost of the best known lattice attacks (BKZ with sieving or enumeration) and outputs estimated bit security for given parameters (n, q, sigma). The tool is regularly updated as new algorithms and hardware cost models are published.

The Block Korkine-Zolotarev (BKZ) algorithm is the best practical lattice reduction algorithm. BKZ with block size beta finds short vectors with complexity roughly 2^{0.292*beta} gate operations using the best sieving algorithms. For ML-KEM-768, the estimated classical security is about 180 bits and quantum security about 164 bits, well above the 192-bit target.

Asymptotic security proofs show that a scheme is secure for sufficiently large parameters, but do not specify what "sufficiently large" means in practice. Concrete security analysis fills this gap by estimating the actual cost of the best attack for the chosen parameters. Post-quantum standardization relies heavily on concrete security analysis, with parameters chosen to resist attacks on anticipated quantum hardware over a 30-year horizon.

Which transform is used to upgrade IND-CPA lattice encryption to IND-CCA2 security in ML-KEM?

Lattice scheme security proofs reduce the scheme's security to the hardness of LWE or SVP. Regev's reduction guarantees that LWE is at least as hard as worst-case lattice problems. The Fujisaki-Okamoto transform upgrades IND-CPA to IND-CCA2 in the ROM. Concrete security is evaluated with the lattice estimator using BKZ complexity models. Reduction tightness gaps mean practical parameters rely on attack cost estimates rather than reduction bounds alone.