A New Algorithm for Solving Ring-LPN with a Reducible Polynomial

2014/09/01 by Qian Guo, Guo, Qian, Thomas Johansson +3
Computer Science · Engineering · #Coding theory and cryptography #graph theory and CDMA systems #Cryptographic Implementations and Security

paper · pdf · doi:10.48550/arxiv.1409.0472

Abstract

The LPN (Learning Parity with Noise) 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 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 about 2⁷0 bit operations.

Citations

• Noise-tolerant learning, the parity problem, and the statistical query model

Related

• Provably weak instances of Ring-LWE
• Solving the LPN problem in cube-root time
• Ring-LWE Cryptography for the Number Theorist
• Cryptanalysis of PLWE based on zero-trace quadratic roots
• Lossy Cryptography from Code-Based Assumptions