模背包向量问题的实际复杂度与基于格密码体制的实际安全性

• 作者: 彭力强 胡磊 许军 黄章杰
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: 模背包向量问题 格基约化算法 唯密文攻击 实际安全性
• 年，卷（期）: 2014,（3）
• 页码范围: 225-234
• 页数: 10页
• 分类号: TP309.7
• 字数: 5283字
• 语种: 中文
• DOI: 10.13868/j.cnki.jcr.000021

摘要

背包问题常被用来构造公钥密码算法,它是公钥密码学中的一个研究热点,模背包向量问题是同时求解若干个在模意义下的背包问题.本文将模背包向量问题转化为格中短向量的求解.我们利用LLL、BKZ等格基约化算法或它们的联合方法求解目标向量,实际地解决了维数较小时的模背包向量问题,讨论了关于模背包向量问题的安全标准,并展示了由模背包向量问题引出的格的Hermite因子随维数的变化关系.我们的实验结果,一方面验证了我们的理论分析,成功地在格维数较小时求解出了目标向量,即模背包向量问题在维数较小时可解;另一方面,由目标向量在维数较大的格中未被找到可以看出,格基约化算法在求解格中短向量问题的计算能力受维数的限制.随着格维数的变大,格基约化算法的运行时间指数级增长并且找到目标向量的概率减小.另外,我们通过具体的实验数据,验证并说明了格基约化算法中参数选取对实验结果产生的影响.对于CANS 2011会议上提出的一个基于格与背包问题混合设计的公钥加密方案,我们将针对该方案的唯密文攻击转化为模背包向量问题的求解,从而在唯密文攻击下实际地攻破了该方案的一个推荐参数m=100.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡磊	中国科学院信息工程研究所信息安全国家重点实验室	36	145	7.0	10.0
5	彭力强	中国科学院信息工程研究所信息安全国家重点实验室	2	3	1.0	1.0
9	黄章杰	中国科学院信息工程研究所信息安全国家重点实验室	1	3	1.0	1.0