Advanced

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

Guo, Qian LU ; Johansson, Thomas LU and Löndahl, Carl (2015) In IEEE Transactions on Information Theory 61(11). p.6204-6212
Abstract
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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
IEEE Transactions on Information Theory
volume
61
issue
11
pages
6204 - 6212
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • wos:000363256500030
  • scopus:84959432221
ISSN
0018-9448
DOI
10.1109/TIT.2015.2475738
language
English
LU publication?
yes
id
650e6434-b553-4bc1-ab0e-33bb2ee09f82 (old id 8147690)
date added to LUP
2015-11-04 11:10:34
date last changed
2017-01-01 06:21:12
@article{650e6434-b553-4bc1-ab0e-33bb2ee09f82,
  abstract     = {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.},
  author       = {Guo, Qian and Johansson, Thomas and Löndahl, Carl},
  issn         = {0018-9448},
  language     = {eng},
  number       = {11},
  pages        = {6204--6212},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  series       = {IEEE Transactions on Information Theory},
  title        = {A New Algorithm for Solving Ring-LPN With a Reducible Polynomial},
  url          = {http://dx.doi.org/10.1109/TIT.2015.2475738},
  volume       = {61},
  year         = {2015},
}