張平原 蔣 瀚 蔡 杰 王晨光 鄭志華 徐秋亮

1(山東大學軟件學院 濟南 250101) 2(山東大學數學學院 濟南 250100) 3(山東師范大學信息科學與工程學院 濟南 250358) (pingyuan0802@163．com)

2017-08-31；

2017-09-11

國家自然科學基金項目(61572294)；國家自然科學基金重點項目(61632020)；山東大學基本科研業(yè)務費專項資金項目(2017JC019) This work was supported by the National Natural Science Foundation of China (61572294), the Key Program of National Natural Science Foundation of China (61632020), and the Fundamental Research Funds for Shandong University(2017JC019).

蔣瀚(jianghan@sdu.edu.cn)；徐秋亮(xql@sdu.edu.cn)

格密碼技術近期研究進展

張平原1,2蔣 瀚1蔡 杰1,2王晨光1,2鄭志華3徐秋亮1

1(山東大學軟件學院 濟南 250101)2(山東大學數學學院 濟南 250100)3(山東師范大學信息科學與工程學院 濟南 250358) (pingyuan0802@163．com)

格理論最初是作為一種密碼分析工具被引入到密碼學中的，用于分析背包密碼體制、RSA密碼體制等.在1997年，Ajtai和Dwork第一次構造了一個基于格的密碼體制Ajtai-Dwork，隨后在1998年出現(xiàn)了NTRU密碼體制.當時基于整數分解及離散對數的公鑰密碼體制是主流，格密碼一直沒有得到足夠的重視.直到2009年，Gentry基于格密碼構造了首個全同態(tài)密碼方案，格密碼才得到了廣泛的發(fā)展.2015年，Peikert在“格密碼十年”一文中，對之前格密碼的發(fā)展做了一個很好的總結.同在2015年，美國國家標準和技術研究院(National Institute of Standards and Technology, NIST)發(fā)布了“后量子密碼報告”，報告指出：由于量子計算技術的飛速發(fā)展，現(xiàn)有的公鑰密碼標準在量子計算下將不再安全.同時NIST在全球范圍內展開了后量子密碼算法標準的征集工作.格密碼作為一類經典的抗量子密碼，公認是后量子密碼算法標準最有力的競爭者，近2年得到了飛速的發(fā)展，出現(xiàn)了許多優(yōu)秀的研究成果.從基于格的零知識證明、格加密、格簽名以及格密鑰交換4個方面，對近2年格密碼研究進行了總結，并對格密碼的發(fā)展趨勢進行了展望.

格密碼；基于格的零知識證明；格加密；格簽名；格密鑰交換

格L是n維歐氏空間n中一個離散的加法子群.更直觀地說，一個格L?n是一組基向量b1,b2,…,bn∈n的所有整系數線性組合的集合，也就是}.在格上存在著各種計算困難問題，一些經典的問題如最短向量問題(shortest vector problem, SVP)、最近向量問題(closest vector problem, CVP)以及這些問題的近似版本等.對應地，對這些困難問題存在著相應的近似解法，如LLL算法是最著名的求解近似SVP問題的算法[1].

格代數結構最早是作為一種密碼分析工具被引入密碼學的.早在1982年，Shamir首次利用了格理論對背包公鑰密碼算法進行了攻擊[2]；而在1996年，Coppersmith提出將破解RSA體制轉化成求解格中困難問題[3], 進而利用LLL算法來求解.

利用格來設計密碼體制要歸于Ajtai的工作.在1996年,Ajtai[4]開創(chuàng)性地證明了格中某些困難問題如果在最壞情形(worst-case)下是困難的，那么它在平均情形(average-case)下也是困難的.這個結果表明，除非某種格問題的所有實例都容易解決，否則我們就有可能基于該問題構造安全的密碼方案.因此，格密碼可以提供基于worst-case困難下的安全性證明.1997年，Ajtai和Dwork構造了第一個格密碼體制Ajtai-Dwork[5].隨后出現(xiàn)了一批基于格的密碼體制，其中比較著名的有NTRU密碼體制[6]，該體制對格密碼的后續(xù)發(fā)展產生了深遠影響.

由于基于大整數分解以及離散對數困難問題的密碼體制，如RSA，DSA，ECC等是當時的主流公鑰密碼體制，基于格的密碼體制沒有得到廣泛的關注.直到2009年，Gentry首次給出了基于格的全同態(tài)加密方案的構造[7],促成了格密碼研究的一次熱潮.全同態(tài)加密的概念雖然在1978年就由Rivest等人[8]提出,但30多年一直沒有得到研究進展.Gentry的工作證明了全同態(tài)密碼方案的存在性，同時帶動了格密碼的研究，2009年之后，在格的數學基礎、格上困難問題、格密碼體制的構造等方面出現(xiàn)了大量的工作.對這一期間的工作，也有一些綜述文章進行了歸納總結.王小云等人的綜述[9]主要側重于對格的數學基礎方面；而Peikert的綜述[10]是一篇對截止到2015年格密碼發(fā)展的一篇覆蓋全面、邏輯清晰的工作.

在2015年，美國國家標準技術研究院(NIST)發(fā)布了一份后量子密碼報告[11]，對公鑰密碼算法的換代工作以及后量子子密碼算法研究工作產生了極大的推動作用.事實上，早在1997年，Shor就提出了一種量子算法，可以在多項式時間內解決大整數分解問題[12]，Shor算法的核心就是利用量子計算的性質來求出函數的周期，這種思想對于求解離散對數問題仍然有效.因此，Shor的工作表明，一旦量子計算機被真正制造出來，基于大整數分解問題，以及離散對數問題的密碼體制，包括RSA，ECC等將不再安全.NIST的后量子密碼報告強化了量子計算機出現(xiàn)的預期，同時NIST也開始在全球范圍內開展后量子密碼算法標準的征集工作.

NIST的后量子密碼報告中提到的后量子密碼算法主要有于基于格的密碼(lattice-based crypto-graphy)、基于編碼(code-based cryptosystems)的密碼系統(tǒng)、多變量密碼(multivariate cryptography)以及基于哈希算法的簽名(Hash-based signatures)4種，此外，還有學者基于超奇異橢圓曲線上的同源問題，共軛搜索問題(conjugacy search problem)以及辮群(braid groups)中的相關問題等設計抗量子的密碼系統(tǒng)等.在這些解決方案中，由于基于格可以設計加密、簽名、密鑰交換等各種密碼系統(tǒng)，且具有較可信的安全性，因此格密碼被公認是后量子密碼算法標準最有力的競爭者.近幾年來，格密碼成為密碼學領域最熱門的研究方向之一，出現(xiàn)了大量的研究成果，因此有必要對近年來的成果做一個梳理.

本文按照基于格的零知識證明、格加密、格簽名以及格密鑰交換4個方面，總結了近2年來格密碼的重要研究成果，并對格密碼的研究趨勢做出了展望.

1 格困難問題的算法和計算復雜性

給定一個格L,用λi(L)表示第i個逐次最小長度，即λi定義為以原點為球心，包含i個線性無關格向量的最小球的半徑.

1) 最短向量問題(shortest vector problem, SVP).給定一個格L，找它的一個最短的非零格向量.

4) 判定版本SVP問題(GapSVP).給定一個格L和有理數r，確定是下列哪種情況成立：λ1≤r或者λ1≥γ×r.

5) SIS(small integer solutions)問題.給定矩陣A∈n×mq(m≥n)和實常數v，找一個非零向量u∈m，使得Au=0modq，且.它等價于在模格m:Au=0modq}中找一個向量長度不超過v的非零格向量.

6) LWE(learning with errors)問題.非正式地，LWE問題是指對于多個獨立抽樣(a,〈a,s〉+e)∈nq×q和(a,u)∈nq×q，它們是計算不可區(qū)分的，其中a,s←nq，u←q，e隨機選區(qū)于一個“l(fā)ow-weight”的分.在一定意義下，它是SIS的對偶問題.定義模格Λq(A)={x∈m:x=ATymodq,y∈n}，則LWE問題可以看作模格Λq(A)上的BDD(bounded distance decoding)問題.

為了提高格密碼的效率，密碼學家提出了一類具有額外代數結構的格—理想格[10]，具體地說，f-理想格是對應于環(huán)[X]〈f〉的理想的一類格，其中f是首項系數為1的不可約多項式，如f=xn+1(n是2的冪次方).同樣地，可以定義理想格上的ring-SIS和ring-LWE問題.

1.1格困難問題的求解算法

在經典計算理論下，密碼學家在求解SVP和CVP的算法方面做出了許多貢獻.求解格問題的最著名的方法是 Lenstra，Lenstra和Lovasz 在文獻[3]中提出的LLL算法，該算法在多項式時間內能解決近似因子為2O(n)的SVP問題.盡管LLL算法的理論估計值較差，但在具體實現(xiàn)中卻比理論要好一些，這個問題目前也沒有合理的解釋，該問題也是有待于進一步努力的方向，因為LLL算法的實際運行結果直接關系到格密碼方案的安全參數選取，即影響密碼方案的效率.

