基于格的公鑰加密體制的研究

潘 平，王勵成，何萬生

（北京郵電大學 計算機學院，北京 100876）

引 言

公鑰密碼的思想由Diffie和Hellman提出以來，許多實用的公鑰密碼體制被建立并得以廣泛的研究.這些體制的安全性大都依賴于數學中的某些難解問題.目前廣泛使用的兩類公鑰密碼體制：RSA體制及其變種和ElGamal體制及其變種，其安全性分別基于大整數分解問題和離散對數問題.然而，人們已經找到了這些問題的多項式時間的量子算法攻擊方法，這意味著在量子計算機時代，這些密碼體制的安全性面臨威脅.于是，人們開始積極尋求新的公鑰密碼體制的實現平臺，并設計新的能夠抵抗量子算法攻擊的密碼方案（即后量子密碼，Post-quantum Cryptography）已經成為密碼學研究的前沿課題.

目前，后量子密碼的研究方向主要包括：基于哈希的密碼體制、基于編碼的密碼體制、基于格的密碼體制、基于多變量的密碼體制等等.其中，基于格的公鑰密碼體制的研究和應用取得了喜人的成果和發展.比如著名的 AD 體制[1]（1997）、GGH 體制[2]（1997）、NTRU體制[3]（1998）、Regev體制[4]（2005）、GPV體制[5]（2008）、Peikert體制[6]（2009）等等.這些體制的安全性分別基于格的最近向量問題（CVP）、最短向量問題（SVP）、uSVP問題、錯誤學習問題（LWE）、最小整數解問題（SIS）等等.

格是一種典型的線性代數結構.由于格豐富的組合結構，使得格成為近年來計算科學領域中活躍的研究課題.1996年，Ajtai[7]發現了某些格問題的最壞情形復雜性與平均情形復雜性之間的聯系，從而引發了對格問題復雜性的一系列研究，使得格在密碼學中得以廣泛的應用，出現了許多基于格難題的密碼體制（以下簡稱格基密碼體制）.

利用格構建公鑰密碼體制之所以吸引人，其主要原因有兩方面：（1）格基密碼體制的安全性可規約于最壞情形下特定格問題的難解性.也就是說，攻破了這些格基密碼體制意味著能求解其相應格難題的所有實例；（2）格基密碼體制的加解密速度非常快.

1 格上的密碼學難題

1.1 格的相關概念

格是m維空間中具有周期性結構離散點的集合.具體定義如下：

定義1（格）設Rm是m維歐式空間，設向量b1，…，bn是n個線性獨立的m維向量（m ≥ n），格定義為：

向量b1，…，bn稱為格的一組基.幾組不同的線性無關向量可表示同一個格，此時這幾組向量都稱為格基.可用矩陣表示格，設B=（b1，…，bn）?Rm×n，則格L（B）=｛Bx—x?Zn｝.

當n=m時，稱格L（B）是滿秩或滿維的.以下如無特別說明，均為滿維格.

定義2（對偶格）任意格基B?Rn×n，定義對偶格為：

則 L（B）*=L（（B-1）T）.

定義3（q元格）設A?Zqn×m是n×m矩陣，q，m，n是整數，兩個m維q元格定義為：

定義4（理想格）設n是2的冪次方，f是有理數域Q上的不可約多項式，如f=xn+1.設R=Z［x］/f，I是R的非零理想，則滿足的整數格L（B）稱為理想格.

m維空間中的格點也可看作是m維向量，稱為格向量.對于格向量，可定義不同的范數，如2-范數（也稱歐氏范數），p-范數，無窮范數等.以下如無特別說明，均視為2-范數，即格向量a=（a1，…，an）?Rn，其范數定義為

1.2 格上難題

下面介紹幾種典型的計算型格問題：

最短向量問題（SVP）：給定格基B?Zm×n，找格中的非零向量 Bx（x?Zn），使得對任意的非零向量滿足

