论文标题
综合征解码符合多个实例
Syndrome decoding meets multiple instances
论文作者
论文摘要
解码随机线性代码的NP硬性问题对于编码理论和密码学都至关重要。特别是，此问题为许多基于代码的量子后加密方案的安全性。解决此问题的最新算法是信息综合征解码算法及其高级变体。在这项工作中，我们考虑在多个实例设置中解码综合征。针对不同的情况采用了两种策略。第一种策略是借助预约技术解决所有实例。我们调整当前框架并区分离线阶段和在线阶段，以降低摊销的复杂性。此外，我们讨论了对某些量子后方案的具体安全性的影响。第二种策略是在许多实例中解决一个。为了调整一些早期算法的分析，我们讨论了使用高级变体的有效性并确认相关的民间猜想。
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.
