基于格的密码方案的研究与设计

论文摘要

公钥密码体制是保障电子商务、电子政务中信息安全的主要手段。基于大整数分解和离散对数困难问题构造公钥密码体制是目前常用的一些密码体制,如RSA加密体制。但这些密码体制中都包含复杂运算,因此效率较低,这也是一直制约公钥密码体制发展的重要因素之一。另外大整数分解和离散对数问题已经被证明不能抵御量子攻击和亚指数攻击。因此必须寻求更加高效、安全的公钥密码体制。1996年Ajtai开创性地提出了基于最差情况下格问题的困难假设构造密码方案的可能性,为构造新型的公钥密码体制提供了一条崭新的思路。一个n维格是Rn上的离散加法子群。基于格构造的密码方案是建立在某个格问题的困难假设基础上的,其中最基本的困难问题是最短向量问题SVP,从目前的研究和实验结果可推测不存在求解近似因子为多项式的格问题的多项式时间算法和多项式时间量子算法。基于格问题构造的密码方案除了能够抵御量子攻击之外,Ajtai等还证明了某类格中一些问题的平均难度等价于格上一类NP问题的难度。因此在这些格问题基础上建立的公钥密码体制,其任意一个实例的安全性与其最难实例的安全性相同。这种优良特性是目前大部分公钥密码体制所不具备的。而且由于格是一种线性结构,其上的运算大多是线性运算,因此可以期望利用格上难题构建的新型公钥密码体制具有更快的运算速度。本文通过对格及相关知识的研究后,详细分析了已有基于格的公钥密码方案,借鉴其中的一些方法和构造思路,构造了新的基于格的密码方案。为构造新的基于格的密码方案,本文首先研究了格的基本知识和性质。对目前在格问题研究中广泛应用的离散高斯分布技术进行深入研究,并将Gentry提出的在格上的离散高斯分布中取点的SampleD算法应用于方案设计中。由Ajtai定义的困难随机格即q模格,是目前基于格的公钥密码体制构造中占主导地位的两种类型的整数格,对此类格及其重要性质的研究奠定了本文方案的构造基础。文中所有方案都是建立在q模格之上的。直接基于格上困难问题构造公钥密码体制是比较困难的,目前基于格构造的公钥密码体制是建立在一些一般情况困难问题之上,这些问题已被证明一般情况下的困难性和最差情况下特定格问题的困难性等价被证明。常见的问题是LWE问题、SIS和ISIS问题。本文研究分析了基于这些问题构造的密码方案,其中基于LWE问题构造的方案包括最初由Regev提出的基于LWE的公钥加密方案, Gnentry等提出的基于身份的加密方案,Peikert等使用Lossy trapdoor functions方法构造的基于LWE的CCA2加密方案；基于SIS和ISIS问题构造的方案主要包括Gentry等定义的原像选取陷门函数以及他们基于原像选取陷门函数构造的数字签名方案。此组原像选取陷门函数也是本文构造基于SIS和ISIS的公钥加密方案的基础。本文研究和构造的主要方案如下：（1）基于LWE的加密方案的研究和构造：Regev首次使用量子算法证明了LWE问题和最差情况GapSVP问题困难性是等同的,同时构造了单比特LWE方案,通过对此方案的研究,了解了基于LWE构造公钥加密方案的思想。本文根据Peikert等提出的多比特LWE方案和Gentry等提出的对偶LWE加密方案构造了多比特对偶LWE加密方案。Gentry在SIS和ISIS的困难假设基础上构造了基于格的原像选取陷门函数,并将此原像陷门函数应用于基于身份加密方案中,负责完成由身份生成对应私钥的操作,在Gentry提出的基于LWE单比特IBE方案基础上,本文构造了多比特IBE方案。最后使用Boneh等提出的将CCA2安全的公钥加密方案建立在CPA安全的基于身份的加密方案基础上的构造方法,以多比特IBE加密方案为基础,构造了基于LWE的CCA2公钥加密方案。上述方案是基于LWE判定问题构造的,Peikert使用非量子算法证明了LWE搜索问题和近似SVP问题的某种变体的困难性是等价的,并以LWE搜索问题为基础,定义了一组陷门函数,进而构造了CCA2安全的加密方案。基于LWE搜索问题构造新的密码方案,也是基于格的密码学研究的一个新方向。（2）基于SIS和ISIS的公钥加密方案的研究和构造：基于SIS和ISIS问题构造的公钥密码方案,主要是以Gentry定义的原像选取陷门函数为基础而构造的公钥密码方案,目前所知的方案是Gnetry基于原像选取陷门函数构造的数字签名方案。但还没有基于原像选取陷门函数构造的公钥加密方案,本文以此原像选取陷门函数为基础,使用Peikert等提出的证据恢复解密（Witness-Recovering Decryption）方法,构造了CPA安全的加密方案。通过对原像选取陷门函数能够满足双射函数的性质的证明,进一步利用Rosen提出的基于一组Correlated Products安全的双射陷门函数构造CCA1和CCA2公钥加密方案的方法,在CPA方案的基础上,利用原像选取陷门函数构造了CCA1和CCA2安全公钥加密方案。（3）基于格的代理签名方案构造：本文研究了Cash等提出的基于LWE的分层IBE方案,其中提出了一种比较实用的技术一格基派生技术,此技术是在某个格的一组短基已知的情况下,使用这组短基来生成另外一个维数更高的格的一组短基的技术。格基派生技术实际上是Gentry定义的原像选取陷门函数技术的推广。由于一组短基实际上就是陷门函数的陷门,因此,格基派生技术可以在基于格的密码方案构造时得到很好的应用。本文将格基派生技术应用于代理签名中代理密钥的生成,结合Gentry等提出的基于原像选取函数构造的数字签名方案,构造了基于格的代理签名方案和多级代理签名方案。本文构造的基于格的密码方案丰富了目前基于格的公钥密码体制的应用和研究,后期我们还将进一步基于格问题的困难假设设计新的密码方案。由于目前方案的安全性都是基于理论证明的结果,如何在实际应用系统中评价这些方案的安全性,以及如何选择安全参数依然是个公开问题,系统参数的选择将决定密码方案的安全性和效率,因此本文进一步的研究工作将主要致力于方案的实际应用,不断改善方案的实用性和效率,为基于格的密码方案真正投入应用做一些力所能及的工作。

