[Resource Topic] 2016/288: Optimization of LPN Solving Algorithms

Welcome to the resource topic for 2016/288

Optimization of LPN Solving Algorithms

Authors: Sonia Bogos, Serge Vaudenay


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.

ePrint: https://eprint.iacr.org/2016/288

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .