基于格的数字签名方案研究与设计

顾晶晶　储逸　崔洛宾　卞欢陆　蔡秋茹

【摘 要】NTRU 是一种公钥密码体制，由于其效率高、快速、运算方便、可抵抗量子计算，因此取得了广泛的应用，密码学界广泛认为其安全性基于理想格中最近向量的困难问题，本文将介绍一种基于格上难题（最短向量NP问题）的NTRU型数字签名方案的密钥生成，加密算法，解密算法的具体实现过程。

【关键词】格；NTRU；数字签名；格上最短向量问题

中图分类号： TN918.1；O153.1 文献标识码： A 文章编号： 2095-2457（2018）06-0013-002

【Abstract】NTRU is a public key cryptosystem.Because it is efficient，fast，easy to operate，and resistant to quantum computation，it has been widely used.The cryptography community widely believes that its security is based on the difficulty of the nearest vector in the ideal lattice.This article will introduce a specific implementation process of key generation，encryption algorithm，and decryption algorithm based on the NTRU type digital signature scheme based on the lattice problem （shortest vector NP problem）.

【Key words】Lattice；NTRU；Digital signature；Lattice shortest vector problem

0 引言

NTRU公鑰密码被认为是可以抵抗量子计算机攻击，因其密钥量小、加解密效率高、安全性好的特点，在公钥密码学中一直是一个研究的热点[1]，并于2009年被纳入IEEE P1363.1标准[2]。在数字签名上，常基于格上难题问题（最短向量问题SVP、最近向量问题CVP等），但是由于设计者[3]采用了附加的结构来完成签名构造，而正因这些附加结构的引入，使得签名和其理论基础之间出现了不完整和模糊关系，致使基于NTRU的数字签名方案仍有缺陷（签名值会泄露私钥部分信息），例如：R-NSS和NTRU Sign都已经被证实不安全[4]。

针对这些问题，本文将介绍一种新的基于格中最短向量难题的数字签名方案，方案通过NTRU格中已知短向量寻找另一组短向量，从而构造一个完整的短格基，同时还添加了消息扰动结构，用于提升已有攻击方案破解数字签名的难度，因此具有更好的抗攻击能力。

本文结构如下：第一部分为引言部分，第二部分介绍相关数学概念和定理[5，6]。第三部分介绍具体数字签名、密钥生成，加密算法，解密算法的具体实现过程。第四部分介绍对安全性的分析。

1 预备知识

1.1 多项式环与多项式的逆

NTRU是建立在整数环Z[x]/（XN-1）上面的密码体制，令Z为整数环，设P为整数多项式上的商环Z[x]/（XN-1），则P可用集合Z[x]/（xN-1）来表示，即P上每一个元素都可以表示为■，令a，b？缀P，a+b定义为两个多项式对应的系数相加，P上的两个元素的乘用*表示，令c=a*b，则c的第k个系数为：

3 安全性分析

3.1 签名方案的依难题据：

由于该方案是建立在格CVP难题上，用私钥构造出格中短循环基，由于私钥生成格中短向量，因此为严格的格中CVP问题，具有可靠的安全性。

3.2 GCD攻击的可能：

若攻击者用GCD攻击获得f。对于NSS签名，由于NSS中有一个mod p的条件，从而攻击者进行归纳，将mod q的f*wmodq和g*wmodq值提升到R（实数域）上，得到没有模的f*w和g*w的值，通过公因子方式得到：导致攻击成功，但是本文中的方案，要构造：

由于只有一个modq使得签名复杂度O（N2）程度形式上升。

3.3 副本攻击伪造签名：

NTRU类数字签名会泄露一定信息，若收集其副本，通过大量的副本会导致信息泄露，因此在该数字签名方案中对消息引入了扰动。

由于扰动的引入使得矩阵信息泄露的数量成指数形式递减，从而本方案对副本攻击是安全有效的。

4 结束语

本文对当前基于格的数字签名方案进行了研究，对算法进行改进，基于循环格基，建立在严格的CVP问题之上，避免了NSS、NTRUSign中的线性构造关系，同时加入了扰动，保证了方案的安全性，同时具有良好的时效性并且便于实现。

【参考文献】

[1]Borrows M，Abadi M，Needham R M.A logic of authentication[J].ACM Transactions on Computer Systems，8（1）：18-36，1990.

[2]古春生.NTRU公钥密码的可视化教学.江苏理工学院学报，2014，20（4）：90-92.

[3]GoldreichO.GoldwasserS.Halevy.Public-key cryptography from lattice reduction problems，1294（56）：112-131，1997.

[4]RivestR，ShamirA，Adleman L.A method for obtaining digital signatures and public-key cryptosystems[J].Communication of the ACM，21（2）：120 -126，1978.

[5]李筱熠.一种基于NTRU格的数字签名.上海工程技术大学学报，23（1）：56-59，2009.

[6]潘彦丰.基于NTRU的数字签名方案分析.计算机工程，2010，36（22）：145-146.

[7]Gentry C.JonssonJ.SternJ.Ctyptanalysis of the NTRU Signature Scheme（NSS），2248：1-20，2001.

[8]张卷美、曹杰等.一种基于NTRU新型数字签名方案的设计.四川大学学报，47（1）：49-53，2015.

[9]杨智超、付绍静等.基于NTRU算法的新型广播攻击.密码学报，36（22）：596-606，2016.

[10]张建航、胡予濮、来齐齐.基于高斯抽样算法的NTRU类数字签名方案.计算机工程，38（17）：126-128，2012.

[11]毕经国.格理论在公钥密码分析和计算机代数中的应用[D].山东：山东大学，2007.