密码学报2016，Vol.3Issue(5)：505-515,11.DOI:10.13868/j.cnki.jcr.000147
信息集攻击算法的改进*
An Improved Algorithm of Information Set Decoding
摘要
Abstract
Linear codes have various applications in information theory and in cryptography. Many problems for random linear codes such as the so-called syndrome decoding are known to be NP-hard. Decoding problem of random linear codes is a computing hard problem on which code-based cryptographic schemes are designed. It is one of the candidates for resisting quantum computer attacks. Solutions on the decoding problem are still of exponential complexity but the optimal decoding algorithm’s running time is in a continuous improvement. The complexity of well-known information set decoding algorithm of Stern[4] isO(20.05563n). Recently, MMT algorithm[6] designed by May et al. was presented with running time complexity being reduced toO(20.05363n) and with space complexityO(20.021n). Mayer proposed the syndrome decoding sub-problems, namely sub-matrix matching, which allows us to look for more efficient ways to solve the problem and then solve the syndrome decoding. An improved algorithm that rearranges the lists partition of MMT algorithms and introduces new parameters is proposed, which optimizes the algorithm’s running time complexity to beO(20.05310n), and space complexity to beO(20.0144n). The main improvement is two-fold, it first breaks down the enumerated range of the index, then the size of the index set. The main idea is still focused on the generation of the list. The improved MMT algorithm has improvements both in time and in space. Recently, Nearest Neighbor algorithm was proposed by May, which has an obvious advantage in time complexity. It leaves us to further analyze the Nearest Neighbor algorithm, and to possibly improve the MMT algorithm.关键词
信息集攻击/复杂度/表示技术/密码分析/基于纠错码的方案Key words
information set decoding/complexity/representation technique/cryptanalysis/code-based scheme分类
信息技术与安全科学引用本文复制引用
李梦东,蔡坤锦,邵玉芳..信息集攻击算法的改进*[J].密码学报,2016,3(5):505-515,11.基金项目
北京市支持中央高校共建项目一青年英才计划 （）
中央高校基本科研业务费专项资金资助课题 （）
