A novel improved information set decoding algorithm via nearest neighbor search

Yu Li

doi:10.1186/s42400-025-00469-z

2026-06-11

Yu Li

Li-Ping Wang *

Xiangyu Pan

DOI：10.1186/s42400-025-00469-z

原文链接

查看原文

摘要

En 中文

基于码的密码系统的多数设计基于伴随式解码（SD）问题。针对SD问题的最有效攻击采用信息集解码（ISD）算法。在EUROCRYPT 2023上，Esser和Zweydinger提出了ISD算法的一个重要时空权衡方案。本文中，我们通过结合Esser-Zweydinger算法和最近邻技术提出了改进的ISD算法。随后，我们将改进算法应用于将深度为2的Both-May算法（2017 WCC）的内存复杂度从$$O\big (2^{0.0282n}\big )$$降低至$$O\big (2^{0.0249n}\big )$$，同时保持其时间复杂度恒定为$$O\big (2^{0.0492n}\big )$$，其中n表示二元线性码的长度。此外，我们考虑了改进算法的量子版本，并推导出渐近时间复杂度为$$O\big (2^{0.057866n}\big )$$，该值低于量子BJMM算法在内存消耗不受限制时的$$O\big (2^{0.058660n}\big )$$。最后，我们使用改进算法分别重新评估了HQC、BIKE和Classic McEliece的安全级别。特别地，对于Classic McEliece的参数，本算法估计的安全级别比Esser-Zweydinger的结果低3~6位。

Keyword:

ISD algorithm

SD problem

Code-based cryptography

Post-quantum cryptography

Nearest neighbor