最近向量問題（CVP）：給定格基B?Zm×n和目標向量t?Zm，找格中的非零向量Bx（x?Zn），使得對任意的 y?Zn，滿足‖Bx-t‖≤‖By-t‖.

uSVP問題：給定格基B?Zn×n，找格中的非零向量v，使得v是唯一最短向量，且長度至多是v的nc倍的其他向量都平行于v.

最短獨立向量問題（SIVP）：給定格基B?Zn×n，找n個線性獨立的格向量S=（s1，…，sn）（1≤i≤n），使得最小.

R-LWE問題：設n是2的冪次方，f（x）=xn+1? Z［x］，q=1mod 2n是大素數模.設Rq=Zq［x］/＜f（x）＞為模f（x）和模q的所有整系數多項式環，s=s（x）?Rq，隨機選擇a?Rq，e取自Rq上的某個高斯分布，輸入一對（a，as+e），計算s.

2 基于格的公鑰加密體制

目前為止，基于格的公鑰加密體制研究取得了顯著的成就.如公鑰密碼體制[1]和有可證明安全的加密體制，[8]基于身份的加密體制[5-6]，[10-11]，全同態密碼體制[12]等.這些密碼體制的構造分為兩類：一類體制效率高、實用性強，但沒有可證明安全性；另一類體制雖然其安全性證明是基于最壞情形下的格問題的困難性，理論上也有效，但不實用.

下面介紹幾種著名的基于格的公鑰加密體制.

2.1 基于uSVP的公鑰加密體制

Ajtai和Dwork[1]在1997年首次提出了最壞情形下基于O（n8）-uSVP難題的公鑰密碼體制.隨后Goldreich等人[2]提議如何消除AD方案中存在的解密錯誤，并將該方案改進到O（n7）-uSVP.在2004年Regev[4]提出的基于O（n1.5）-uSVP加密方案相當簡單，僅有整數模運算，有很強的安全性.但是以上幾個公鑰密碼體制的效率很低，公鑰長度太長，密文擴展也太大.

Ajtai和Dwork設計了三種版本的新型公鑰密碼算法AD1、AD2和AD3，統稱為AD密碼算法[1].其描述如下：

密鑰生成：如果u是uSVP格的最短向量，那么可由u確定一組超平面，這組超平面作為私鑰.然后通過一些特殊的方法，生成與這組超平面很接近的一個空間點，這個點就是公鑰.根據這個點找出其超平面的難度等價于求解最壞情形下的uSVP問題.

加密：按逐比特進行加密.加密0時，通過公鑰找到某個超平面附近的一個隨機向量，然后對這個向量在一個很小的領域內進行擾動，擾動后的向量就是0的密文.加密1時，隨機地從空間中選擇一個向量，這個向量就是1的密文.

解密：用私鑰（超平面）檢查密文對應的點是否足夠靠近某個超平面.如果是，則解密為0，否則為1.

顯然，AD存在解密錯誤的可能.對0加密后總能解密成0，但對1的加密有可能被解密成0，發生解密錯誤.但可以選取適當的參數，降低AD體制解密失敗的概率.

Regev[4]公鑰加密體制如下所示：

解密：如果密文除以N/h的余數很小時，解密為0，否則為1.因為a1，…，am均離N/h的整數倍數很近，則0的密文∑i?Sai也離N/h的整數倍數很近.因此0的密文能被正確地解密；同樣，遠離N/h的倍數，那么1的密文也遠離N/h的倍數.從而可以正確解密為1.當然，這個方案也存在解密錯誤.

2.2 基于CVP的公鑰加密體制

1997年Goldreich等人[2]提出基于CVP難題的GGH密碼體制，GGH是最直觀的基于格的公鑰密碼體制.該體制的密文是將對應于明文的格向量加上一個隨機噪聲向量而得；公鑰和私鑰是同一個格中的兩種不同表示.私鑰具有特殊的結構，它允許在一定界限下消去噪聲向量.

