基于格的數字簽名方案研究與設計

顧晶晶　儲逸　崔洛賓　卞歡陸　蔡秋茹

【摘 要】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.