论文部分内容阅读
有损陷门函数（lossy trapdoor function,简记为LTDF）是由 Peikert和Waters在会议STOC 2008上正式定义的。有损陷门函数中包含了两族不可区分的函数。一类即是常见的单射函数。在这类函数中,利用陷门就可以有效的求逆;另一类即是有损的函数。有损函数的值域范围比定义域的范围要小,且有损函数不可以求逆。同时,Peikert和Waters给出了一个有损陷门函数的一般化的定义:All-But-One（ABO）有损陷门函数。在ABO有损陷门函数中,每一个函数都有一个额外的输入,这个输入被称之为分支。在这些分支中只有一个有损分支,其他的都是单射分支。Peikert和Waters证明了利用有损陷门函数、ABO有损陷门函数和一个一次强签名方案可以构造一个选择密文攻击安全的公钥加密方案。变色龙ABO有损陷门函数是ABO有损陷门函数的一种扩展形式,在会议PKC 2011上,Junzuo Lai等人利用变色龙ABO有损陷门函数构造了高效的选择密文攻击安全的公钥加密方案。All-But-Many（ABM）有损陷门函数是有损陷门函数和ABO有损陷门函数的一种扩展形式。它是Hofheinz在会议Eurocrypt 2012上正式给出定义的。ABM有损陷门函数是带有标签的有损陷门函数。标签分为单射标签和有损标签,其中利用单射标签可以得到单射的函数,而用有损标签则可以得到有损的函数。ABM有损陷门函数是一个比有损陷门函数更为强大的密码学原语。Hofheinz证明了利用ABM有损陷门函数可以构造具有选择打开安全性的公钥加密算法,而这是有损陷门函数和ABO有损陷门函数做不到的。自从有损陷门函数定义正式提出以来,已有了广泛地应用。例如利用有损陷门函数可以构造抗碰撞的哈希函数,选择明文攻击和选择密文攻击安全的公钥加密方案,以及不经意传输方案等。特别的,Kakvi和Kiltz在会议ASIACRYPT 2012上提出了一个基于有损陷门函数的全域哈希签名方案,并证明了这类的签名方案有一个紧的安全性规约,而在此之前,全域哈希签名方案的安全性证明是不紧的;Kiltz、O’Neill和Smith在会议CRYPTO 2010上给出了一个新的RSA-OAEP加密方案的安全性证明。他们利用RSA算法的有损性,证明了在标准模型下,RSA-OAEP加密方案是选择明文攻击安全的,而在此之前,RSA-OAEP加密方案的安全性是在预言机模型下证明的。目前,已有的有损陷门函数的构造一般基于确定性Diffie-Hellman（DDH）假设、带误差的学习问题（LWE）假设、合数剩余假设、二次剩余假设和Φ-hiding假设等。ABM有损陷门函数的构造基于配对、合数剩余假设和格。在本论文中,我们主要研究了基于改进的RSA算法的有损陷门函数的构造、变色龙All-But-One有损陷门函数和身份基有损陷门函数的构造、All-But-Many有损陷门函数的构造以及它们的应用,其主要研究成果如下:1.我们构造了一个基于改进的RSA算法的有损陷门函数,我们的构造是依赖于二次剩余假设。与传统的RSA有损陷门函数相比较,我们的方案不受指数e大小的限制（传统的RSA陷门函数只有在指数e<N1/4时才是有损的）。我们还利用了改进的RSA有损陷门函数构造了 一个全域哈希数字签名方案,并且证明了该方案有一个紧致的UF-CMA安全性规约。最后,我们还构造了一个盲签名方案,并且证明了该方案有一个紧致的L-OMF安全性规约。2.我们首先构造了一个通用的变色龙ABO有损陷门函数,我们方案的基本构件是ABO有损陷门函数和变色龙哈希函数,同时我们根据通用的构造,给出了基于改进的RSA加密算法的具体的构造。其次,我们将变色龙ABO有损陷门函数中的分支和身份基密码学中的身份id相对应,利用了一个基于配对的变色龙ABO有损陷门函数构造了一个身份基有损陷门函数。我们构造的基本构件是Boyen和Waters的基于DBDH假设的有损陷门函数。最后,我们利用身份基有损陷门函数构造了一个基于DDH假设的身份基加密方案,并证明该方案是选择性密文不可区分选择身份选择明文攻击安全的。同时我们利用身份基有损陷门函数构造了身份基签名方案,并给出了一个紧致的安全性规约。3.我们构造了一个基于判定性RSA子群假设的ABM有损陷门函数。我们的方案中基本构件是Groth的基于判定性RSA假设的CPA安全的公钥加密方案和变色龙哈希函数。ABM有损陷门函数有两个安全性:计算不可区分性和模糊性。在证明计算不可区分性时,我们利用Groth的CPA安全的公钥加密方案的密文不可区分性来完成证明。对于模糊性,我们构造了一个在选择明文攻击下不可伪造安全的签名方案,利用签名的不可伪造性来证明敌手输出一个有损标签的概率是可忽略的。其次,我们给出了 ABM有损陷门函数的一个通用的构造方法,其基本构件是CPA安全的同构公钥加密方案和变色龙哈希函数,我们利用同构公钥加密方案密文的不可区分性完成了计算不可区分性和模糊性的证明。同时,我们给出了一个基于DCR假设的具体的ABM有损陷门函数。