信息集攻击算法的改进*??

• 作者: 李梦东 蔡坤锦 邵玉芳
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: 信息集攻击 复杂度 表示技术 密码分析 基于纠错码的方案
• 年，卷（期）: 2016,（5）
• 页码范围: 505-515
• 页数: 11页
• 分类号: TP309.7
• 字数: 7251字
• 语种: 中文
• DOI: 10.13868/j.cnki.jcr.000147

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李梦东		21	104	5.0	9.0
3	蔡坤锦		4	8	1.0	2.0
6	邵玉芳		4	7	1.0	2.0