The NP-hard problem of decoding random linear codes is crucial to both coding theory and cryptography. In particular, this problem underpins the security of many code based post-quantum cryptographic schemes. The state-of-art algorithms for solving this problem are the information syndrome decoding algorithm and its advanced variants. In this work, we consider syndrome decoding in the multiple instances setting. Two strategies are applied for different scenarios. The first strategy is to solve all instances with the aid of the precomputation technique. We adjust the current framework and distinguish the offline phase and online phase to reduce the amortized complexity. Further, we discuss the impact on the concrete security of some post-quantum schemes. The second strategy is to solve one out of many instances. Adapting the analysis for some earlier algorithm, we discuss the effectiveness of using advanced variants and confirm a related folklore conjecture.
翻译:NP 随机线性代码解码的难题对于编码理论和密码学都至关重要。 特别是, 这个问题是许多基于代码的分子后加密方法安全的基础。 解决这一问题的最先进的算法是信息综合解码算法及其先进的变体。 在这项工作中, 我们考虑在多种情况下设置综合解码。 两种策略适用于不同的情景。 第一个策略是借助预先计算技术解决所有案例。 我们调整当前框架, 区分离线阶段和在线阶段以减少分解复杂性。 此外, 我们讨论某些分子后加密方法对具体安全的影响。 第二个策略是解决许多实例中的一种。 调整分析以适应某些早期的算法, 我们讨论使用先进变种的有效性, 并证实相关的民俗猜想 。