之后，許多密碼學家對LLL算法進行了改進，其中包括Schnorr算法[13]、Schnorr和Euchner在1994年提出的BKZ算法[14]和Chen等人的BKZ 2.0算法[15]，但至今為止，這些算法求解近似SVP問題都需要指數時間的復雜度，在多項式時間內僅能解決近似因子為2O(n lblb n/lb n)的SVP問題.因此可以猜想，不存在多項式時間算法能夠解決近似因子為多項式的近似SVP問題，從而我們就可以用格來構造相應的密碼學方案.

在量子計算理論下，自從Shor發(fā)現(xiàn)量子算法以來，傳統(tǒng)的基于整數分解和離散對數的問題困難性受到了極大的威脅.自然地，是否也存在量子算法來求解格中困難問題，但目前為止還沒有發(fā)現(xiàn)明顯優(yōu)于經典算法的量子算法用于求解格中的問題.因此，格密碼在量子計算下仍能夠保證方案的安全性.

1.2格困難問題的計算復雜性

對于一般格中的困難問題的計算復雜性，由于SIS和LWE能夠歸約到GapSVP和SIVP上去.因此，選取足夠小的近似因子，一般格中的困難問題大都是NP-hard的[3].

雖然理想格上的GapSVP和SIVP 的復雜度分析并沒有理論上的證明, 但是在最困難情況下，目前人們并沒有找到環(huán)上相應格問題的多項式時間算法,因此有理由相信這些問題也是足夠困難的(即使在量子算法下).

2 格密碼體制的近期研究進展和主要思想

近2年以來，格密碼體制的設計是密碼學研究的熱點問題之一.我們將分別從基于格的零知識證明、加密、簽名和密鑰交換4個方面來詳細介紹這2年以來的研究進展，并簡單闡述其涉及的主要思想和關鍵技術.

2.1基于格的零知識證明

零知識證明是證明者向驗證者證明某個命題的真?zhèn)?，但不泄露其他的任何信?它可以用到密碼學的很多領域，是格密碼近期研究的熱點問題.

基于格的零知識證明在加密、可驗證加密和群簽名等密碼方案的應用方面，明文知識證明得到越來越多的關注.在明文知識的零知識證明體系中，一個擁有消息m的證明者生成一個密文t=Enc(m)，然后它向驗證證明它知道該消息m=Dec(t).也就是說，向驗證者證明它知道Dec(t)的值，等價于證明密文t是由相應的消息m正確生成的.

1) 在格困難問題中采用Stern[18]的方法來構造，然而，利用該方法構造的方案效率較低.這是由于每輪協(xié)議有23的錯誤概率，因此要達到128比特的安全性，需要重復執(zhí)行192次.

2) 另一個可行的思路是結合Rejection Sampling引理[19]利用Fait-Shamir技術[20].一般情況下，該方法下的協(xié)議每輪有12的錯誤概率，但由于該方法比Stern的有更多的代數結構，因此，近幾年的主要進展都是基于該方法之上的.該方法的主要障礙是：當抽取一些短向量使得對于某個整數c，滿足方程Ae′=tc時，即有Ae′c-1=t.不幸的是，除非c=±1，否則并不能保證e′c-1是一個短向量，這也正是基于格與基于離散對的Fait-Shamir技術的主要不同之處.需要注意的是，該障礙在理想格上仍舊存在.

在2014年亞洲密碼年會上，Benhamouda等人[21]利用ring-LWE成功地將錯誤概率降到12n，其中n是ring-LWE的維數(例如取1 024).因此實際情況下，對于128 b的安全性，只需要執(zhí)行12次協(xié)議.然而，有趣的是該思路的構造只適用于理想格的情況，其背后的主要技術是利用了一個重要的引理，該引理保證了環(huán)[X]〈Xn+1〉上的某些二項式是可逆的，并且它們的逆僅僅有很小的整系數.其具體敘述為:設n是2的次冪，且0

在2016年美密會上,Baum等人[22]提出了一個新的誠實驗證者零知識證明協(xié)議.該協(xié)議的主要思想是構造了一個在整數向量上的同態(tài)單向函數f:r→G，其中G是一個阿貝爾群，運用的關鍵技術之一是在向證明者提取知識時，運用了cut-and-choose rewinding技術；其次作者高效地利用了Lyubashevsky[19]的Rejection Sampling引理，其主要思想是：證明者收到的挑戰(zhàn)值c能夠顯示witness的部分信息時，可以選擇終止協(xié)議.

