The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

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

På svenska

Author

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.

Publishing year

2015

Language

English

Pages

6204-6212

Publication/Series

IEEE Transactions on Information Theory

Volume

61

Issue

11

Document type

Journal article

Publisher

IEEE - Institute of Electrical and Electronics Engineers Inc.

Topic

  • Other Electrical Engineering, Electronic Engineering, Information Engineering

Status

Published

Research group

  • Crypto and Security

ISBN/ISSN/Other

  • ISSN: 0018-9448