类背包DH问题的比特安全性研究

作者：李伟; 吕克伟

来源：信息网络安全, 2013, (10): 121-123.

DOI：10.3969/j.issn.1671-1122.2013.10.038

• 单向函数
• 比特安全
• 背包DH问题
• 双线性对 one-way function
• bit security
• knapsack DH problem
• bilinear pairings

类背包DH问题是椭圆曲线背包Diffie-Hellman问题的变形。该问题具有与椭圆曲线背包问题在计算上是等价的困难性。针对这个问题的单向性,文章证明其明文的最小有意义比特是hardcore谓词,并给出问题单向性到hardcore谓词可预测性的一个有效归约,进而证明了该问题的每一个比特都是同样困难的。

• 单位
  中国科学院信息工程研究所; 信息安全国家重点实验室