lpn 0.1.2

Software to study attacks on the Learning Parity with Noise problem

Attacks on Learning Parity with Noise

This software package allows to construct attacks on LPN. The examples/ directory shows many examples of solving algorithms that solve various LPN instances using various (combinations of) reductions and solution-finding algorithms.

Usage

  1. Get Rust and Cargo set up. You may need the nightly version (as of September 2018).
  2. cargo run --release --example bkw

Source material

Thom Wiggers. Solving LPN using Large Covering Codes. Master's Thesis Radboud University, 2018.

See also https://thomwiggers.nl/research/msc-thesis/

References

  • Blum, Kalai and Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Computing, 2000, ACM, 2013.
  • Levieil and Fouque. An improved LPN algorithm. SCN 2006, Springer 2018.
  • Bogos, Tramer and Vaudenay. On solving LPN using BKW and variants – implementation and analysis. Cryptography and Communications, 2016.
  • Bogos and Vaudenay. Optimization of LPN solving algorithms. ASIACRYPT 2015, Springer, 2016.
  • Esser, Kübler and May. LPN Decoded. CRYPTO 2017, Springer, 2017.
  • Samardjiska and Gligoroski. Approaching Maximum Embedding Efficiency on Small Covers Using Staricase-Generator Codes. 2015 IEEE International Symposium on Information Theory, 2015.