GGH公鑰加密體制描述如下：

密鑰生成：私鑰為一個“好”的格基B，即由短且幾乎正交的向量組成.從數學意義上講，如果輸入是一個良好的規約基，則可在較短時間內準確地找到靠近目標向量的格點.即有效求解近似CVP問題的某個實例.公鑰是一個“壞”基H，使得L（H）=L（B），即公私鑰是同一個格的兩個不同基.

加密：消息為格點v，加上隨機產生的擾動向量r，形成的密文為c=v+r.

GGH密碼體制沒有達到語義安全，因為其加密過程是確定型的（即很容易區分出密文所對應的明文）.即使取適當大的安全參數，GGH密碼體制也容易被攻破，因而實際上GGH是不安全的.另外，GGH也存在解密錯誤現象.GGH選擇體制參數可使出現解密錯誤的概率控制在10-5以下.

2.3 基于LWE及R-LWE的公鑰加密體制

在2005年，Regev[4]提出LWE問題并證明在適當假設下LWE問題是難解的.第一，LWE在目前最好的算法下是指數級的運行時間；第二，LWE是LPN（錯誤奇偶校驗學習）問題的擴展，而LPN在機器學習領域中認為是難的；第三，LWE與最壞情形下的某些格問題一樣難，如，近似SVP和近似SIVP.

近年來，LWE在密碼構造中有著非常廣泛的應用.如選擇明文安全（CPA）的加密方案：Regev05[4]，PVW08[13]等；選擇密文安全（CCA）的加密方案：PW08[9]，Pei09[6]等；不經意傳輸協議 PVW08[13]；基于身份的加密方案：BCHK06[14]，GPV08[5]，ABB09[10]等；密鑰泄露容忍的加密方案：GPV08[5]，AGV09[15]，GKPV10[16]等.LWE問題之所以有很強的吸引力，除其能夠抵抗量子算法攻擊外，還具有高效性和低復雜性的運算（主要是加法）.

2.3.1 基于LWE的公鑰加密體制

Regev[4]構造了第一個基于LWE的可證明安全的密碼體制.后來，Peikert等人[13]給出基于LWE的多比特的PVW公鑰密碼體制，其在時間和空間效率上都有很大的改進.

Regev公鑰加密體制如下所示：

體制參數：設m，n，p均是整數，χ是Zp上的概率分布.

Regev公鑰加密體制的公鑰長度為O（n2），在加解密中每加密一比特需要?（n2）比特的運算，每加密一比特擴展了?（n）.

PVW公鑰加密體制描述如下：

體制參數：設m，n，p，l是整數，q＞ p是素數.對每一個v?Zp（即一個消息的一個坐標），定義v的“補償”為ω（v）=「v·q/p」?Zq.χ是Zp上的概率分布.設R≤q是整數，定義行向量的集合 ? =［0，R-1］1×m? Zq1×m.

密鑰生成：隨機選擇矩陣S?Zqn×l，S為私鑰.隨機選取矩陣A?Zqm×n和E?Zqm×l，其中E中的每一個元素ei，j服從分布χ.公鑰為一對（A，B=AS+E）?Zqm×n×Zqm×l.

加密：對于表示成行向量的待加密消息 v?Zq1×l，ω=ω（v）?Zq1×l.選擇一個行向量r?? ìZq1×m，密文為（u，c），這里 u=rA?Zq1×n，c=rB+ω?Zq1×l.

解密：對于私鑰S和密文（u，c），計算d=c-uS?Zq1×l，然后輸出明文 v?Zq1×l，使得v中的每一個元素 vi滿足di-ω（vi）?Zq離0 mod q最近.

PVW公鑰加密體制在時間和空間效率均改進到線性因子.特別是，在加解密中每加密一比特只需?（n）比特的運算，每加密一比特擴展到O（1）.以上兩個方案比AD公鑰密碼體制好，但在公鑰長度上仍不理想.

