混合约简:一种可调整的覆盖码约简算法OA北大核心CSTPCD

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.