New Definition of Density on Knapsack Cryptosystems
New Definition of Density on Knapsack Cryptosystems
复制标题
DOI：
10.1007/978-3-540-68164-9_11
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
N. Kunihiro
中科院分区：
文献类型：
--
作者：
N. Kunihiro
许多背包密码系统被提出，但由于其低密度，几乎所有的方案都容易受到格攻击。为了防止晶格攻击，Chor和Rivest提出了一种低重量背包方案，该方案使密度高于临界密度。在Asiacrypt2005中，Nguyen和Stern引入了伪密度，并证明了如果伪密度足够低（即使通常密度不够低），背包方案可以通过单次调用SVP/CVP oracle被打破。然而，通常密度和伪密度不足以单独测量对晶格攻击的抵抗力。在本文中，我们首先引入了一个新的密度概念，它自然地统一了前面的两个密度。其次，我们推导出密度的条件，使背包方案易受晶格攻击。我们得到了一个密度的临界界，它只取决于信息长度与其汉明权值的比值。更进一步，我们证明了如果d < 0.8677，背包方案可以被格攻击解决。其次，我们证明了当Hamming权值减小时，临界界趋于1，这意味着很难构造一个有密度参数支持的低重量背包方案。
Many knapsack cryptosystems have been proposed but almost all the schemes are vulnerable to lattice attack because of its low density. To prevent the lattice attack, Chor and Rivest proposed a low weight knapsack scheme, which made the density higher than critical density. In Asiacrypt2005, Nguyen and Stern introduced pseudo-density and proved that if the pseudo-density is low enough (even if the usual density is not low enough), the knapsack scheme can be broken by a single call of SVP/CVP oracle. However, the usual density and the pseudo-density are not sufficient to measure the resistance to the lattice attack individually. In this paper, we first introduce a new notion of densityD, which naturally unifies the previous two densities. Next, we derive conditions for our density so that a knapsack scheme is vulnerable to lattice attack. We obtain a critical bound of density which depends only on the ratio of the message length and its Hamming weight. Furthermore, we show that ifD< 0.8677, the knapsack scheme is solved by lattice attack. Next, we show that the critical bound goes to 1 if the Hamming weight decreases, which means that it is quite difficult to construct a low weight knapsack scheme which is supported by an argument of density.