2.3.2 基于R-LWE公鑰加密體制

LWE已經成為密碼構造的主要部分.基于LWE的密碼方案常常需要相當大的密鑰長度，通常是n2階.2010年，Lyubashevsky等人[17]提出LWE的代數變種，R-LWE，并證明：假定不存在多項式時間的量子算法能夠求解理想格上的最壞情形問題，則R-LWE的分布是偽隨機的；同時給出第一個真正實用且有效的有可證明安全的公鑰密碼體制.他們預言R-LWE問題的代數結構可能會引起新的密碼應用.

下面介紹基于R-LWE的公鑰加密體制：

體制參數：設f（x）=xn+1?Z［x］，其中n是2的冪次方，q=1mod 2n是大素數模.R=Z［x］/＜f（x）＞為模f（x）的所有整系數多項式環，設Rq=Zq［x］/＜f（x）＞為模f（x）和模q的所有整系數多項式環.

密鑰生成：設m是安全參數，元素ai?Rq.選擇m個“小”ri?R.計算am+1=∑i?［m］ri·ai?Rq.公鑰為a1，…，am?Rqm+1，私鑰為r1，…，rm，rm+1=-1 ?Rm+1.

加密：加密n比特消息z?｛0，1｝n，隨機選擇s?Rq，ei服從Rq的某個分布.對于每一個i?［m］，計算

則密文為b1，…，bm+1?Rqm+1.

解密：待解密密文b1，…，bm+1?Rqm+1和私鑰 r1，…，

以上方案只需Zq上的O（n）個元素，利用快速傅里葉變換，可以使得向量上的運算速度更快，從而其密碼構造有小的密鑰且運算速度也相當快.

NTRU方案是Hoffstein，Pipher和Silverman提出的目前很實用的加密方案.但是，NTRU沒有可證明安全，也遭到各種攻擊.最近，Stehlé和Steinfeld［18］結合NTRU公鑰密碼體制和R-LWE思想，通過以下幾點改進，使得改進后的NTRU在理想格上最壞情形格難題下達到CPA安全，并給出可證明安全.

第一，改進的NTRU是基于環R=Z［x］/＜xn+1＞而不是RNTRU=Z［x］/＜xn-1＞的加密體制.

第二，選擇素數q使得f=xn+1mod q有n個不同的線性因子，即q=1mod 2n.這樣使得在Rq=R/q上搜索型R-LWE可以規約到判定型R-LWE，p仍取2.

第三，f，g取樣于R的離散高斯分布，其中f滿足f=1mod p，設f在模q下的逆元為fq-1，私鑰為f?Rq，h=pg fq-1mod q，公鑰為h?Rq.

第四，在原加密算法中加上一個小擾動e，密文為c=m+rh+pe mod q，這里r，e是取樣于R-LWE的錯誤分布.

第五，解密簡化為m=（fc mod q）mod p.

改進后的NTRU加、解密Ω（n）比特明文時只需?（n）比特運算，就能獲得抗 2g（n）-time攻擊的安全，這里g（n）介于Ω（log n）和о（n）之間.

R-LWE的代數結構給基于格的密碼設計的真正實用性帶來了很大的希望，同時也在密碼領域中引起了格理論的進一步發展.

3 基于身份的加密體制

最早提出基于格的身份加密（IBE）方案是Gentry等人.[5]隨后 Peikert，[19]Agrawal等人，[10]和 Cash等人[20]先后提出了安全、有效的基于格的IBE/HIBE方案.

Gentry等人[5]表明：在Regev公鑰加密體制中，公鑰是靠近格點的某些點，這些點在格空間是指數級稀疏的.相比之下，密文在空間上是均勻分布的.但是如果要構造IBE體制時，那么在Regev公鑰體制中如何把身份映射為有效的公鑰呢？為此Gentry等人提出簡單解決此問題的辦法，即Regev公鑰加密體制的“對偶”體制，稱為DualRegev公鑰加密體制，其本質是對公鑰和密文進行交換.以DualRegev公鑰加密體制為主要部分，構造了隨機預言模型下基于LWE的匿名安全的IBE體制.另外，他們又提出新的陷門原語概念，稱為原像可取樣陷門函數.這個陷門函數與隨機預言模型下幾個著名簽名方案中的陷門置換相比，其功能更強.

