Open AccessSpecifications and improvements of LPN solving algorithms
Author(s) -
Jiao Lin
Publication year - 2020
Publication title -
iet information security
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.308
H-Index - 34
eISSN - 1751-8717
pISSN - 1751-8709
DOI - 10.1049/iet-ifs.2018.5448
Subject(s) - computer science , algorithm , cryptography , nist , reduction (mathematics) , binary number , gaussian , theoretical computer science , mathematics , arithmetic , physics , geometry , quantum mechanics , natural language processing
The hardness of LPN problems serves as security source of many primitives in lightweight and post‐quantum cryptography, which enjoy extreme simplicity and efficiency for various applications. Accordingly there are several LPN solving algorithms proposed over past decade, and received quite a lot of attention recently. In this paper, we propose a new LPN solving algorithm using covering codes in the existing algorithmic framework with a new data structure of numerical value instead of vector quantity for convenience in table look‐up, integrate the optimized procedures, and further presenting four main improvements. Firstly, we apply the technique of binary tree sum in Gaussian elimination and new BKW iterations. Secondly, we propose a global BKW collision optimization with tweakable reduction length, which is proved optimized. Thirdly, we extend the covering codes scope in service for lager bias and smaller data requirement with a bias estimation strategy. Finally, we propose a detailed parameter selection principle for given LPN instances. The best known classic results are given for the (512/532/592,1/8)‐instances suggested in cryptographic schemes. Besides, we evaluate the performance on low‐noise LPN and (k,1/4)‐LPN instances, and further correct the lower length bounds of LPN instances with various bias for security levels of NIST's Post‐Quantum Call.