New Conditions for Secure Knapsack Schemes against Lattice Attack
New Conditions for Secure Knapsack Schemes against Lattice Attack
复制标题
DOI：
10.1587/transfun.e93.a.1058
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
N. Kunihiro
中科院分区：
文献类型：
--
作者：
N. Kunihiro
背包密码体制已被提出，但几乎所有的方案都是脆弱的格攻击，因为它们的低密度。为了防止格攻击，Chor和Rivest提出了一种低重量背包方案，使密度高于临界密度。在Asiacrypt 2005中，Nguyen和Stern引入了伪密度，并证明了如果伪密度足够低（即使通常的密度不够低），则背包方案可以通过对SVP/CVP oracle的单个调用来打破。然而，通常的密度和伪密度不足以单独测量对晶格攻击的抵抗力。在本文中，我们首先引入密度D的新概念，它自然地统一了前两个密度。接下来，我们推导出我们的密度条件，使背包计划是安全的格攻击。我们得到了一个临界密度界，它只依赖于消息长度和它的汉明重量的比率。当D < 0.8677时，背包方案可通过格攻击得到解.接下来，我们表明，临界界去1，如果汉明重量减少，这意味着它是（几乎）不可能构建一个低重量的背包计划，这是支持的一个参数的密度。
Many knapsack cryptosystems have been proposed but almost all the schemes are vulnerable to lattice attack because of their 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 to 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 the new notion of density D, which naturally unifies the previous two density. Next, we derive conditions for our density so that a knapsack scheme is secure against lattice attack. We obtain a critical bound of density which depends only on the rate of the message length and its Hamming weight. Furthermore, we show that if D < 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 (almost) impossible to construct a low weight knapsack scheme which is supported by an argument of density.