在2017歐洲密碼年會上，Lyubashebsky等人[16]利用明文知識證明構造了一個可驗證加密方案.其背后的基本思路是：給定矩陣B∈p和線性關系式Bm=umodp，設法生成一個密文和一組“l(fā)ow-weight”證據，使得密文的解密結果是并且滿足關系式

(1)

目前基于格的零知識證明發(fā)展較快，基于LWE或ring-LWE構造高效的，且最好沒有異常終止的零知識證明將會是今后研究的重點內容.

2.2基于格的加密

近幾年來，基于格的加密方案大致沿著2條線.首先是對NTRU加密系統(tǒng)的改造，Stehle和Steinfeld在2011年首次對NTRU進行了成功改進[23]，將方案的語義安全規(guī)約到了ring-LWE問題的困難性假設.在PKC 2017會議上，Yu等人[24]討論了在素分圓環(huán)[X]〈Xn-1+…+X+1〉(其中n是奇素數)上的NTRU加密方案，得到一個標準模型下IND-CPA安全方案，其安全性可規(guī)約到理想格上的最壞情況的困難問題.提出這種環(huán)的研究主要是因為它比2011年Stehle的環(huán)更容易控制而且能抵抗子域攻擊[25]，此外注意到素分圓環(huán)[X]〈Xn-1+…+X+1〉是NTRU環(huán)[X]〈Xn-1〉的一個子環(huán)，因此基于素分圓環(huán)構造加密方案更接近于原始的NTRU加密系統(tǒng).

另外，格加密方案大多應用LWE和ring-LWE問題構建某些特殊加密方案如謂詞加密(predicate encryption)[26]、基于屬性加密(attribute based encryption, ABE)[27-28]和可驗證加密[16]等.例如文獻[26]討論了基于LWE的謂詞加密，然而方案的構造借助于全同態(tài)加密(fully homomorphic encryption, FHE)機制，在分層電路到所有電路中用到了自舉(bootstrap)的方法,方案的效率比較低.對于現(xiàn)有方案的一些改進方向大多都是不改動方案本身，單獨優(yōu)化FHE效率從而提高謂詞加密的效率.最后，2014年亞洲密碼年會Benhamouda等人[17]提出的零知識證明能夠改進基于ring-LWE的加密方案；2017年歐洲密碼年會Lyubashebsky等人[16]利用明文知識證明構造了一個可驗證加密方案等.總之，基于格構造各種特殊的加密方案是格加密的重要發(fā)展趨勢，豐富了格密碼的研究內容.

2.3基于格的數字簽名

近2年格上數字簽名的研究成果，基本是利用Fiat-Shamir變換[15]這種思路來構造高效安全的簽名方案[29-30].這種思路的構造一般要經歷如下過程：困難問題→抗碰撞Hash函數→一次簽名→身份認證協(xié)議→數字簽名.以格上ring-SIS為例，下面我們給出該思路的大致過程.

取環(huán)R=p[X]〈Xn+1〉，定義抗碰撞Hash函數ha(z)=a·z，其中a∈m，z∈Dm?m.首先我們就可以構造一個三輪的身份認證協(xié)議[15]:

1) 證明者在R中隨機選取一個向量y，根據實際情況可以對它的范數適當限制；

2) 證明者向驗證者發(fā)送b=h(y)；

3) 驗證者選取一個隨機的“挑戰(zhàn)”c，并發(fā)送給證明者；

4) 證明者的應答為r=y+zc；

5) 驗證者驗證h(r)=b+h(z)c.

注意到上述協(xié)議如果不加上承諾y，該應答將完全恢復私鑰z，因此承諾y的作用主要是隱藏私鑰.把協(xié)議中的驗證者替換為隨機預言機，利用Fiat-Shamir變換就可以構造出一個數字簽名方案.

需要特別注意的是,通過該思路構造的簽名輸出y+zc要保證不能包含私鑰的任何有用信息，這個問題在基于整數分解和離散對數的簽名中很容易解決，但在基于格的數字簽名中，由于格特殊的代數結構，這是格簽名發(fā)展的主要障礙.一個比較直觀的解決辦法是：相對于zc，我們可以在足夠大的范圍內隨機選取向量y，那么y+zc的值就會以很大的概率在y的范圍隨機分布，如果敵手對y一無所知，那么它就不會獲取私鑰z的任何信息.但是這種解決辦法y的值很大，因此輸出的簽名y+zc的簽名長度就會很長，所以在構造簽名時，該方法很少被利用.除此之外，目前主要的有效的解決途徑主要有2種方法：