论文目录

• 摘要
• ABSTRACT
• 符号说明和缩略词
• 第一章 绪论
• 1.1 背景和意义
• 1.2 国内外研究现状
• 1.3 主要研究内容和成果
• 1.4 论文组织
• 第二章 预备知识
• 2.1 格基本知识
• 2.2 LWE方案
• 2.3 原像选取陷门函数
• 2.4 公钥密码学预备知识
• 第三章 基于LWE的CCA2安全加密方案
• 3.1 基于身份加密1BE
• 3.2 Boneh方法
• 3.3 多比特GPV IBE方案
• 3.4 CCA2安全方案
• 3.5 结论
• 第四章 基于SIS和ISIS的加密方案
• 4.1 证据恢复解密方法
• 4.2 CPA安全加密方案
• 4.3 CCA1安全加密方案
• 4.4 CCA2安全加密方案
• 4.5 结论
• 第五章 基于格的代理签名方案
• 5.1 GPV基本签名方案
• 5.2 格基派生技术
• 5.3 代理签名
• 5.4 代理签名方案
• 5.5 多级代理签名
• 5.6 多级代理签名方案
• 5.7 结论
• 第六章 结论
• 参考文献
• 致谢
• 攻读博士学位期间发表的学术论文目录
• 在读期间参与科研项目情况
• 学位论文评阅及答辩情况表