格困难问题的复杂度分析

作为新型的密码系统,格密码因为其巨大的潜在应用价值备受关注.作为格密码的基石,格困难问题一直是格密码研究的重点.本文通过分析一些常见的格问题,主要包括最短向量问题(SVP),最近向量问题(CVP),小整数解问题(SIS)和误差学习(LWE)等,对相关格问题的复杂度成果进行了总结.结果主要包括两个方面,一方面是SVP,CVP等格困难问题的复杂度分析,本文得到了SVP,CVP和SIVP在不同参数和不同范数下的依据参数大小排序的复杂度表格;另一方面则是不同问题之间的归约,其中包括最坏情况之间,最坏情况和一般情况之间和一般情况之间的归约,本文主要讨论了最坏情况和一般情况归约的结果,并得到了SIS和LWE按归约参数递减顺序排列的表格,并得到了困难问题归约的关系图.此外,文中还给出了格在密码系统上应用的例子.

一种基于格理论的数字签名方案

本文介绍了一种建立在解决 NTRU 格(NTRU Lattice)中近似最近向量问题(Appr-CVP)基础上的数字签名方案。与现有的基于解决 Appr-CVP 问题的数字签名方案相比,这种新的数字签名方案通过构造完整的短格基进行签名,在签名与近似最近向量问题之间建立了直接而清晰的关系,因此不需引入任何附加结构,具有更高的安全性。同时,该签名方案引入了适当的扰动,有效地限制了攻击者通过分析大量签名副本所获取的有用信息,具有副本分析免疫性。实验结果表明:该方案不仅安全可靠,而且易于实现。

新的NTRU格上抗量子攻击的群签名方案

分析以往基于格的群签名方案,虽能有效抵抗量子攻击,但都存在计算复杂度高、通信代价大和系统公钥尺寸过大的弱点,而NRTU格是一类基于多项式环的特殊格,因只涉及多项式环上的乘法和小整数求模运算,与一般格相比,NTRU格密码体制所需公私钥长度更短,运算速度更快。方案中使用NTRU格上高效的参数生成算法,构建了一个新的基于NTRU格的群签名方案,缩短了系统公钥长度,且系统公钥、追踪密钥和签名密钥之间可并行计算,使得计算效率更高,降低了通信代价。方案安全性归约至判定性LWE问题和近似CVP问题的难解性,并给出方案详细的效率分析。

基于格的门限秘密共享算法

基于传统数学假设的秘密共享算法难以有效抵御量子算法的攻击。为此,提出一种基于格的门限秘密共享算法。分析秘密共享基本步骤,包括公钥生成、份额生成以及秘密重构。论述基于格的门限秘密共享算法,该算法可被规约为格上的最近向量问题,并对其安全性进行分析。推算结果证明了该算法具有正确性和安全性。

对DSA和ECDSA的一种改进格攻击

利用格攻击DSA和ECDSA的方法,通过构造同余方程组可以将隐藏数字问题转化为格中最近向量问题,当同余方程组至多有一个解小于给定界限时,可通过求解格中最近向量获取签名私钥。给定界限越大,对解向量的大小要求越宽松,攻击的难度也越低。文章提出一种新的给定界限,其大小是原有界限的6.92倍,显著降低了格攻击的难度。利用从OpenSSL收集到的DSA和ECDSA的签名数据,设计验证新界限的格攻击实验。实验结果表明,新界限对已知解向量元素的要求由最高比特位6位降低到3位。对于DSA,当格的维度为350时,攻击成功率达80%;对于ECDSA,当格的维度为260时,攻击成功率达97%。通过解向量减去一个基准向量,可将对已知解向量元素的要求降低至1位,从而降低格攻击的难度。

一个基于循环格的NTRU类数字签名方案

依据格中的最近向量问题(CVP)提出一种基于NTRU公钥密码体制的数字签名方案。新的数字签名利用循环格基构造循环格,从而得到格中严格的距离消息D最近的向量点。与NSS相比,新的签名方案在签名与最近向量难题之间建立了直接的关系,具有更高的安全性。同时,新的签名方案引入了适当的扰动,有效地弥补了NSS签名中攻击者通过分析大量签名副本获取有用信息的缺陷。

