4 releases
0.2.0 | Apr 1, 2021 |
---|---|
0.1.2 | Sep 11, 2019 |
0.1.1 | Sep 5, 2018 |
0.1.0 | Sep 5, 2018 |
#1741 in Algorithms
9MB
166K
SLoC
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.
It also contains some example programs that try to find covering codes (mainly StGen codes) that have desirable properties.
Usage
- Get Rust and Cargo set up. You may need the nightly version (as of September 2018).
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.
Dependencies
~10–21MB
~296K SLoC