基于格的密码体制概述

王黎

摘要：本文主要对基于格的密码体制进行了概述，首先简述了格基密码体制的起源，而后分别分析了格基加密体制和格基签名体制的发展历程。

关键词：格;加密体制;签名体制

一、引言

格理论在密码学中的首次应用，是作为一种密码分析工具。许多非基于格的密码方案的安全性分析，可归约到格上的困难问题，进而可以利用求解这些困难问题的算法进行安全性分析。

二、格基加密体制的发展概述

1997年，Ajtai和Dwork首次基于格上困难问题构造了一个加密方案——AD加密体制[1]，这是第一个被证明了的系统中任意实例的安全性与最难实例的安全性等价的密码方案。此后密码学者又陆续提出了GGH密码体制[2]和NTRU公钥密码体制。

2005年，Regrev提出了格上带差错的学习问题，并证明了其复杂性可归约到格上的Gap-SVP和SIVP問题的困难性上。基于LWE问题，Regrev设计出了一个选择明文攻击安全的格基加密算法。随后，大量基于格的公钥密码算法被提出，并且随着研究的深入，格基加密方案的安全性越来越高。2008年，Peikert和Waters设计出了第一个选择密文攻击安全的加密方案，其后Peikert在2009年基于LWE问题并结合混合加密的设计思想给出了第二个格基CCA安全的加密方案。

格基密码的另一重大突破出现在2009年，Gentry在理想格上实现了全同态加密方案的构造，从而解决了困扰密码学者三十多年的公开难题，并且在云计算、云存储日益盛行的今天，有着广阔的应用和发展前景。

三、格基数字签名体制的发展概述

格基数字签名体制的发展大体可以分为两个阶段。在第一个发展阶段，主要是基于NTRU格的困难性设计出了多个NTRU签名方案，如：NSS，R-NSS和NTRUSign等。2001年，NTRU的设计者提出了NSS签名算法，但该算法存在重大缺陷。随后其设计者J.Hoffstein等人对其进行改进并提出了R-NSS签名算法。2008年，胡予濮教授提出了一种新的NTRU数字签名方案，新方案同时具备NSS算法的简洁性和NTRUSign算法的安全性。

随着2008年Gentry等人在文章中提出了原像抽样函数的概念，并借助PSF设计出首个随机预言机模型下可证明安全的格基数字签名方案，格基数字签名进入到了快速发展的第二阶段。

2010年，Cash等人提出了盆景树模型的概念，并基于盆景树模型构造了一个标准模型下可证明安全的数字签名方案，但是盆景树模型的结构特点使得方案的公钥和签名的长度以及空间复杂度都很大，并且方案是EU-sCMA安全的。然而，盆景树模型却为密码学者构造具有特殊性质的数字签名算法提供很好的思路，并取得了大量的研究成果。同年，Boyen提出一个更加高效的格基数字签名方案。Boyen提出了双边陷门的概念，并使用消息选择技术使得签名长度显著减小。而Agrawal等人设计出了一种固定维数的格基委派算法，与盆景树模型相比，该算法通过选择合适的矩阵，利用矩阵乘而不是矩阵的级联进行扩展，保证了扩展后的格与上一级格具有相同的维数，进而使得公钥和签名长度减小。值得一提的是上述方案都是以PSF为基础的，因而构造出好的陷门生成函数一直是格基数字签名的一个重要研究方向。2011年，Alwen和Peikert对Ajtai陷门生成算法进行了改进。2012年，Micciancio和Peikert在欧密会上提出了一个新的陷门生成算法，与之前的算法相比，该算法更加简单高效。在其基础上，Micciancio等人提出了新的原像抽样算法和陷门委托算法，进而构造了一个高效的格基数字签名算法，并在标准模型下对方案的强不可伪造性进行了证明。

另一方面，Lyubashevsky借助Fiat-Shamir模型构造出了一种无陷门的格基签名方案，方案通过使用拒绝性采样来生成签名，其安全性可归约到SIVP问题的困难性上。并且通过改变参数，方案可以转变成一个更加高效的基于LWE问题的数字签名方案。相比于基于陷门构造的签名方案，Lyubashevsky的方案结构更加简单，密钥和签名更短，并且只需进行矩阵乘法和拒绝性采样运算，因而效率更高。

四、结束语

在大数据时代，数据的价值越来越重要，而其安全性遭受到各种威胁，因而研究出高效安全的加密及签名算法显得及其重要。

参考文献：

[1]Ajtai M，Dwork C.A public-key cryptosystem with worst-case/ average-case equivalence[C].Proceedings of the twenty-ninth annual ACM symposium on Theory of computing.ACM，1997：284-293.

[2]Goldreich O，Goldwasser S，Halevi S.Collision-free hashing from lattice problems[C].Electronic Colloquium on Computational Complexity （ECCC）.1996，3（42）：236-241.

[3]Goldreich O，Goldwasser S，Halevi S.Collision-free hashing from lattice problems[C].Electronic Colloquium on Computational Complexity （ECCC）.1996，3（42）：236-241.

[4]Nguyen P.Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from crypto’97[C].Advances in Cryptology—CRYPTO’ 99.Springer Berlin Heidelberg，1999：288-304.