Learning with errors

As explained in Real-World Cryptography

Learning with errors is a computational problem of recovering a secret vector from linear equations whose results are perturbed by small random errors, typically modulo a large number.

Learning with errors (LWE) hides a secret vector inside many linear equations. Each equation combines a random vector with the secret, then adds a small random error, usually modulo a large number. Without the errors, Gaussian elimination can recover the secret efficiently; with larger numbers and more secret coordinates, recovery becomes hard. section 14.3.2

From solvable equations to noisy equations

The clean equations 5s₀ + 2s₁ = 27 and 2s₀ = 6 reveal s₀ and s₁ through Gaussian elimination. Changing their results to 28 and 5 introduces noise, making the secret harder to determine. In vector form, random aᵢ and secret s produce aᵢs + eᵢ, where eᵢ is small random error. For example, s = (3, 6), a₀ = (5, 2), and a₁ = (2, 0) produce the original equations through dot products. section 14.3.2

The construction is commonly organized as follows:

• Choose a secret vector whose coordinates are considered modulo a large number. section 14.3.2
• Generate random vectors and publish their noisy dot products with the secret. section 14.3.2
• Rewrite the equations as t = As + e, where A contains the random vectors and e contains the errors. section 14.3.3
• Use small errors and private-key coefficients relative to q; this structure supports LWE-based encryption and key exchange such as Kyber. section 14.3.3

Figure 14.9 The learning with errors problem (LWE) is said to be a lattice-based construction due to the existence of a reduction to a lattice problem: the CVP. In other words, if we can find a solution to the CVP, then we can find a solution to the LWE problem.

Relate LWE to a lattice problem through a reduction to the closest vector problem (CVP). section 14.3.2

How Real-World Cryptography covers it

How deep it goes

Defines noisy linear equations, vectors, dot products, and matrix form, then stops short of formal proofs or implementation detail.

Examples

Uses two noisy two-variable equations, vector dot products, the matrix equation t = As + e, and Kyber key exchange.

What it assumes

Assumes basic linear algebra, while introducing vectors, dot products, modular arithmetic, and matrix notation.

What you can do after

Evaluate/understand why small errors change tractable linear recovery into a cryptographic hardness assumption.

How it connects

Connects Gaussian elimination, dot products, matrices, lattices, CVP, SVP, Kyber, Dilithium, and post-quantum cryptography.

liveBookmanning.com

Read Real-World Cryptography on liveBook Get the book at manning.com

Related concepts

• CRYSTALS-Dilithiumused by · CRYSTALS-Dilithium is a lattice-based digital signature scheme based on the learning with errors problem.
• homomorphic encryptionused by · Homomorphic encryption is encryption that permits specified computations on ciphertexts whose decrypted results correspond to computations on the underlying plaintexts.
• Gaussian eliminationcontrasts with · Gaussian elimination is a procedure that applies elementary row operations to transform a linear system or matrix into an equivalent triangular or row-reduced form.
• noiseused by · Noise is variation, content, or data treated as unwanted, irrelevant, or distinct from the signal, pattern, or structure of interest.
• lattice-based cryptographyused by · Lattice-based cryptography is cryptography whose security constructions or reductions are based on computational problems involving lattices.

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.