Lattice-Based Cryptography

Lattices uniquely enable powerful primitives beyond basic encryption and signatures, which are difficult or impossible to build with classical number-theoretic assumptions.

• Fully Homomorphic Encryption (FHE): Lattice schemes like BGV and CKKS allow arbitrary computation on encrypted data, a breakthrough first achieved using ideal lattices.
• Identity-Based Encryption (IBE): Allows a user's public key to be an arbitrary string like an email address, eliminating the need for a traditional public-key directory.
• Attribute-Based Encryption (ABE): Decryption is possible only if the user's secret key possesses attributes satisfying the ciphertext's policy, enabling fine-grained access control on encrypted data.

Lattice problems are believed to be intractable for both classical and quantum computers, making them the primary focus of the NIST Post-Quantum Cryptography Standardization process.

• No Superpolynomial Speedup: The best quantum attacks, based on Grover's algorithm variants, provide only a polynomial speedup for lattice problems, requiring a simple doubling of key sizes to maintain security.
• Standardized Schemes: CRYSTALS-Kyber (KEM) and CRYSTALS-Dilithium (signatures) are NIST-selected lattice-based standards designed to replace RSA and ECDSA.
• Migration Path: Major protocols like TLS 1.3 and Signal are integrating hybrid key exchange, combining classical ECDH with Kyber for defense-in-depth.

A unique theoretical advantage is the worst-case to average-case reduction proven by Regev. Breaking a random instance of LWE is provably as hard as solving the hardest instances of standard lattice problems.

• Uniform Security: Unlike RSA, where a weakness might exist only for specific primes, a break in LWE would imply a break for all lattices.
• Foundation: This reduction connects the average-case cryptographic assumption directly to well-studied computational problems like GapSVP and SIVP.
• Confidence: This provides stronger theoretical confidence in the underlying hardness assumption compared to factoring or discrete log.

Lattice operations are based on linear algebra over finite fields or polynomial rings, making them computationally efficient and highly parallelizable.

• Vectorized Arithmetic: Core operations involve matrix-vector multiplication and polynomial arithmetic, which map efficiently to GPU and hardware accelerator architectures.
• No Large Integer Arithmetic: Unlike RSA's modular exponentiation with 4096-bit integers, lattice schemes use many operations on small (e.g., 16-bit) integers, avoiding complex big-number libraries.
• Constant-Time Implementation: The algebraic structure facilitates implementations resistant to timing side-channel attacks, a critical requirement for real-world cryptographic libraries.

Lattices support efficient trapdoor generation, where a secret 'good' basis of a lattice allows sampling preimages or inverting functions that appear random without the trapdoor.

• Gadget-Based Trapdoors: Techniques like the MP12 trapdoor allow generating a statistically random public matrix A along with a secret trapdoor R with small entries.
• Gaussian Sampling: The trapdoor enables sampling short vectors from a discrete Gaussian distribution satisfying Ax = y, a core operation in lattice-based signatures and identity-based encryption.
• Applications: Enables the construction of secure digital signatures (e.g., GPV framework) and hierarchical identity-based encryption systems.

The foundational computational problem underpinning most efficient lattice-based schemes. RLWE operates over polynomial rings, making it significantly more compact and faster than standard LWE.

• Structure: Works in the ring R_q = Z_q[x]/(x^n + 1) where n is a power of 2
• Hardness: Reduces to worst-case problems on ideal lattices
• Efficiency: Key sizes are quasi-linear O(n) rather than quadratic O(n²)
• Applications: Forms the basis for CRYSTALS-Kyber (NIST PQC standard) and CRYSTALS-Dilithium
• Advantage over LWE: Uses polynomial multiplication which maps to O(n log n) via NTT, enabling practical implementations

A lattice-based hardness assumption used primarily for constructing digital signatures and collision-resistant hash functions. The problem asks to find a non-zero short vector x such that Ax = 0 mod q.

• Average-case to worst-case reduction: Proven by Ajtai in 1996, establishing the first lattice-based cryptographic foundation
• Parameters: Matrix A ∈ Z_q^{n×m} where m > n, solution vector x must have small norm
• Signature schemes: Underpins CRYSTALS-Dilithium and Falcon (both NIST standards)
• Key property: Finding any short solution is hard; verifying a given solution is trivial
• Contrast with LWE: SIS is an inhomogeneous problem focused on collision resistance rather than encryption

Introduced by Regev in 2005, LWE is the central hardness assumption for lattice-based public-key encryption and key encapsulation mechanisms. It asks to recover a secret vector s given noisy inner products.

• Problem: Given (A, b = As + e mod q), recover s where e is a small error vector
• Noise distribution: Typically a discrete Gaussian or centered binomial distribution
• Quantum reduction: Proven to be at least as hard as worst-case lattice problems even against quantum adversaries
• Standard LWE drawback: Key sizes are O(n²), making it impractical without optimization
• Evolution: RLWE and MLWE (Module-LWE) were developed to address the efficiency limitations while preserving security guarantees

The oldest practical lattice-based public-key cryptosystem, patented in 1996 and now in the public domain. NTRU operates over the polynomial ring Z[x]/(x^N - 1) with small coefficients.

• Mechanism: Encryption multiplies message by a random polynomial and adds noise; decryption uses a trapdoor short vector
• NIST variant: NTRU-HRSS and NTRUEncrypt merged into the NTRU submission for PQC standardization
• Performance: Extremely fast encryption/decryption compared to RSA at equivalent security levels
• Maturity: Over 25 years of cryptanalysis without fundamental breaks
• Current status: Selected as a NIST PQC finalist, though Kyber was chosen as the primary KEM standard

Cryptographic constructions that embed a secret 'trapdoor' into a lattice basis, enabling efficient inversion of functions that appear random without the trapdoor knowledge.

• GPV Framework: Gentry, Peikert, and Vaikuntanathan (2008) showed how to construct preimage sampleable trapdoor functions from lattices
• Mechanism: A public key is a 'bad' basis (hard to solve SVP), while the private key is a 'good' basis with short, nearly orthogonal vectors
• Gaussian sampling: The trapdoor enables sampling short vectors from a discrete Gaussian distribution satisfying specific linear constraints
• Applications: Identity-based encryption, attribute-based encryption, and hierarchical IBE
• Micciancio-Peikert improvement (2012): Reduced trapdoor size from O(n²) to O(n log q), making constructions practical

Defensive techniques to prevent leakage of lattice-based private keys through timing, power analysis, or electromagnetic emissions during polynomial arithmetic operations.

• Constant-time NTT: Number Theoretic Transform must execute in uniform cycles regardless of secret coefficients to prevent timing attacks
• Masking: Secret-sharing sensitive variables across multiple shares so that power consumption reveals no single share
• Shuffling: Randomizing the order of independent operations to decorrelate power traces from secret data
• Critical operations: Gaussian sampling and polynomial multiplication are primary leakage vectors
• NIST requirements: All PQC candidates must demonstrate side-channel countermeasures in their reference implementations
• Real-world attack: 2022 research demonstrated electromagnetic side-channel recovery of a Kyber-512 key in under 2 minutes without countermeasures