一种基于NTRU格的数字签名

NTRU(Number Theory Research Unit)是一种新型的公钥密码体制,因其高效、快速和运算简单等特点,已得到越来越广泛的应用.其安全性建立在大维数格中的数学难题之上,为此,在研究NTRU算法和格理论的基础上,设计了一种建立在最近向量难题上的数字签名方案.

一个基于ISIS问题签名方案的分析与改进

量子计算具有强大的计算能力。利用量子计算,一些传统的数学困难问题可以被解决,例如:基于大整数因子分解问题、离散对数问题等。2017年,Gupta提出了一个基于格的签名方案,在基于格理论的SIS问题和ISIS问题困难性假设前提下,称提出的签名方案是不可伪造的。笔者对Gupta的方案进行了研究,指出在适应性选择消息攻击下方案是不安全的,并给出了一个新方案。在随机预言模型下证明了新方案的安全性,并将新方案与同类型的5个方案在存储成本方面进行了比较,结果显示出新方案具有更高的效率。

一个新型的NTRU类数字签名方案

NTRU类数字签名方案的一个共同缺陷是签名值会泄露私钥的一些信息.针对这个缺陷,当前已经有若干有效攻击.该文提出一个新型的NTRU类数字签名方案.新方案具有与R-NSS相似的结构,但有若干新颖的设计.文中给出新方案的3个结果:(1)由公钥恢复出私钥的困难性基于若干格上的最小向量问题(SVP);(2)由公钥伪造签名的困难性等价于某个格上的最近向量问题(CVP);(3)每个签名值仍然会泄露私钥的一些信息,但无限制泄露的最终形式只是关于私钥的一组复杂的非线性方程.

基于高斯抽样算法的NTRU类数字签名方案

针对NTRU类数字签名方案的签名值会泄露私钥的部分信息等问题,提出一种NTRU类数字签名方案。该方案通过私钥生成循环格,采用格上高斯抽样算法在此循环格上找出与杂凑后消息最近的向量作为消息的签名值。与现有的方案相比,该方案在保持签名和验证过程效率的同时,安全性方面具有2个新的性质:(1)由公钥伪造签名的困难性是基于循环格上的最近向量问题;(2)由新方案生成的大量签名值在空间分布呈球形,不泄露私钥的任何信息。

原-对偶规约基与连续最小元

最近Koy提出一种质量优于LLL规约基的原-对偶规约基,但没有给出该规约基与最小元比值因子的上界和下界.本文首先分析了原-对偶规约基的性质,然后给出并证明了原-对偶规约基与连续最小元比值因子的上界和下界,最后用原-对偶规约基改进Babai的近似CVP算法——舍入算法,提高了其近似因子.

基于格的公钥密码体制研究

基于格(Lattice)的公钥密码体制是继RSA、ECC之后提出的新型公钥密码体制之一,它包括NTRU体制、Ajtai-Dwork体制、GGH体制等。这些体制的安全性基于求最短格向量困难问题(SVP)、求最近格向量困难问题(CVP)等,并且已经证明,这些体制能够抗量子计算攻击。研讨了对格困难问题及格公钥的相互关系,并展望了格困难问题及格公钥的研究方向。

基于NTRU格的数字签名方案

数论研究组(NTRU)是20世纪末提出的一种新型公钥密码体制,其安全性基于格上的最短向量问题和最近向量问题,被认为具有抗量子计算攻击的能力,和其他公钥密码体制相比,具有密钥短、加解密速度快等优点。基于NTRU格上的最近向量问题提出了一个新的数字签名方案,方案简化了签名过程,提高了签名速度,并且引入了多个扰动因子,有效地防止了签名值泄露导致私钥信息的泄露,最后基于格上的最短向量问题和最近向量问题分析了该方案的安全性。