Peikert[19]在2009年提出新的基于格的密碼原語，稱為盆景樹（bonsai tree）技術，并利用這個技術構造了不依賴于雙線性配對的HIBE方案（標準模型下）.Peikert表明該方案的安全性是基于標準的LWE且是等級匿名的.就是說，從計算上看，密文隱藏了被加密的身份.

隨后，Agrawal和Boyen[10]構造了標準模型下基于隨機整數格上LWE問題的IBE體制.該體制具有偽隨機密文的匿名性.文獻[10]給出IND-sID-CPA安全（即選擇性ID、選擇明文攻擊下達到不可區分）的IBE，利用身份的比特分解可以得到完全自適應性ID安全的IBE.也表明利用指數規約或組合變換，可以得到更有效的IND-ID-CPA安全的IBE方案.

接著，Cash，Hofheinz和Kiltz[20]提出一個新的密碼原語，稱為基授權，即允許一個人通過安全方式用給定格的一個短基來導出相關格的新的短基.本質上來說這些短基的作用類似于密碼中的陷門.基授權技術的主體思想被認為是GPV的原像可取樣思想的一般化，有著更靈活、更廣泛的應用.從技術層次上看，基授權技術等價于Peikert的盆景樹技術.利用基授權技術，他們得到了如下幾個新的構造：第一，構造了第一個標準模型下有可證明安全的無狀態數字簽名方案和IBE方案，其安全性是基于最壞情形下的LWE.第二，構造了隨機預言模型下有可證明安全的相當高效的HIBE，其安全性是基于最壞情形下的LWE.這個構造利用基授權實現了密鑰的階層.第三，構造了同樣難題假設下無隨機預言模型的可證明安全的HIBE方案.他們認為可以利用BCHK[14]的變換將CPA安全的d-HIBE轉換成CCA安全的（d-1）-HIBE.

文獻[5]中的IBE/HIBE方案都是把身份看成是一系列比特數，對每一比特分配一個矩陣.這樣的加密體制是相當完美的，但是與隨機預言模型下的GPV加密方案相比，還是很低效的.2010年，Agrawal等人[10]構造IBE體制時，把身份看成塊，產生與GPV體制中隨機預言模型下相同維數的格，將格分為“左”格和“右”格.“左”格的陷門只作為體制的主密鑰，可以為所有的身份生成私鑰.“右”格的陷門只用在安全性證明中，使得模擬器為所有身份生成私鑰，當然除挑戰的身份外.另外，一般的基于格的密碼體制是定義在相對小的域Zq，這樣使得編碼后的身份取自于1，…，q，導致體制的身份太少.在方案中把身份看成Zqn上的向量（共有qn個身份），然后利用編碼函數H映射成Zqn×n上的矩陣，這里H是單射以便在安全性證明中，對于不同的身份，其哈希值的差值絕不能是單數.該方案與Cash等人的IBE方案[20]相比，其密文更短、更簡潔.另外也可利用基本的格基委托技術，將基本的IBE轉化成HIBE.

4 總結

最初以LLL算法[21]為標志的格基技術是作為一種密碼分析工具展示了其威力，但10年后，格基技術作為一種嶄新的密碼設計平臺而備受關注.如今，格成為最看好的后量子密碼體制之一.這種繁榮正如雙線性配對技術[22]最初也是作為一種密碼分析工具而出現，隨后在密碼設計上大放異彩.因此，格基技術在密碼設計上的應用將會更加豐富多彩.當然，為了使格基密碼體制最終走向實用，還有許多工作要做.一方面，許多格問題的困難性需要進一步的研究；同時，減少格基密碼的密鑰長度、追求更加高效的設計，永遠是值得大力研究的課題；最后，嘗試設計人們期待已久的基于其它數學平臺而未能獲得的密碼方案，也許最能顯示格基密碼的獨特魅力.比如基于格的全同態加密方案的成功設計.[12]