1) aborting技術[15].它的主要思想是簽名者可以有選擇性的輸出簽名，以保證簽名不包含私鑰的任何有用信息.具體地講，我們主要運用下面這個論斷：如果我們要計算2個數的和，其中a∈[-A,A],b←[-3A,3A],那么，當且僅當c∈[-2A,2A]時，我們才輸出c=a+b.否則，重新選擇b，直至上述條件成立.在這種情形下，我們就能保證c的輸出分布與a是無關的.利用這個思想，當有選擇性的輸出簽名時，就可以保證簽名的輸出分布與私鑰是無關的.

2) Rejection Sampling引理[16].為了便于理解，我們給出該引理的具體內容：設f:n→是一個概率分布.給定一個子集V?n,令h:V→定義在V上的概率分布，gv:n→是一個的概率分布族，使得幾乎對于所有的v∈V，都存在一個上界M∈使得：

Pr[Mgv(z)≥f(z);z←f]≥1-negl(λ),

則下面2個分布的統(tǒng)計距離可忽略不計：

也就是說，給定一個概率密度函數f，找另一個密度函數g，滿足f(z)≤Mg(z).然后分別以函數f和g進行抽樣并以一定概率輸出，以保證f和g的輸出分布的統(tǒng)計距離是可忽略的.在簽名方案的構造過程中，實際上找函數g的過程就是構造簽名的過程.

近幾年來，格上數字簽名主要以上述2種方法為基礎來構造高效安全的簽名方案.在CT-RSA 2014 上，Bai和Galbraith[29]在生成簽名的過程中，先用rounding算子對承諾值v的比特取高位，也就是扔掉一些最不重要的比特位，然后再取它與簽名消息μ的Hash值c，然后根據上述方法即可得到一個基于LWE的短簽名方案.注意：為了保證承值v扔掉一部分值后仍能夠驗證成功，需要控制好方案中一些參數的取值.

在2016亞洲密碼年會上，Lyubashevsky[30]利用Fiat-Shamir變換基于所有環(huán)q[X]〈f〉的ring-SIS問題構造了一個高效的簽名方案，這里僅僅對f的次數進行了較弱的限制.它的主要貢獻是：之前的文章在利用理想格構造數字簽名時，往往用一些特殊的環(huán)，如NTRU環(huán)[X]〈Xn-1〉和素分圓環(huán)[X]〈Xn-1+…+X+1〉.目前為止，雖然還沒有對這種環(huán)的worst-case困難問題實質有效的攻擊，但是，文獻[31]利用某些特殊環(huán)的代數結構，解決了這些環(huán)的一些其他困難問題，Cramer等人[31]在量子計算下構造了一個多項式時間算法，該算法能夠解決分圓環(huán)中主理想的近似因子為最短向量問題.而文獻[30]在很大程度上放寬了對f的限制，這里僅僅要求函數f的次數有一個合理的上界，這在一定程度上增加了方案的安全性.

總之，目前格簽名的密鑰和簽名長度有了進一步的縮短.但是，構造高效的格簽名的思路比較單一，如何豐富格簽名的構造將會是一個有趣的方向.另外，相比較于傳統(tǒng)的簽名方案，格簽名的簽名長度還有待于縮短，這也是格簽名進一步研究的方向.

2.4基于格的密鑰交換

對于基于格的密鑰交換協(xié)議的構造，近幾年出現(xiàn)許多優(yōu)秀成果，如文獻[32-38].其思路基本是根據Diffie-Hellman密鑰交換協(xié)議的思想，直接由LWE問題直接構造.其關鍵問題一般在于金正中和趙運磊[32]首次提出的密鑰共識，也就是說，它能基于交換雙方持有的近似值達成共識.除了文獻[32]中的一般構造算法，一種思路是Ding等人[33]提出的robust extractor.更具體地說，robust extractor是這樣的一個確定性算法E，它滿足對于任意x,y∈q，如果x-y是偶數，且其絕對值足夠小，那么E(x,σ)=E(y,σ)，其中σ∈{0,1}.

另一個較為常用的思想是Peikert[34]在2014年提出的Reconciliation技術.由于后續(xù)的密鑰交換協(xié)議基本都是建立在Peikert的Reconciliation技術基礎之上，下面結合其密鑰封裝機制的基本構造(如圖1所示)，簡述其基本思想.

