Learning With Errors

Solving noisy systems of linear equations modulo a number. Can be reduced to a Short Vector Problem

LWE Problem

• For positive integers $n\in \mathbb{Z}$ and $q\ge 2$
• For secret vector $s\in {\mathbb{Z}}_q^n$
• For Probability Distribution $\mathcal{X}$ on $\mathbb{Z}$ Define distribution $A_{s,\mathcal{X}}$ as follows:
• Choose a vector $a$ from ${\mathbb{Z}}_q^n$ uniformly at random and sample a noise term $e$ from $\mathcal{X}$
• Output the pair $(a,[⟨a,s⟩+e{]}_q)$ where:
  • $⟨,⟩$ is the Inner Product
  • $q$ is the reduction Modulo

Intuition

• Messages are repesented as vectors or polynomials
• Noise is added during encryption to hide plaintext
• Difficulty in solving encrypted form depends on complexity of lattice problem