Lattice-Based Cryptography

The foundational hardness assumption for lattice-based cryptography. Security relies on the difficulty of solving noisy linear equations over finite fields. Given a matrix A and a vector b = As + e, where e is a small error vector, recovering the secret s is computationally infeasible.

• Search LWE: Recover the secret vector s.
• Decision LWE: Distinguish (A, b) from a uniformly random pair.
• Forms the direct security basis for BFV and CKKS schemes.

An algebraic variant of LWE that operates over polynomial rings, dramatically improving efficiency. Instead of unstructured matrices, operations occur in R_q = Z_q[x]/(x^n + 1).

• Reduces key size from O(n²) to O(n).
• Enables SIMD packing via the Chinese Remainder Theorem.
• Underpins practically all efficient homomorphic encryption schemes deployed today.

The dual problem to LWE, providing collision-resistant hash functions and signature schemes. The problem asks to find a non-zero, short vector x such that Ax = 0 mod q.

• Average-case hardness: Solving random instances is as hard as worst-case lattice problems.
• Used in digital signatures and zero-knowledge proofs.
• Provides the security backbone for lattice-based commitment schemes.

A unique cryptographic property proving that breaking a random lattice instance is at least as hard as solving the hardest instances of underlying lattice problems like GapSVP or SIVP.

• Regev's Theorem (2005): Established the quantum reduction from worst-case lattice problems to average-case LWE.
• Peikert's Theorem (2009): Provided a classical reduction, removing the quantum requirement.
• Guarantees that no secret "weak" keys exist in the cryptosystem.

Lattice-based schemes are leading candidates in the NIST Post-Quantum Cryptography Standardization process because no known quantum algorithm efficiently solves lattice problems.

• Shor's Algorithm breaks RSA and ECC but is useless against lattices.
• CRYSTALS-Kyber (ML-KEM) and CRYSTALS-Dilithium are NIST-selected lattice standards.
• Provides long-term confidentiality for data that must remain secure for decades.

A structured subclass of lattices corresponding to ideals in polynomial rings. They enable compact key representation and fast multiplication using Number Theoretic Transform (NTT).

• Efficiency: NTT reduces polynomial multiplication from O(n²) to O(n log n).
• Trade-off: Additional algebraic structure introduces potential attack surface, though no practical breaks are known.
• The foundation for RLWE and Module-LWE variants.

A lattice-based hardness assumption used primarily for constructing digital signatures and collision-resistant hash functions, rather than encryption.

• Problem: Given a random matrix A, find a non-zero, short integer vector x such that A*x = 0 mod q.
• Average-Case Hardness: Security is based on the difficulty of finding short vectors in random lattices.
• Relation to FHE: While FHE relies more on LWE, SIS provides the security foundation for the digital signature schemes used to authenticate data in distributed cryptographic protocols.

A special class of lattices possessing an algebraic structure corresponding to ideals in polynomial rings. This structure enables the compact representation of bases using a single vector.

• Efficiency: Reduces key size from O(n^2) to O(n) by exploiting the rotational symmetry of the lattice.
• Underlying Ring: Typically defined over cyclotomic rings like Z[x]/(x^n + 1) where n is a power of two.
• Trade-off: The extra algebraic structure that enables efficiency also introduces potential attack vectors, though no practical vulnerabilities have been found that break the standard security assumptions.

The foundational computational problem generalized by RLWE. It asks an adversary to recover a secret vector s from samples of the form (a, <a,s> + e).

• Noise: The error e is drawn from a discrete Gaussian distribution and is critical to security; without it, the problem reduces to trivial Gaussian elimination.
• Regev's Reduction: Oded Regev proved that solving LWE on average is at least as hard as solving the GapSVP (Shortest Vector Problem) in the worst case using a quantum reduction.
• Usage: Serves as the security basis for the TFHE and CKKS schemes.

A lattice construction based on polynomial rings with small coefficients, forming the basis of the NTRUEncrypt public-key cryptosystem and its homomorphic derivatives.

• Structure: Uses a mix of large and small modulus rings with sparse, ternary polynomials.
• Performance: Historically offers faster encryption and decryption speeds than standard RLWE-based schemes due to simpler sampling procedures.
• Standardization: The NTRU-based Falcon signature scheme and NTRU KEM are finalists in the NIST Post-Quantum Cryptography standardization process.

The cryptographic technique for drawing random noise vectors from a Gaussian distribution over a lattice. The quality of this sampling directly impacts the security margin of the scheme.

• Purpose: Generates the error term e in LWE samples to hide the secret.
• Security Requirement: The distribution must be statistically close to a true continuous Gaussian rounded to the lattice; biased sampling can leak the secret.
• Side-Channel Risk: Constant-time implementations of Gaussian samplers are notoriously difficult to build, making them a prime target for timing attacks in hardware deployments.