信息集攻击算法的改进

作     者：李梦东 蔡坤锦 邵玉芳 LI Meng-Dong;CAI Kun-Jin;SHAO Yu-Fang

作者机构：北京电子科技学院北京100070 西安电子科技大学西安710071 

基　　金：北京市支持中央高校共建项目一青年英才计划 中央高校基本科研业务费专项资金资助课题 

出 版 物：《密码学报》 (Journal of Cryptologic Research)

年 卷 期：2016年第3卷第5期

页      码：-页

摘      要：在信息论和密码学中,线性码有各种不同的应用.其中随机线随性码有很多困难问题,如伴随式译码问题是已知的NP-hard问题.随机线性码的译码问题是基于纠错码的密码方案所依赖的计算困难问题.它是抵抗量子计算机攻击的候选方案之一.关于这一问题的求解方法目前仍然是指数时间的,但最优译码算法的运行时间也在不断改善,其中信息集译码的Stern算法^([4]),其运行时间复杂度为■(2^(0.05563n)).最近,May等人设计了MMT算法^([6]),使得运行时间复杂度降为■(2^(0.05363n)),空间复杂度降为■(2^(0.021n)).May等人提出伴随式译码的子问题,即子矩阵匹配问题,这使得我们可以寻找更加有效的方法来解决进而解决伴随式译码问题.针对May提出的MMT算法及其优化的参数,我们提出一种改进MMT算法,主要的改进有两方面,首先,分解索引的枚举范围,然后是索引集合的大小;主要的思路依然是集中在列表的生成方式上,得到的时间复杂度为■(2^(0.05310n)),空间复杂度为■(2^(0.0144n)).改进后的MMT算法不但在时间上有所提高,而且在空间上占有一定的优势.近期May等提出了Nearest Neighbor算法,它的在时间复杂度上占有绝对的优势,以后的工作可以分析Nearest Neighbor算法,对MMT算法进一步提高.

主 题 词：信息集攻击 复杂度 表示技术 密码分析 基于纠错码的方案 

学科分类：0808[工学-自动化类] 0809[工学-计算机类] 08[工学] 0839[0839] 0714[0714] 0835[0835] 0701[理学-数学类] 0811[工学-水利类] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.13868/j.cnki.jcr.000147

馆 藏 号：203208604...