Skip to content

CONCEPT Cited by 1 source

Lattice-based cryptography

Definition

Lattice-based cryptography builds cryptographic primitives — encryption, signatures, key exchange, homomorphic encryption, zero-knowledge proofs — on the conjectured hardness of problems over point lattices in high-dimensional space. The canonical hard problems are Learning With Errors (LWE), Ring-LWE (RLWE), Module-LWE (MLWE), and Shortest Vector Problem (SVP).

The defining feature: lattice problems are conjectured hard for quantum computers as well as classical ones — making lattice-based constructions the dominant substrate for post-quantum cryptography.

Why lattices

Lattice-based crypto has three structural advantages that explain its production dominance among PQC candidates:

  1. Post-quantum resilience — no known quantum algorithm gives a superpolynomial speed-up against LWE / SVP, unlike Shor's algorithm against RSA / ECC. NIST's standardised PQC primitives ( ML-KEM, ML-DSA) are both lattice-based.
  2. Homomorphic-friendly — RLWE-based fully homomorphic encryption (FHE) schemes (BGV / BFV / CKKS) allow computation on ciphertext. Pairing-based crypto, the prior dominant FHE substrate, is broken by quantum computers.
  3. Key-aggregation algebraically natural — ciphertexts and keys in lattice schemes can be combined linearly, enabling secure-aggregation schemes where the sum of ciphertexts decrypts under the sum of keys. The 2026-05-27 Google secure-aggregation protocol is built on this property.

Hardness foundations

Problem Statement Used in
LWE Given (A, As + e), find s. e is small noise. KEMs, signatures, FHE
Ring-LWE LWE over polynomial rings — more compact, similar hardness ML-KEM, ML-DSA, BFV, BGV
SVP Find the shortest non-zero vector in a lattice Underlying hard problem behind LWE reductions
CVP Closest-vector problem Underlying hardness assumption

The security parameter is the lattice dimension — increasing it trades off ciphertext / signature size against attack difficulty.

Production lattice-based primitives on the wiki

Primitive Type Wiki page
ML-KEM (FIPS 203) KEM (key encapsulation) systems/ml-kem
ML-DSA (FIPS 204) Signature systems/ml-dsa-signature
HQC KEM (alternate, code-based) systems/hqc (not lattice but PQC sibling)
Open Quantum Safe library Lattice + alternates wrapper systems/liboqs
Google secure-aggregation (2026-05-27) One-shot key-aggregating encryption This source

Use in the 2026 Google secure-aggregation protocol

Per the 2026-05-27 post:

"At its heart, our cryptographic solution is powered by an innovative lattice-based protocol that allows clients to encrypt their data in a way that the resulting ciphertexts can be aggregated while aggregating the underlying messages as well as encryption keys."

The lattice substrate gives this protocol three production-load-bearing properties:

  • Linearity over both ciphertexts and keys — needed for the "sum of encrypted = encrypted sum, decryptable only with sum of keys" property that prevents the server from ever holding a per-client decryption key.
  • Single-message submission — clients commit to their ciphertext + key share in one shot, without rounds of interaction. Critical for mobile-fleet deployment where devices are not always online (see patterns/one-shot-secure-aggregation).
  • Post-quantum resilience by construction — the production fleet of Android devices generating analytics today is the same fleet that will be alive when CRQCs become realistic; PQ-secure-by-default avoids a later forced migration.

The full protocol spec is in the linked ACM paper, which is referenced but not detailed in the blog post.

Trade-offs vs other PQC families

Family Pros Cons
Lattice (LWE, RLWE) Versatile (KEM, sig, FHE, ZKP); fast; PQ; key-aggregation natural Larger keys / signatures than ECC
Code-based (HQC, BIKE) Long-studied hardness Very large public keys
Hash-based (SLH-DSA / SPHINCS+) Conservative security; simple Large signatures, only signatures
Isogeny Smaller keys SIKE was broken; remaining schemes less mature
Multivariate Compact signatures Many broken; limited deployment

Lattice's combination of versatility + speed + maturity is why every NIST-standardised general-purpose PQC primitive uses it.

Caveats

  • Conjectured hardness, not proven. All cryptographic hardness assumptions are conjectures; LWE / SVP have withstood decades of cryptanalysis but a polynomial-time algorithm is not ruled out.
  • Parameter selection is fragile. Concrete security depends on precise lattice-dimension / noise-distribution / modulus choices; errors here have historically caused breaks in published schemes.
  • Side-channel attacks on lattice implementations are a real concern — constant-time decoders, BLISS-style rejection sampling, and floating-point hazards have all caused implementation-level breaks. Hardening matters.
  • Public-key sizes are larger than ECC equivalents (kilobytes vs hundreds of bytes), which matters for bandwidth-constrained deployments — though not for the mobile-fleet federated-analytics use case.

Seen in

Last updated · 542 distilled / 1,571 read