基于格的可证安全的签名方案研究

发布时间：2018-05-12 16:56

本文选题：密码学 + 格密码　；参考：《山东大学》2014年硕士论文

【摘要】：现代密码学以很多数学工具为基础,格是现代密码学中极具吸引力的一种数学工具。基于格的密码研究近年来发展很快,现在几乎已经涉及了各种密码领域,如基本公钥加密、基本签名、群环签名、基于身份的加密、基于属性的加密,甚至于半同态或全同态加密。格密码的兴起源于量子计算机概念的逐步成熟。在量子计算机上,基于传统困难问题,如大整数分解问题、离散对数问题、椭圆曲线问题等,构造的密码方案,其安全性将受到严峻的挑战。因为在量子计算模型下,可以同时进行指数级别的运算,也就是说,传统计算模型需要指数时间完成的运算,量子计算模型只需要多项式时间。这是因为一个量子比特可以同时具有多种状态,而不像电子比特只能具有两种状态。基于格理论构造的密码方案极具吸引力,其原因是多方面的。首先,从理论上来说,格密码基于最坏情况困难问题假设,这比基于数论平均情况困难问题的假设要弱,也就是说安全性保障更强；并且,部分规约属于量子规约,使得格密码在某些困难问题假设下可以抵抗量子攻击。其次,在实现方面,格密码的基本运算只有矩阵和向量的模乘运算,而模数通常是小素整数,运算非常简单,不需要“大数”函数库的支持；另外,由于格结构的规整性和运算特点,很容易构造并行算法,事实上,格规约和格取样算法都有了GPU并行实现。本文的选题来源于格密码领域中的签名部分。在本文中,我们构造了两种签名方案,并分别在不同模型下、不同敌手能力下证明了其安全性,一种是在随机预示模型下,另一种在标准模型下。首先,我们使用格基代理技术,借鉴“分享校验子”思想,暨分享消息,实现了门限签名,并在随机预示模型下,证明其在适应性选择消息攻击下具有存在性不可伪造性。具体地,我们用格基代理算法,将“权力”代理给多个参与方,以实现“权力”的分散；用Shamir秘密分享算法分享待签名的消息,以实现门限机制。我们采用的格基代理算法,不会增加格的维度,从而可以很容易地合并各个签名分享。然后,我们考虑另一种格签名模式,不同于前者将消息散列为校验子,后者把消息散列为随机格矩阵,校验子置为随机向量或零向量,再通过取样算法得到签名。我们使用可容许哈希函数技术消除证明过程中的随机预示,在标准模型下,证明其满足适应性选择消息攻击下的存在性不可伪造性。本文的创新点主要有： ·用格做构造工具,方案具有天然的抗量子攻击特性； ·用分享消息的方式,配合格代理算法实现门限签名； ·把可容许哈希函数应用到签名方案上,消除随机预示。本文未实现的方面有：在门限签名中,没有消除可信第三方,目前是因为如果没有可信第三方,敌手视图难以模拟；可容许哈希函数会把公钥维度扩展到原来的平方倍,实用性不够,这和可容许哈希函数结构有关,为了满足可容许性,构造时和格维度做了折衷。
[Abstract]:Modern cryptography , based on many mathematical tools , is a very attractive mathematical tool in modern cryptography . The lattice - based cryptography has developed rapidly in recent years . It has now almost dealt with various cryptographic fields , such as basic public key encryption , basic signature , group ring signature , identity - based encryption , attribute - based encryption , and even semi - homomorphism or all - homomorphic encryption .

The rise of lattice passwords is derived from the gradual maturity of quantum computer concepts . Based on traditional difficult problems , such as large integer decomposition , discrete logarithm problem , elliptic curve problem and so on , the security of a quantum computer is severely challenged . Because in the quantum computing model , exponential - level operations can be performed at the same time , that is , the traditional computing model needs an exponential time to complete the operation , and the quantum computing model only needs polynomial time . This is because a quantum bit can have multiple states at the same time , unlike electronic bits only .

Firstly , based on the assumption of the worst - case problem assumption , this is weaker than the hypothesis based on the problem of the average situation of the number theory , that is , the security assurance is stronger ;
Moreover , some protocols belong to quantum protocols , so that the lattice passwords can resist the quantum attack under the assumption of some difficult problems . Secondly , in the realization aspect , the basic operation of the trellis codes is only the modulo multiplication operation of the matrix and the vector , and the modulus is usually a small prime integer , the operation is very simple , and the support of the " large number " function library is not required ;
In addition , due to the regularity and operation characteristics of the lattice structure , the parallel algorithm is easy to construct . In fact , both the lattice structure and the lattice sampling algorithm are realized in parallel with the GPU .

In this paper , we construct two kinds of signature schemes . In this paper , we construct two kinds of signature schemes , and prove their security under different models . One is under the stochastic predictive model , and the other is under the standard model .

First , we use lattice - based proxy technology to draw lessons from the idea of " sharing check " and share the message , implement the threshold signature , and prove that it has the existence non - forgery under the adaptive selection message under the stochastic predictive model . Specifically , we use the lattice - based proxy algorithm to proxy " power " to a plurality of participants to realize the dispersion of the power ;
Shamir ' s secret sharing algorithm is used to share the message to be signed in order to implement the threshold mechanism . The lattice - based proxy algorithm used by us does not increase the dimension of the grid , so that the signature sharing can be easily merged .

Then , we consider another lattice signature mode , which is different from that of the former , which lists the message as a random lattice , and the latter is set as a random vector or a zero vector , and then the signature is obtained by the sampling algorithm . We use the admissible hash function to eliminate the stochastic prediction in the proof process , and prove that it satisfies the existence non - forgery of the adaptive selection message under the standard model .

The innovation points of this paper are as follows :

lattice is used as construction tool , and the scheme has natural anti - quantum attack characteristics ;

using the way of sharing the message , the matching grid proxy algorithm implements the threshold signature ;

applying the allowable hash function to the signature scheme to eliminate the random indication .

It is not realized in this paper that the trusted third party is not eliminated in the threshold signature , because if there is no trusted third party , the enemy ' s view is difficult to simulate ;
The allowable hash function extends the public key dimension to the original square and is not practical enough , which is related to the allowable hash function structure , which compromises the admissibility , structure , and lattice dimensions .

【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TN918.1

【共引文献】