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

Pseudo-Randomness Extraction for Generalized Diffie-Hellman Problem over Composite Modulus Under Factoring Assumption

作　　者：梅其祥[1,2] 李宝[1] 路献辉[1] 

机构地区：[1]中国科学院研究生院信息安全国家重点实验室,北京100049 [2]广东海洋大学信息学院,广东湛江524088

出　　处：《计算机学报》2011年第7期1308-1313,共6页Chinese Journal of Computers

基　　金：国家自然科学基金(60862001;61070171);国家"九七三"重点基础研究发展规划项目基金(2007CB311201);中国博士后基金(20090460565)资助~~

摘　　要：研究怎样在因子分解假设下有效地提取复合模数上的广义菲赫尔曼问题的伪随机比特串.证明了Blum-Blum-Shub生成器是一个合适的广义菲赫尔曼问题提取器.利用Naor-Reingold-Rosen伪随机函数中的技巧证明:在因子分解假设下,对于任意的{1,2,…,n}上的真子集合A,即使公开了gi∏∈Aai,BBSr(g∏ni=1ai)仍然是伪随机的(其中,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-Reingold-Rosen pseudorandom function,it is proven that BBSr（g ∏ni =1ai） is pseudo-random even if g ∏i ∈Aai is given for any proper subset A of {1,2,…,n},where g is a random element of quadratic residues group QRN,N is a Blum integer.The result can be used to obtain public key encryption and key exchange protocol secure in the sense of indistinguishability under factoring assumption.

关 键 词：随机提取 Blum-Blum-Shub生成器 因子分解假设 广义迪菲赫尔曼问题 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]