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

摘要

研究怎样在因子分解假设下有效地提取复合模数上的广义菲赫尔曼问题的伪随机比特串.证明了Blum-Blum-Shub生成器是一个合适的广义菲赫尔曼问题提取器.利用Naor-Reingold-Rosen伪随机函数中的技巧证明:在因子分解假设下,对于任意的{1,2,…,n}上的真子集合A,即使公开了giпai∈A,BBSr(gii=1nпai)仍然是伪随机的(其中,g是平方剩余群QRN上的生成元,N为Blum整数).利用该结论,在因子分解假设下,可以得到不可区分意义安全的公钥加密和密钥交换协议.%This paper studies how to efficiently extract the pseudo-random bits string from the Generalized Diffie-Hellman (GDH) problem over composite modulus under the factoring assumption. It is proven that Blum-Blum-Shub(BBS) generator is a suitable extractor for GDH problem over composite modulus. In particular, adapting the technique used in the proof of Naor-Rein-gold-Rosen pseudorandom function, it is proven that BBSr(Ⅱn gt=1 ai ) is pseudo-random even if Ⅱ gi∈A ai is given for any proper subset A of {1,2,···