AliceBobKEM．Gen(a)：s，e←χb=as+eKEM．Decaps(s，(u，v′))：μ=rec(2us，v′)b→u，v′← KEM．Encaps(a，b)：s′，e′，e″←χu=as′+e′v=bs′+e″ v←dbl(v)v′=〈 v〉2μ=[ v]2

Fig. 1 Peikert’s key-encapsulation mechanism圖1 Peikert密鑰封裝機制

向量a隨機選取于環(huán)q，其中對于Alice，環(huán)元素是us=ass′+e′s，對于Bob，則為v=bs′+e″=ass′+es′+e″.在不泄露雙方私鑰的情況下，為了保證得到完全相同的分擔密鑰，Peikert定義〈v〉2對于隨機選取的定義隨機函數dbl(v)其中的概率為，分別取和的概率均為.令則調節(jié)函數定義為

在CCS 2016大會上，Bos等人[36]基于Peikert的調節(jié)機制給出了一個新的、較實用的密鑰交換協(xié)議Frodo.與之前效率較好的協(xié)議相比，該方案的安全性基于困難性更好的LWE問題.協(xié)議的構造主要從2個方面進行改進：1)在不增加高斯抽樣維數的前提下，作者給出了抽樣效率更高的由離散概率密度函數構成的擾動分布；2)相比于Peikert的密鑰封裝機制，作者構造了一個更一般的調解機制，即對每個約定允許提取更多的分擔比特.盡管它以增加了調解失敗概率為代價，但是概率的增加足夠小，并不會影響到實際的應用.正如文獻[36]所述，為了使協(xié)議達到足夠的安全程度，需要滿足固定關系式m×n×B≥256,其中m,n是LWE問題的維數，B是上述允許提取的分擔比特值.因此，當B比較大時，反過來可以降低LWE矩陣的維數.如此不僅能有效地減小帶寬，而且能有效地避免某些預計算攻擊，例如CCS 15會議[38]上提出的針對Diffie-Hellman交換協(xié)議的Logjam攻擊，實際上這種攻擊對格上的密鑰交換協(xié)議的安全性更具有毀滅性[35].

3 結束語

本文簡單介紹了格困難問題的求解和計算復雜性的基本結論，并對近期格密碼的發(fā)展狀況進行簡單總結.雖然格困難問題在密碼體制的設計和安全性方面有著很大的潛力，但仍有許多問題還不明朗，有待于密碼學家進一步去研究、驗證.如關系到密碼方案參數選取的LLL算法在具體實現(xiàn)中卻比理論結果要好，這個問題目前也沒有合理的解釋.此外，理想格上的問題應該比普通格上的相應問題更加簡單，雖然在最困難情況下，目前人們并沒有找到環(huán)上相應格問題的多項式時間算法，但是理想格上的如GapSVP和SIVP問題的復雜度分析并沒有理論上的證明.因此，這些都是密碼學家進一步努力的方向.

在格密碼體制的設計方面，格密碼在安全性方面有著很大的潛力，但在效率和實用性方面，它與目前傳統(tǒng)的較實用的密碼方案還有很大的差距，格密碼的研究歷程還有很長的路要走.例如簽名長度過大一直就是格簽名實例化的一個主要障礙，密碼學家為此做了很多努力，而基于理想格的簽名方案就指明了一個可行性的方向.

總之，格密碼已經成為當前密碼學研究的熱點，無論從理論還是實用價值方面，格密碼都有很大的潛力，但是它仍需要進一步完善和發(fā)展.

[1] Lenstra A K, Lenstra H W, Lovász L. Factoring polynomials with rational coefficients[J]. Mathematische Annalen, 1982, 261(4): 515-534

[2] Shamir A. A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem[J]. IEEE Trans on Information Theory, 1984, 30(5): 699-704

[3] Coppersmith D. Finding a small root of a univariate modular equation[G] //LNCS 1070: Proc of EUROCRYPT 96. Berlin: Springer, 1996: 155-165

[4] Ajtai M. Generating hard instances of lattice problems[G] //Proc of ACM Symp on Theory of Computing 1996. New York: ACM, 1996: 99-108

[5] Ajtai M, Dwork C. A public-key cryptosystem with worst-case/ average-case equivalence[G] //Proc of ACM Symp on Theory of Computing 1997. New York: ACM, 1997: 284-293

[6] Hoffstein J, Pipher J, Silverman J H. NTRU: A ring-based public key cryptosystem[G] //LNCS 1423: Proc of Int Algorithmic Number Theory Symp. Berlin: Springer, 1998: 267-288

