A New Algorithm for Solving Ring-LPN With a Reducible Polynomial
Författare
Summary, in English
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 ~271 bit operations.
Avdelning/ar
Publiceringsår
2015
Språk
Engelska
Sidor
6204-6212
Publikation/Tidskrift/Serie
IEEE Transactions on Information Theory
Volym
61
Issue
11
Dokumenttyp
Artikel i tidskrift
Förlag
IEEE - Institute of Electrical and Electronics Engineers Inc.
Ämne
- Other Electrical Engineering, Electronic Engineering, Information Engineering
Status
Published
Forskningsgrupp
- Crypto and Security
ISBN/ISSN/Övrigt
- ISSN: 0018-9448