Specifications and improvements of LPN solving algorithms

摘要

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.