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

Actual Complexity of Modular Knapsack Vector Problem and Practical Security of a Lattice Based Public Key Cryptosystem

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

Knapsack problem is usually utilized to design asymmetric cryptographic algorithms, and it is a research hotspot of public key cryptography, the modular knapsack vector problem is the problem of solving several knapsack problems simultaneously in the sense of modulo operation. In this paper, this problem is converted into finding short vectors in some lattices. We show that the modular knapsack vector problem can be practically solved for small dimensions by using the LLL or BKZ algorithm or their combination, and discuss the security standard of the modular knapsack vector problem and show the relationship between the Hermite factor and the dimensions of the lattices which are derived from the modular knapsack vector problem. Our experiments coincide with the theoretical analysis and can solve the target vector for small dimensions, namely the modular knapsack vector problem can be solved for small dimensions. On the other hand, due to the failure to find target vectors in lattices with large dimensions, we can see that the computation capability of lattice basis reduction algorithms is restricted by the dimensions of lattices. When the dimension increases, the running time of lattice basis reduction algorithm increases exponentially and the probability of success for finding out the target vector decreases. Furthermore, based on the experiments, we verified and showed that the choices of parameters of algorithms also affect the experimental results. For a lattice-knapsack mixed public key cryptosystem proposed at the CANS 2011 conference, when converted into modular knapsack vector problem, we can practically break the cryptosystem under ciphertext-only attack for one of its recommended parameters m =100.