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

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