The security of code-based cryptography relies primarily on the hardness of generic decoding with linear codes. The best generic decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoders (ISD). A while ago, a generic decoding algorithm which does not belong to this family was proposed: statistical decoding. It is a randomized algorithm that requires the computation of a large set of parity-checks of moderate weight, and uses some kind of majority voting on these equations to recover the error. This algorithm was long forgotten because even the best variants of it performed poorly when compared to the simplest ISD algorithm. We revisit this old algorithm by using parity-check equations in a more general way. Here the parity-checks are used to get LPN samples with a secret which is part of the error and the LPN noise is related to the weight of the parity-checks we produce. The corresponding LPN problem is then solved by standard Fourier techniques. By properly choosing the method of producing these low weight equations and the size of the LPN problem, we are able to outperform in this way significantly information set decodings at code rates smaller than $0.3$. It gives for the first time after $60$ years, a better decoding algorithm for a significant range which does not belong to the ISD family.
翻译:基于代码的加密安全主要取决于对线性代码进行非常规解码的严格性。 最佳的通用解码算法就是由于Prange而改进的旧算法: 它们以信息解码器( ISD) (ISD) 的名称而为人所知。 不久前, 提出了一个不属于这个家族的通用解码算法: 统计解码。 这是一个随机化算法, 需要计算大量中度对等检查的重量, 并使用某些多数票来恢复这些方程式的错误。 这一算法被长期遗忘, 因为与最简单的ISD 算法相比, 其最优的变种都表现不好。 我们通过使用对等检查方程式来重新审视这个旧算法。 这里的对等式算法用来获取不属于这个家族的 LPN 样本, 其部分是错误, 而 LPN 噪音则与我们所制作的对等度检查的重量有关。 相应的 LPN 问题随后由标准的 Fourier 技术来解决 。 通过正确选择这些低重重的方程式, 和LPN 3 的大小, 我们无法在60 年的算算算法中, 。