基于格的伪随机函数研究综述

伪随机函数是密码学领域最基本的原语之一,其自提出以来便备受关注.近几十年间发展起来的格理论在密码领域取得了很多重要的应用成果,特别是格上很多困难问题被普遍认为具备抵抗量子攻击的特性,在后量子密码方案设计中处于核心地位.对于格上伪随机函数的研究正式起始于Banerjee、Peikert和Rosen在2012年欧密会上发表的工作.此后,密码学家们围绕如何基于格困难问题设计伪随机函数方案开展了大量研究,特别是在提升伪随机函数方案的安全性、效率和并行性,以及扩展伪随机函数的功能方面取得了诸多成果.本文对格上伪随机函数的研究现状进行综述:总结了伪随机函数的通用构造方法以及格上伪随机函数依赖的底层困难问题;整理了现有基于格困难问题设计的伪随机函数方案,重点关注这些方案在提升安全性、效率或并行性方面采用的技术以及取得的成果;整理了格上具备扩展功能的伪随机函数的研究进展,包括具有密钥同态性质的伪随机函数、约束伪随机函数、水印伪随机函数以及可验证伪随机函数.

基于矩阵作用问题的公钥密码体制抗量子攻击安全性分析

半群作用问题作为离散对数问题的推广,在公钥密码的设计中有着重要应用。通过分析基于整数矩阵乘法半群在交换群直积上的作用问题的公钥密码体制,将矩阵看作直积元素的指数,这类矩阵作用具有类似群的指数运算法则。首先证明了若矩阵作用是单射或隐藏子群的生成元个数小于或等于矩阵阶的平方,则这类矩阵作用问题可在多项式时间归约为矩阵加法群直和的隐藏子群问题。其次证明了交换矩阵作用问题一定可在多项式时间归约为矩阵加法群直和的隐藏子群问题。因此基于这类矩阵作用问题的公钥密码体制无法抵抗量子攻击,该结论对抗量子攻击的公钥密码设计有理论指导意义。

HFEM公钥密码方案的设计与实现

基于BMQ问题的困难性,以及有限域上的矩阵与向量之间的关系,提出了一种新的公钥密码方案,即隐藏域上遍历矩阵的公钥密码。给出了有关矩阵集合的约束条件以及利用遍历矩阵来构造满足条件之矩阵集合的方法。与已有MPKC方案相比,HFEM具有陷门设计新颖、算法简单、不涉及任何乘幂及复杂运算、加/解密算法效率相当、中心映射难以抽象、密钥/明文/密文空间大等特点。

基于多离散对数问题的公钥密码

该文首先定义了多离散对数问题,给出了现有隐含子群问题量子计算算法不适用于求解该问题的必要条件,且该问题在经典计算模式下,其困难性比离散对数问题难,用于求解有限域上离散对数问题的数域筛法不适用于求解多离散对数问题。然后设计了基于多离散对数问题的公钥密码,其安全性依赖于多离散对数问题,且公私钥的数据量小,分析了算法参数的选取原则,证明了算法脱密原理的正确性,算法在每次加密时需要随机选取一个数,使得算法对同一个明文加密所得的密文不一定相同。

通信密码学前瞻:量子密码技术

安全性是密码学研究一直追求的目标 ,最近取得飞速发展的量子加密技术综合了量子力学原理和经典密码术 ,具有可证明的安全性 ,同时还能对窃听者的非法侵入进行检测 ,克服了传统密码学的桎梏 ,为未来的网络通信提供了真正确实的保障 .此文讨论了量子加密的相关研究及实用化实验模型 ,详细说明了量子密钥分发协议 。

基于多变量公钥密码体制的代理重签名方案

代理重签名方案大多是基于大数分解和离散对数难题设计的,而量子计算机能在多项式时间内求解这些难题,从而给方案造成安全隐患。为此,利用多变量公钥密码体制可以抵抗量子攻击的特性,设计一个新的代理重签名方案。理论分析结果表明,该方案满足内部安全性和外部安全性,且运算效率高。

基于矩阵填充问题的五轮零知识身份认证方案

针对现存绝大多数身份认证协议容易遭受量子计算攻击及实现效率低的缺陷,基于矩阵填充(MC)问题构造了一种安全高效的五轮零知识身份认证方案。由于MC问题是NP完全的,所提方案具有很好的抗量子计算攻击潜力。相较于目前已有类似方案,所提方案通过增加单轮交互将欺骗概率由2/3降至1/2,同时兼具容易实现、密钥尺寸小等优点。此外,采用Fiat-Shamir密码转换技术还可将所提五轮零知识认证协议转换为高效的具有抗量子计算攻击潜力的数字签名方案。