[7] Gentry C. Fully homomorphic encryption using ideal lattices[C] //Proc of ACM Symp on Theory of Computing 2009. New York: ACM, 2009: 169-178

[8] Rivest R L, Adleman L, Dertouzos M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978, 4(11): 169-180

[9] Wang Xiaoyun, Liu Mingjie. Survey of lattice-based cryptography[J]. Journal of Cryptologic Research, 2014, 1(1): 13-27 (in Chinese)

(王小云, 劉明潔. 格密碼學研究[J]. 密碼學報, 2014, 1(1): 13-27)

[10] Peikert C. A decade of lattice cryptography[J]. Foundations and Trends in Theoretical Computer Science, 2016, 10(4): 283-424

[11] Chen L, Jordan S, et al. Report on Post-Quantum Cryptography[M]. Gaithersburg: US Department of Commerce, National Institute of Standards and Technology, 2016

[12] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484-1509

[13] Schnorr C P. A hierarchy of polynomial time lattice basis reduction algorithms[J]. Theoretical Computer Science, 1987, 53(2/3): 201-224

[14] Schnorr C P, Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems[J]. Mathematical Programming, 1994, 66(1/2/3): 181-199

[15] Chen Yuanmi, Nguyen P Q. Bkz 2.0: Better lattice security estimates[G] //LNCS 7073: Proc of ASIACRYPT 2011. Berlin: Springer, 2011: 1-20

[16] Lyubashevsky V, Neven G. One-shot verifiable encryption from lattices[G] //LNCS 10210: Proc of EUROCRYPT 2017. Berlin: Springer, 2017: 293-323

[17] Benhamouda F, Camenisch J, Krenn S, et al. Better zero-knowledge proofs for lattice encryption and their application to group signatures[G] //LNCS 8873: Proc of ASIACRYPT 2014. Berlin: Springer, 2014: 551-572

[18] Stern J. A new identification scheme based on syndrome decoding[G] //LNCS 773: Proc of CRYPTO 1993. Berlin: Springer, 1993: 13-21

[19] Lyubashevsky V. Lattice signatures without trapdoors[G] //LNCS 7237: Proc of EUROCRYPT 2012. Berlin; Spring, 2012: 738-755

[20] Lyubashevsky V. Fiat-shamir with aborts: Applications to lattice and factoring-based signatures[G] //LNCS 5912: Proc of ASIACRYPT 2009. Berlin: Springer, 2009: 598-616

[21] Benhamouda F, Camenisch J, Krenn S, et al. Better zero-knowledge proofs for lattice encryption and their application to group signatures[G] //LNCS 8873: Proc of ASIACRYPT 2014. Berlin: Springer, 2014: 551-572

[22] Baum C, Damgrd I, Larsen K G, et al. How to prove knowledge of small secrets[G] //LNCS 9816: Proc of CRYPTO 2016. Berlin: Springer, 2016: 478-498

[23] Stehlé D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices[G] //LNCS 6632: Proc of EUROCRYPT 2011. Berlin: Springer, 2011: 27-47

[24] Yu Yang, Xu Guangwu, Wang Xiaoyun. Provably secure NTRU instances over prime cyclotomic rings[G] //LNCS 10174: Public - Key Cryptography 2017. Berlin: Springer, 2017: 409-434

[25] Albrecht M, Bai S, Ducas L. A subfield lattice attack on overstretched NTRU assumptions[G] //LNCS 9814: Proc of CRYPTO 2016. Berlin: Springer, 2016: 153-178

[26] Gorbunov S, Vaikuntanathan V, Wee H. Predicate encryption for circuits from LWE[G] //LNCS 9216: Proc of CRYPTO 2015. Berlin: Springer, 2015: 503-523

[27] Gorbunov S, Vaikuntanathan V, Wee H. Attribute-based encryption for circuits[C] //Proc of ACM Symp on Theory of Computing 2013. New York: ACM, 2013: 545-554

[28] Boneh D, Gentry C, Gorbunov S, et al. Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits[G] //LNCS 8841: Proc of EUROCRYPT 2014. Berlin: Springer, 2014: 533-556

[29] Bai S, Galbraith S D. An improved compression technique for signatures based on learning with errors[G] //LNCS 8366: Proc of Topics in Cryptology CT-RSA 2014. Berlin: Springer, 2014: 28-47

[30] Lyubashevsky V. Digital signatures based on the hardness of ideal lattice problems in all rings[G] //LNCS 10032: Proc of ASIACRYPT 2016. Berlin: Springer, 2016: 196-214

