基于DL类假设Lossy Trapdoor函数的构造及其优化

论文摘要

1976年Diffie和Hellman在[15]中提出Trapdoor函数的概念,并且历史上认为单向Trapdoor函数是密码学中最基本的工具,可以用于构造很多密码学中有用的工具。比如构造伪随机生成器[23]、零知识证明[23]、以及各种密码协议特别是语义安全的加密方案[24]。但是我们知道语义安全并不能满足很多应用的要求,更普遍的观点认为抵抗可以截取修改信启、并能观察解密等的敌手的加密方案才是安全的,也就是抵抗主动的选择密文安全（CCA）[24]的加密方案。由单向Trapdoor函数构造语义安全的加密方案是直接的,但是不能直接而简单的用于构造CCA安全的加密力案,现有的构造方案都是基于非交互的零知识证明。同时不是所有的困难性假设都可以用来构造单向Trapdoor函数,现在只有基于分解和离散对数的构造,比如没有基于格问题的构造方法。Chris Peikert和Brent Waters08年在[31]中提出的Lossy trapdoor函数（LTF）是一个公钥密码学中新的基本的概念。该类函数不仅可以基于广泛的困难问题来构造,特别是基于格问题的构造,还可以用于构造经典的Trapdoor函数,Lossy trapdoor函数的应用广泛,是很多基本的密码学对象的基础比如Collision Resistant Hash Function[24]、Oblivious Transfer协议[24]、确定性的加密方案和CCA2安全的加密方案[24]等。Lossy trapdoor函数是一个公开的函数f,有两种计算不可区分的模式,并且给定函数的描述没有敌手能有效的计算区分是属于那个模式。在第一种模式中,函数是一个单射函数,并且给定陷门的话可以计算函数的逆；在第二种模式中,函数的象集明显的小于元象集合,因此也称作此模式是Lossy函数。Chris Peikert和Brent Waters [31]给出了基于判定的Diffie-Hellmani假设（DDH）,和格上的Learn with Erro （LWE）假设为基础给出两种构造的实例。但是作者所给出的两种构造都具有较高的复杂度,两种构造的函数指标（公钥）大小都为（?）（A2）。Freeman等在[29]中给出了更多的构造Lossy Trapdoor函数的方法,其中有基于二次剩余、Composite Residuosity假设和kDLDH假设[7]分别做的构造。在k-linear构造方法中,作者定义了一种在指数上是矩阵的运算,并且证明在判定k-Linear假设之下敌手区分不了秩为k的和满秩的矩阵,并基于此做的构造。但是该构造的复杂度很高,如果原象是λbit的,就需要（?）（λ2）的陷门和（?）（A2）的函数指标。Xavier Boyen等[8]对PW机制的基于DDH的方案做出了优化,使得函数指标复杂度大大降低,从（?）（λ2）降低到（?）（λ）。Xavier Boyen等分别使用的是公共字符串（CRS）和（?） Pairing做了优化。由于DDH假设在双线性群上是不成立的,他们将构造的安全性基于了双线性的判定Diffie-Hellman （DBDH）假设。所以该方案只能在双线性群上使用。类似于Cramer和Shoup[11][12]将基于DDH设计的IND-CCA安全的加密方案推广到用一般的HPS设计ND-CCA安全的加密方案,Brett和Rafail [19]（?）（?）PW机制的基于DDH的构造LTD推广到用一般的HSHPS设计LTDs,并得到任意的HSHPS构造Ⅰ（?）TDs的方法。以上的基于离散对数相关困难问题的构造都具有较高的复杂性,本文主要考虑如何构造更加有效的LTF,使得具有更加小的函数指标和陷门,并且可以有效调节Lossiness大小。本文主要作出以下3个贡献。1、我们给出了一般的基于DLDH假设设计的Lossy trapdoor函数的PW机制的构造,并利用Pairing群给出优化密钥大小的构造。虽然Freeman等在[29]中已经给出了指数矩阵的构造方法,但是他们的方案不能优化,复杂度还是很高。我们给出的方案能够使用Pairing（?）等函数指标的复杂度从（?）（λ2）降低到（?）（λ）。我们主要在第三章中予以详细说明。2、在第四章我们推广Hash Proof System的概念,在证明系统中增加了Bilinear映射,得至（?）Bilinear Hash Proof System的概念。将上而缩短函数指标的方法推广,我们给出了由Bilinear Hash Proof System到LTF更加有效的一般性构造。函数指标的大小大约为（?）（λ）.缺点是该构造只在双线性群上可行。3、其次在第五章中,我们给出基于两种新的DL类假设给出新的构造LTF的方案,并且我们的方案的函数指标和陷门大小均为（?）（λ）。首先给出基于DDH-like假设[10]构造出（n,n-2dlog2q）的LTF.考虑指数上是扩域上的元素而不是Zq中的元素,同时扩域中的元素可以表示成矩阵的形式。首先我们将基本的ElGmal加密方案作出修改,将困难性基于DDH-like（?）假设。加密方案指数上是Fqn集合中属于Fqd的元素（其中d|n,Fqd为Fqn的子域）同时我们将n长bits的消息映射到Fqn中的元素并进行加密。并且分别将对于单位矩阵和零矩阵的加密做为Injective和（?）Lossy函数的指标,上面加密方案的语义安全就保证了该函数两个模式指标的不可区分性。在我们的构造中,lossy（?）勺大小约为n-2dlog2q.并且明显的该设计中的lossy的大小很容易通过调节所选取子域的大小（d的大小）来调节lossy的大小。之后我们指出由于DDH-like假设在双线性的群上是不成立的,所以我们将DDH-like假设推广到新的DLDH-like（?）段设,说明该假设是一个比DDH-like和DLDH都较弱的假设。同时在该假设下也构造出新自（?）（n,n-3dlog2q）LTF类似于对标准ElGmal加密方案的修改,我们对于基于DLDH（?）假设的加密方案作出修改。同样将对于单位矩阵和零矩阵的加密做为Injective和Lossy函数的指标。可见基于DLDH-like（?）假设的构造在一般的群上也是成立的。本节对于LTF的构造都比之前的构造都更加有效,只需要（?）（λ）的陷门和（?）（λ）的函数指标。并且据我们所知之前并没有基于离散对数相关问题的更加有效的构造。最后我们对比了几种基于DL类假设的构造的有效性和适用性。

论文目录

• 中文摘要
• ABSTRACT
• 符号说明
• 第一章 预备知识
• §1.1 Lossy trapdoor函数
• §1.2 Pairing的定义
• §1.3 复杂性假设
• §1.4 Smooth Hash Proof System
• 第二章 PW机制的构造及优化
• §2.1 基于DDH的构造
• §2.2 缩短指标
• §2.2.1 CRS模型下的优化
• §2.2.2 标准模型下的优化
• §2.3 基于HSHPS的一般化构造
• 第三章 基于DLDH的新构造及优化
• §3.1 基于DLDH的新构造
• §3.2 缩短指标
• §3.2.1 CRS模型下的优化
• §3.2.2 标准模型下的优化
• §3.3 一般化基于k-DLDH的构造
• 第四章 基于Bilinear-HSHPS更有效的一般化构造
• 第五章 基于DDH-like和DLDH-like的新构造
• §5.1 基于DDH-like的构造
• §5.2 基于DLDH-like的构造
• §5.2.1 DLDH-like假设
• §5.2.2 基于DLDH-like的构造
• 第六章 总结
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录
• 学位论文评阅及答辩情况表