• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Progress in Cryptology - AFRICACRYPT 2008 >New Definition of Density on Knapsack Cryptosystems
【24h】

New Definition of Density on Knapsack Cryptosystems

机译：背包密码系统密度的新定义

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 density D, 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 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 quite difficult to construct a low weight knapsack scheme which is supported by an argument of density.
机译：已经提出了许多背包密码系统，但是几乎所有的方案由于其低密度而容易受到晶格攻击。为了防止晶格攻击，Chor和Rivest提出了一种轻量级背包方案，该方案使密度高于临界密度。在Asiacrypt2005中，Nguyen和Stern引入了伪密度，并证明了如果伪密度足够低（即使通常的密度不够低），也可以通过一次调用SVP / CVP oracle来破坏背包方案。但是，通常的密度和伪密度不足以单独测量对晶格侵蚀的抵抗力。在本文中，我们首先介绍了密度D的新概念，它自然地统一了前两个密度。接下来，我们得出密度的条件，以便背包方案容易受到晶格攻击。我们获得了密度的临界范围，该密度范围仅取决于消息长度与其汉明权重的比率。此外，我们表明，如果D <0.8677，则背包方案可通过晶格攻击解决。接下来，我们表明，如果汉明权重减小，则临界界限将变为1，这意味着构造密度参数支持的低权重背包方案非常困难。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号