[31] Cramer R, Ducas R, Peikert C, et al. Recovering short generators of principal ideals in cyclotomic rings[G] //LNCS 9666: Proc of EUROCRYPT 2016. Berlin: Springer, 2016: 559-585

[32] Jin Zhenzhong, Zhao Yunlei. Optimal key consensus in presence of noise[J]. ArXiv Preprint.ArXiv:1611.06150, 2016 [2017-08-15]. http://arxiv.org/pdf/1611.06150.pdf

[33] Ding Jintai, Xie Xiang, Lin Xiaodong. A simple provably secure key exchange scheme based on the learning with errors problem[J]. IACR Cryptology Eprint Archive, 2012 [2017-08-15]. http://ai2-s2-pdfs.s3.amazonaws.com/b1e7/faec59a9bdd70e75f9d15496cf27916ce060.pdf

[34] Peikert C. Lattice cryptography for the Internet[G] //LNCS 8772: Post-Quantum Cryptography 2014. Berlin: Springer, 2014: 197-219

[35] Alkim E, Ducas L, P?ppelmann T, et al. Post-quantum key exchange—A new hope[C] //Proc of the 25th USENIX Security Symp. Berkeley, CA: USENIX Association, 2016: 327-343

[36] Bos J, Costello C, et al. Frodo: Take off the ring! practical, quantum secure key exchange from LWE[C] //Proc of Conf on Computer and Communications Security 2016. New York: ACM, 2016: 1006-1018

[37] Zhang Jiang, Zhang Zhenfeng, Ding Jintai, et al. Authenticated key exchange from ideal lattices[G] //LNCS 9057: Proc of EUROCRYPT 2015. Berlin: Springer, 2015: 719-751

[38] Adrian D, Bhargavan K, Durumeric Z. Imperfect forward secrecy: How Diffie-Hellman fails in practice[C] //Proc of Conf on Computer and Communications Security 2015. New York: ACM, 2015: 5-17ZhangPingyuan, born in 1988. PhD candidate. His main research interests include public key cryptography, especially lattice-based cryptography.

RecentAdvancesinLattice-BasedCryptography

Zhang Pingyuan1,2, Jiang Han1, Cai Jie1,2, Wang Chenguang1,2, Zheng Zhihua3, and Xu Qiuliang1

1(CollegeofSoftware,ShandongUniversity,Jinan250101)2(SchoolofMathematics,ShandongUniversity,Jinan250100)3(CollegeofInformationScienceandEngineering,ShandongNormalUniversity,Jinan250358)

Lattice theory was first introduced to cryptography as a cryptanalysis tool to analyze knapsack and RSA cryptosystem. In 1997, Ajtai and Dwork constructed the first lattice cryptography: Ajtai-Dwork; and then in 1998, NTRU is appeared. Since factorization and discrete logarithm based cryptography was the mainstream, lattice-based cryptography has not

enough attention. Until 2009, Gentry constructed the first fully homomorphic encryption, which led to a wide of development of lattice cryptography. In 2015, Peikert made a summary of the development of lattice cryptography in “A decade of lattice cryptography”. Also in 2015, NIST released “Report on post-quantum cryptography”. According to the report, due to the rapid development of quantum computation technology, the existing standard of public key cryptography in quantum computing will be no longer safe. At the same time, NIST has launched a worldwide collection of quantum cryptography algorithms. As a classic quantum-resistant cryptography, lattice-based cryptography is known as the most promising competitor. Therefore, lattice cryptography has attracted much attention in recent years, and a lot of excellent results have been appeared. In this paper, we summarize the main results of lattice cryptography for the past two years, which consist of zero-knowledge proofs, encryption, signature and key exchange; and at last, we outlook the development trend of lattice-based cryptography.

lattice-based cryptography; lattice-based zero-knowledge proof; lattice-based encryption; lattice-based signature; lattice-based key exchange

TP309

JiangHan, born in 1974. Lecturer of Shandong University since 2009. His main research interests include cryptography and infor-mation security, especially secure multi-party computation.

CaiJie, born in 1986. PHD candidate in Shandong University. Her main research interests include cryptography, especially lattice-based cryptographic protocols.

WangChenguang, born in 1982. PhD candidate in Shandong University and lecturer in Jining University. His main research interests include cryptography, complex analysis and mathematical modeling.

ZhengZhihua, born in 1962. Associate professor in Shandong Normal University. Her main research interests include cryptographic algorithms and protocols.

XuQiuliang, born in 1960. Professor and PhD supervisor in Shandong University. His main interests include public key cryptography and multi-party secure computation.