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

DOI10.1109/TIT.2015.2475738MaRDI QIDQ2977130zbMATH OpenFDO

Authors Qian Guo, Thomas Johansson, Carl Löndahl

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.0472

Mathematics Subject Classification ID

Cryptography (94A60)

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^70 bit operations.

Cited in

(8)

• A new birthday-type algorithm for attacking the fresh re-keying countermeasure
• A new class of the smallest FSSP partial solutions for 1D rings of length \(n=2^k-1\)
• Efficient pseudorandom correlation generators from ring-LPN
• Solving LPN using covering codes
• On solving LPN using BKW and variants, Implementation and analysis
• Correlated pseudorandomness from the hardness of quasi-abelian decoding
• Key recovery from side-channel power analysis attacks on non-SIMD HQC decryption
• Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices

This page was built for publication: A New Algorithm for Solving Ring-LPN With a Reducible Polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977130)