[1]AJTAI M,DWORK C.A public-key cryptosystem with worstcase/average-caseequivalence[C].STOC,1997:284-293.

[2]GOLDREICH O,GOLDWASSER S,HALEVI S.Public-key cryptosystems from lattice reduction problems[J].Advances in cryptology,LNCS1294.Sci.,1997:112-131.

[3]HOFFSTEIN J,PIPHER J,SILVERMAN J H.NTRU:a ring based public key cryptosystem[C].ANTS-III,LNCS 1423,1998:267-288.

[4]REGEV O.On lattices,learning with errors,random linear codes,and cryptography[C].STOC,ACM,2005:84-93.

[5]GENTRY C,PEIKERT C,VAIKUNTANATHAN V.Trapdoors for hard lattices and new cryptographic constructions[C].STOC,ACM,2008:197-206.

[6]PEIKERT C.Public-key cryptosystems from the worst-case shortest vector problem[C].STOC,2009:333-342.

[7]AJTAI M.Generating hard instances of lattice problems[C].STOC,1996,(13):1-32.

[8]REGEV O.New lattice-based cryptographic construction[J].ACM,2004,51(6):899-942.

[9]PEIKERT C,WATERS B.Lossy trapdoor functions and their applications[C].STOC,ACM,2008:187-196.

[10]AGRAWAL S,BONEH D,BOYEN X.Efficient lattice(H)IBE in the standard model[C].EUROCRYPT,2010:553-572.

[11]PEIKERT C.Bonsai trees(or,arboriculture in lattice-based cryptography)[J].Cryptology ePrint Archive,Report 2009:359,http://eprint.iacr.org/.

[12]GENTRY C.Fully homomorphic encryption using ideal lattices[C].STOC,2009:169-178.

[13]PEIKERTC,VAIKUNTANATHANV,WATERSB.Aframework for efficient and composable oblivious transfer[C].CRYPTO,2008:554-571.

[14]BONEHD,CANETTIR,HALEVIS,KATZJ.Chosen-Ciphertext Security from Identity-Based Encryption[J].SIAM Journal on Computing,2006,36(5):915-942.

[15]AKAVIA A,GOLDWASSER S,VAIKUNTANATHAN V.Simul-taneous hardcore bits and cryptography against memory attacks[C].TCC,2009:474-495.

[16]GOLDWASSER S,KALAI Y,PEIKERT C,VAIKUNTANATHAN V.Robustness of the learning with errors assumption[C].ICS,2010.

[17]LYUBASHEVSKY V,PEIKERT C,REGEV O.On Ideal Lattices and Learning with Errors over Rings[C].EUROCRYPT 2010,LNCS 6110,2010:1-23.

[18]STHLEAND D,SREINFELD R.Making NTRU as secure as worst-case problem over ideal lattices[C].EUROCRYPT 2011,Publisher:Springer Berlin Heidelberg,6632:2011:27-47.

[19]PEIKERT C.Bonsai trees(or,arboriculture in lattice-based cryptography)[J].Cryptology ePrint Archive,Report 2009:359,http://eprint.iacr.org.

[20]CASH D,HOFHEINZ D,KILTZ E.How to delegate a lattice basis[J].Cryptology ePrint Archive,Report 2009/351,2009.http://eprint.iacr.org/.

[21]LENSTRA A K,LENSTRA H W,Jr.,LOVSZ L.Factoring polynomials with rational coefficients[J].Math.Ann.,1982,261(4):515-534.

[22]SAKAI R,OHGISHI K,KASAHARA M.Cryptosystem based on pairings[J].SCIS 2001,Oiso,Japan.