Crypto 2017 - LPN Decoded
Unknown (noreply@blogger.com)
Crypto 2017 kicked off this morning in Santa Barbara. After a quick eclipse-watching break, the lattice track ended with the presentation of LPN Decoded by Andre Esser, Robert Kübler, and Alexander May. Learning Parity with Noise (LPN) is used as the underlying hardness problem in many cryptographic protocols. It is equivalent to decoding random linear codes, and thus offers strong security guarantees. The authors of this paper propose a memory-efficient algorithm to the LPN problem. They also p