密码学报（中英文）2024，Vol.11Issue(4)：820-829,10.DOI:10.13868/j.cnki.jcr.000710
混合约简:一种可调整的覆盖码约简算法
Hybrid Reduction:An Adjustable Covering Code Reduction
摘要
Abstract
Learning parity with noise(LPN)is an important cryptographic hard problem and is considered as a good problem in the design of post-quantum cryptographic algorithms.It can be viewed as a general problem of the decoding random linear codes.Prior to solving LPN,it is necessary to perform a reduction operation to transform the instance into a shorter secret length instance.This paper proposes a new hybrid reduction algorithm,denoted as Hybrid,that combines the classical techniques of the drop reduction and covering code reduction.During the reduction process,Hybrid drops the LPN samples that have a distance greater than a given threshold from the codeword instead of approximating all the samples to the codeword,to achieve a balance between sample complexity and time complexity.From an algorithmic point of view,the drop reduction and covering code reduction can be considered as special cases of hybrid reduction.Finally,the Well-Pooled Gauss algorithm is used to solve the LPN samples after hybrid reduction,which leads to its complete theoretical complexity.The results of numerical estimation show that the hybrid reduction can further reduce the sample complexity of the Well-Pooled Gauss algorithm,but at the cost of increased time overhead.关键词
带噪声奇偶学习/丢弃约简算法/覆盖码约简算法/池化高斯算法Key words
learning parity with noise/drop reduction/covering code reduction/Pooled-Gauss分类
信息技术与安全科学引用本文复制引用
耿致远,胡红钢..混合约简:一种可调整的覆盖码约简算法[J].密码学报（中英文）,2024,11(4):820-829,10.基金项目
国家自然科学基金(61972370)National Natural Science Foundation of China(61972370) （61972370）
