Computational cryptography › Public-key encryption and key exchange › Post-quantum public-key › Codes and noisy equations
Hardness assumption

LPN

In plain words

Solve a system of yes/no equations where some of the answers are deliberately wrong.

The idea: Take a secret string of bits and write down lots of random equations about it, like "bit 2 + bit 5 + bit 9 = 1", where 1 + 1 wraps around to 0. If every answer were right, school algebra would find the secret in a blink. LPN flips a small fraction of the answers at random, and that noise is believed to make the secret impossible to recover: the answers look like coin flips.

That's what makes it useful: a short secret expands into a long string that looks random. And because the expansion is linear, two parties holding related seeds get related outputs, which is how secure-computation tools (PCGs) mass-produce the random material they need.

With very little noise it even gives public-key encryption: hide a bit inside the sum of a few public equations. The key holder can subtract the clean answer, and with so little noise the leftover error is usually zero.

Why it matters: It needs nothing but additions of bits, so it's extremely cheap: it powers the fastest tools for computing together on private data.

Equations with a few wrong answers
secret bits:????????b1b2b3b6=0b1b2b6b7=0b8=0b1b2b5b6=1b1b2b3b5b6b8=1flippedb4b6b7=0b6b7b8=1
Each row says which secret bits to add up (with 1 + 1 = 0), followed by the answer. Most answers are right, but a few are flipped at random (red here, unmarked in reality). Without the flips, the secret would fall out of a few rows of school algebra. With them, nobody knows which rows to trust, and every row you combine also combines the errors.

The details

On the map: learning parity with noise. Standard noise: OT extension, PCGs. Low noise (~1/√n) gives public-key encryption (Alekhnovich), i.e. KE

Learning parity with noise: solve a system of random linear equations over bits where each equation is wrong with some probability. It is the binary cousin of LWE[1].

With standard (constant) noise it powers efficient secure-computation tools, OT extension variants and pseudorandom correlation generators[2], but it isn't known to give public-key encryption. With low noise (about 1/√n) it does (Alekhnovich 2003)[3], which would earn it a KE tag. It is also used in lightweight authentication (the HB protocols)[4].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

References

  1. Avrim Blum, Adam Kalai and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM, 2003. doi:10.1145/792538.792543
  2. Elette Boyle, Geoffroy Couteau, Niv Gilboa et al. Efficient Pseudorandom Correlation Generators: Silent OT Extension and More. Advances in Cryptology – CRYPTO 2019. doi:10.1007/978-3-030-26954-8_16
  3. M. Alekhnovich. More on average case vs approximation complexity. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. doi:10.1109/sfcs.2003.1238204
  4. Nicholas J. Hopper and Manuel Blum. Secure Human Identification Protocols. Advances in Cryptology — ASIACRYPT 2001. doi:10.1007/3-540-45682-1_4