IEEE Transactions on Information Theory · 2015 · 21 citations · 12 references
ComputingComputer ScienceMathematicsAlgorithmsAuthenticationCryptographyCryptographic AlgorithmsCryptographic ProtocolsMutual AuthenticationApplications In Cryptography
The learning parity with noise (LPN) problem has recently proved to be of great importance in cryptology. A special and very useful case is the Ring-LPN problem, which typically provides improved efficiency in the constructed cryptographic primitive. We present a new algorithm for solving the Ring-LPN problem in the case when the polynomial used is reducible. It greatly outperforms the previous algorithms for solving this problem. Using the algorithm, we can break the Lapin authentication protocol for the proposed instance using a reducible polynomial, in ~2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">71</sup> bit operations.
12
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2005 · 2.2K citations
Efficient noise-tolerant learning from statistical queries
Michael Kearns · Journal of the ACM · 1998 · 712 citations · Full text