格上基于身份的前向安全签名方案

在前向安全签名方案中,即使当前的秘钥泄露,也能保证先前生成的签名具有不可伪造性。针对已有格上基于前向安全签名方案签名长度过长的不足,利用Lyubashevsky无陷门技术,提出一个高效的前向安全签名方案。在随机预言模型下,基于小整数解困难假设证明了其能抵抗适应性选择消息攻击,无需陷门函数和高斯抽样函数。性能分析结果表明,与现有方案相比,该方案具有前向安全的特性,计算效率更高。

Catch 22问题及其解决方案

研究了密码学中的Catch22问题及其经典和量子密码解决方案,特别研究了量子密码解决方案。研究表明:经典密码学不能完全解决Catch 22问题,而建立在量子力学基础上的量子密码学能提供一个较好的解决方案。

公钥密码体制的现状与发展

文中对公钥密码体制的现状与发展进行了介绍，其中着重讨论了几个比较重要的公钥密码体制M-H背包算法、RSA、ECC、量子密码、NTRU密码体制和基于辫群上的密码体制。

基于多变量公钥密码的代理环签名方案

多变量公钥密码是后量子密码的可选方案之一,受到了广泛的关注。由于已有的代理环签名方案大多基于大整数分解和离散对数等难题设计,都不能抵抗量子计算机的攻击,因此基于多变量公钥密码设计出了一个新的代理环签名方案,该方案基于MQ问题及IP问题设计,不仅满足代理环签名的各项性能要求,还具有抗量子计算特性,且计算简单,效率更高。

破解HFEM公钥密码方案

为设计后量子公钥密码,赵永哲等人提出了一种基于BMQ问题新的公钥方案。利用有限域上遍历矩阵的性质,从该方案公钥能够直接求出其等价私钥,从而破解了该HFEM公钥密码方案。

基于格的可验证秘密共享方案

可验证秘密共享是密码学领域中的一项重要分支.以往可验证秘密共享方案的有效性通常是基于离散对数的数学难题,然而离散对数问题已经被证明在量子计算模型下是不安全的.因此,需要借助格难题去实现可以抵抗量子攻击的可验证秘密共享方案.本文分析现有的可验证秘密共享方案,针对现有方案计算效率低和无法抵御量子攻击的缺陷,利用格密码学中的数学难题,提出一种新的可验证秘密共享方案.该方案相对于以往的可验证秘密共享方案,具有更高的计算效率和抗量子攻击的特性.

Niederreiter公钥密码方案的改进

针对现有Niederreiter公钥密码方案容易遭受区分攻击和信息集攻击(ISD)的现状,提出一种改进的Niederreiter公钥密码方案。首先,对Niederreiter公钥密码方案中的置换矩阵进行了改进,把原有的置换矩阵替换为随机矩阵;其次,对Niederreiter公钥密码方案中的错误向量进行了随机拆分,隐藏错误向量的汉明重量;最后,对Niederreiter公钥密码方案的加解密过程进行了改进,以提高方案的安全性。分析表明,改进方案可以抵抗区分攻击和ISD;改进方案的公钥量小于Baldi等提出的方案(BALDI M,BIANCHI M,CHIARALUCE F,et al.Enhanced public key security for the Mc Eliece cryptosystem.Journal of Cryptology,2016,29(1):1-27)的公钥量,在80比特的安全级下,改进方案的公钥量从原方案的28 408比特降低到4 800比特;在128比特的安全级下,改进方案的公钥量从原方案的57 368比特降低到12 240比特。作为抗量子密码方案之一,改进方案的生存力和竞争力增强。

基于LPN困难问题的后量子安全公钥加密

对基于LPN问题的公钥加密方案进行研究,提出一个低噪紧凑LPN(Exact LPN,xLPN)问题的变体VxLPN(Variant of the Exact LPN,VxLPN)问题,并证明了VxLPN问题和标准LPN问题一样困难。利用双陷门技术,分别构造基于VxLPN的选择明文攻击下的不可区分(Indistinguishability against Chosen Plaintext Attack,IND-CPA)安全的公钥加密方案和基于VxLPN的选择密文攻击下的不可区分(Indistinguishability against Chosen Ciphertext Attack,IND-CCA)安全的公钥加密方案。性能分析表明,在相同安全参数情况下,基于VxLPN的IND-CCA安全的公钥加密方案解码错误率更低。

