混合约简:一种可调整的覆盖码约简算法  

Hybrid Reduction:An Adjustable Covering Code Reduction

作　　者：耿致远 胡红钢[1] GENG Zhi-Yuan;HU Hong-Gang(School of Cyber Science and Technology,University of Science and Technology of China,Hefei 230027,China)

机构地区：[1]中国科学技术大学网络空间安全学院,合肥230027

出　　处：《密码学报（中英文）》2024年第4期820-829,共10页Journal of Cryptologic Research

基　　金：国家自然科学基金(61972370)。

摘　　要：带噪声奇偶学习问题(learning parity with noise,LPN)是密码学中的一类重要困难问题,它可以视作随机线性码译码问题的一般形式,是抗量子假设中的有力候选.在求解LPN问题前,通常需要执行约简操作,将待求实例转化为秘密长度更短的实例.本文提出了一种新的混合约简算法Hybrid,它将经典的丢弃约简算法和覆盖码约简算法相结合,在约简过程中丢弃与码字距离超过给定界限的LPN样本,而非将所有样本直接近似到码字.这种新的约简方法可以到达权衡样本复杂度和时间复杂度的目的.从算法层面讲,丢弃约简与覆盖码约简可以视作混合约简的特例.最后,使用池化高斯算法求解经过混合约简后的LPN样本,给出了其完整的理论复杂度.数值估计的结果表明混合约简可以进一步缩减良好池化高斯算法(Well-Pooled Gauss)的样本复杂度,但需要以时间开销上升为代价.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.

关 键 词：带噪声奇偶学习 丢弃约简算法 覆盖码约简算法 池化高斯算法 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]