因子分解假设的复合模广义迪菲赫尔曼问题的伪随机提取

作者：梅其祥; 李宝; 路献辉

来源：计算机学报, 2011, (07): 1308-1313.

• 随机提取
• Blum-Blum-Shub生成器
• 因子分解假设
• 广义迪菲赫尔曼问题 randomness-extraction
• Blum-Blum-Shub generator
• factoring assumption
• Generalized Diffie-Hellman problem

研究怎样在因子分解假设下有效地提取复合模数上的广义菲赫尔曼问题的伪随机比特串.证明了Blum-Blum-Shub生成器是一个合适的广义菲赫尔曼问题提取器.利用Naor-Reingold-Rosen伪随机函数中的技巧证明:在因子分解假设下,对于任意的{1,2,…,n}上的真子集合A,即使公开了gi∏∈Aai,BBSr(g∏ni=1ai)仍然是伪随机的(其中,g是平方剩余群QRN上的生成元,N为Blum整数).利用该结论,在因子分解假设下,可以得到不可区分意义安全的公钥加密和密钥交换协议.

• 单位
  中国科学院研究生院; 信息安全国家重点实验室; 广东海洋大学