NTRU格上高效的身份基线性同态签名方案

针对现有的格上身份基线性同态签名方案密钥存储量大、结构复杂导致方案实际运行效率相对偏低的问题,提出了一个NTRU(Number Theory Research Unit)格上高效的身份基线性同态签名方案。首先在密钥生成阶段利用NTRU密钥生成算法产生主密钥,接着采用格基委派算法给出身份签名私钥,最后运行NTRU格上原像抽样算法产生出线性同态签名。对方案的安全性证明与性能分析结果表明,新方案满足正确性,具有弱内容隐私性。在随机预言机模型下,该方案在小整数解问题困难性条件下满足适应性选择身份和选择消息的存在性不可伪造性。同时,由于采用NTRU格的特殊结构,新方案在密钥量与运行效率方面与已有方案相比较均具有显著的优势,这对于计算资源受限环境的同态认证中具有重要的应用价值。

格上基于同态加密的数据完整性验证方案

为使用户存储在半可信云服务器上的数据不被篡改或丢失,提出一种基于格密码算法的数据完整性验证方案。方案安全性基于LWE困难问题,用户运用同态加密算法对数据块进行加密,并将加密密文和原始数据上传至服务器中。分析结果表明,该方案可以实现数据持有者对数据的完整性验证,且支持数据的动态更新。

基于LPN困难问题的后量子安全密钥封装

选择密文攻击下的不可区分(Indistinguishability against Chosen Ciphertext Attack,IND-CCA)安全的密钥封装机制可以由选择明文攻击下的不可区分(Indistinguishability against Chosen Plaintext Attack,IND-CPA)或者选择明文攻击下的单向(One-Wayness against Chosen Plaintext Attack,OW-CPA)安全的公钥加密方案使用FO(Fujisaki-Okamoto)变换得到,并在随机预言机模型(Random Oracle Model,ROM)下是安全的。截止目前,并没有一个基于LPN(Learning Parity with Noise)问题的密钥封装机制能在标准模型下达到选择密文攻击(Chosen Ciphertext Attack,CCA)安全。以双陷门技术回答敌手的解封装询问,以抗第二原像哈希函数检测方案中密文的有效性,由此可得出首个基于LPN在标准模型下达到CCA安全的密钥封装机制的直接构造,其密钥通过特殊LPN问题构造,并不依赖随机预言机。通过一系列的游戏和相邻游戏间的安全规约,可证明该密钥封装机制在量子算法的攻击下是CCA安全的。

基于Niederreiter编码的混合加密方案的改进

基于编码的密码方案具有抗量子的特性和较快的加解密速度,是当今抗量子密码方案的备用方案之一。现有基于编码的混合加密方案已经达到选择密文攻击不可区分(IND-CCA)安全,其缺点是加密收发双方共享秘密密钥的公钥尺寸较大。针对基于Niederreiter编码的混合加密方案公钥尺寸大的的问题,首先对Niederreiter编码方案的私钥进行随机拆分,然后对Niederreiter编码方案的明文进行随机拆分,最后对Niederreiter编码方案的加解密过程进行了改进。经过分析得出,改进方案的公钥尺寸小于Maurich方案的公钥尺寸,在80比特的安全级下,改进方案的公钥从原方案的4 801比特降低到240比特;在128比特的安全级下,改进方案的公钥从原方案的9 857比特降低到384比特。虽然改进后的方案比原方案过程复杂,但其存储代价和计算代价变小,方案的实用性增强。

McEliece编码签名方案的设计

针对现有Niederreiter编码签名方案存在安全性低、签名速度慢的缺点,设计了一种McEliece编码签名方案。首先,对McEliece密码方案的加解密过程进行改进,以提高方案的安全性;其次,利用改进后的McEliece密码方案设计了一种编码签名方案。分析结果表明,改进后的McEliece密码方案具有较高的安全性;设计的McEliece签名方案具有较高的安全性和较快的签名速度;在同等安全级下,Hash次数由Niederreiter编码签名方案的32 881次降低为25次,译码次数由Niederreiter编码签名方案的32 880次降低为24次。作为抗量子签名方案之一,设计的McEliece编码签名方案的生存力和竞争力较强。