Paper 2016/288

Optimization of LPN Solving Algorithms

Sonia Bogos and Serge Vaudenay

Abstract

In this article we focus on constructing an algorithm that automatizes the generation of LPN solving algorithms from the considered parameters. When searching for an algorithm to solve an LPN instance, we make use of the existing techniques and optimize their use. We formalize an LPN algorithm as a path in a graph G and our algorithm is searching for the optimal paths in this graph. The results bring improvements over the existing work by a factor from 2^8 to 2^{10}, i.e. we improve the results of the covering code from ASIACRYPT'14. Furthermore, we propose concrete practical codes and a method to find good codes.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
soniamihaela bogos @ epfl ch
History
2016-03-17: received
Short URL
https://ia.cr/2016/288
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/288,
      author = {Sonia Bogos and Serge Vaudenay},
      title = {Optimization of LPN Solving Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2016/288},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/288}},
      url = {https://eprint.iacr.org/2016/288}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.