楊楠　田有亮

摘要：在后量子密碼時(shí)代，如何設(shè)計(jì)可以抵抗量子計(jì)算攻擊的密碼體制是后量子密碼的主要任務(wù)，基于格的公鑰密碼體制被認(rèn)為是最有可能抵御量子威脅的密碼體制之一，基于容錯(cuò)學(xué)習(xí)（learning with errors， LWE）問題構(gòu)建的密碼體制是基于格密碼發(fā)展實(shí)用前景最好的兩種構(gòu)建方案之一。從基于LWE問題構(gòu)建基于屬性加密方案、全同態(tài)加密方案、函數(shù)加密方案、密鑰交換協(xié)議、數(shù)字簽名方案等5個(gè)方面，對(duì)基于LWE問題構(gòu)造的密碼方案和當(dāng)前研究面臨的挑戰(zhàn)進(jìn)行了總結(jié)。

關(guān)鍵詞：容錯(cuò)學(xué)習(xí);基于屬性加密;全同態(tài)加密;函數(shù)加密;密鑰交換;數(shù)字簽名

中圖分類號(hào)：TP309.7文獻(xiàn)標(biāo)志碼：A

格理論作為幾何學(xué)中的經(jīng)典理論，其研究可以追溯到17世紀(jì)KEPLER猜想，德國數(shù)學(xué)家GAUSS通過引入格的概念證明了猜想。MINKOWSKI、HERMITE、BOURGAIN、HLAWKA等的研究促進(jìn)格理論的進(jìn)一步發(fā)展，在組合優(yōu)化、信息安全等領(lǐng)域有著廣泛的應(yīng)用。最初，格理論作為密碼分析工具被引入到密碼學(xué)中，用于分析RSA、MH-knapsack等密碼體制的安全性。

1996年， AJTAI[1]取得開創(chuàng)性成果，構(gòu)造出整數(shù)格中的隨機(jī)格類，第一次將任意格上一類困難問題的最壞情況問題歸約到求解隨機(jī)格類的平均困難情況上，使得基于格問題構(gòu)造可證明安全性的密碼體制成為可能。AJTAI等[2]在1997年的計(jì)算理論研討會(huì)（symposium on theory of computing， STOC）上，基于格上唯一最短向量問題（unique shortest vector problem， uSVP）的困難性，構(gòu)造出第一個(gè)基于格的公鑰密碼體制。隨后，基于格的公鑰密碼體制不斷出現(xiàn)，但存在密鑰尺寸過大、效率不高或缺乏安全性證明的問題。

2005年，REGEV[3]提出容錯(cuò)學(xué)習(xí)（learning with errors， LWE）問題，利用一個(gè)量子多項(xiàng)式規(guī)約算法，將求解平均困難情況的LWE問題歸約到求解任意的n維格上最壞情況困難問題判定型近似最短向量問題（decisional approximate shortest vector problem， GapSVP）、近似最短獨(dú)立向量問題（approximate shortest independent vectors problem， SIVP）上，從而將任何求解LWE的算法（無論是經(jīng)典算法還是量子算法）轉(zhuǎn)化為求解格問題的量子算法。目前除了一般的量子加速外，還沒有已知求解GapSVP或SIVP的量子算法顯著優(yōu)于經(jīng)典算法。

LWE問題有兩個(gè)主要的版本：搜索型LWE（Search-LWE）問題和判定型LWE （Decision-LWE）問題。通過選擇恰當(dāng)?shù)膮?shù)，這兩個(gè)版本是等價(jià)的。在利用LWE問題構(gòu)造密碼方案時(shí)，多數(shù)使用判定型LWE問題。文獻(xiàn)[3]構(gòu)造出第一個(gè)基于LWE問題的公鑰加密方案，其加密過程是對(duì)明文逐位加密，每次只能加密1 bit，效率較低。為進(jìn)一步提高效率，在不增加密文大小的情況下，KAWACHI等[4]提出基于LWE問題的多比特公鑰加密方案。PEIKERT等[5]給出更大明文空間上的基于LWE問題的有損陷門函數(shù)（lossy trapdoor functions， lossy TDFs），隨后 MICCIANICO等[6]對(duì)該方案進(jìn)行優(yōu)化。

由于LWE 使用中固有的二次開銷，造成上述方案的效率相當(dāng)?shù)?。為解決這一問題，2010年，LYUBASHEVSKY等[7]構(gòu)造出LWE的一個(gè)代數(shù)變體環(huán)-LWE （Ring-LWE， R-LWE）。該方案相對(duì)于LWE方案的主要優(yōu)勢(shì)是減少密鑰尺寸，降低開銷。R-LWE問題的困難性可以歸約到任意理想格上的近似最短向量問題（approximate shortest vector problem， SVPγ）上。與LWE問題類似，R-LWE問題有兩個(gè)主要的版本：搜索型R-LWE（Search-R-LWE）問題和判定型R-LWE（Decision-R-LWE）問題。

1994年，SHOR[8]提出著名的Shor量子算法，可以在多項(xiàng)式時(shí)間內(nèi)高效解決大整數(shù)分解和離散對(duì)數(shù)問題，對(duì)當(dāng)時(shí)主流公鑰密碼體制構(gòu)成潛在威脅。設(shè)計(jì)可以抵抗量子計(jì)算攻擊的密碼體制是后量子密碼的主要任務(wù)，基于格的公鑰密碼被認(rèn)為是最有可能抵御量子計(jì)算威脅的密碼體制。在美國國家標(biāo)準(zhǔn)與技術(shù)研究院（national institute of standards and technology， NIST）公布的第三輪后量子密碼系統(tǒng)的7個(gè)提案中，基于格的提案有5個(gè)?；贚WE問題構(gòu)建的密碼體制是基于格密碼發(fā)展實(shí)用前景最好的兩種構(gòu)建方案之一。

本文從基于LWE問題構(gòu)建基于屬性加密方案、全同態(tài)加密方案、函數(shù)加密方案、密鑰交換協(xié)議、數(shù)字簽名等5個(gè)方面，總結(jié)基于LWE問題構(gòu)建的密碼體制取得的重要研究成果。

1 基本知識(shí)

1.1 格

定義1格（lattice）。格是R中n個(gè)線性無關(guān)的向量a，…，a的整數(shù)系數(shù)線性組合的全體，記為

L=L（a，…，a）

={xa+…+xa|x∈Z，i∈[n]}

其中：向量組a，…，a是格L的一個(gè)基;m是格L的維數(shù);n是格L的秩;常用的格是整數(shù)格。

1.2 格中困難問題

最短向量問題（shortest vector problem， SVP）。對(duì)于給定的一個(gè)格，找到它的最短非零格向量。

近似最短向量問題（SVP）。L是一個(gè)m維格，實(shí)數(shù)d>1，找到一個(gè)格向量v∈L，使得‖v‖≤dλ1（L）。

γ-唯一最短向量問題（uSVP）。給定一個(gè)格L，滿足λ（L）>γλ（L），找到格中最短非零格向量。

判定型近似最短向量問題（GapSVP）。L是一個(gè)m維格，實(shí)數(shù)d>0，若λ（L）≤d，則yes，若λ（L）>γ（n）d，則no。

近似最短獨(dú)立向量問題（SIVPγ）。L是一個(gè)秩為n的格，找到n個(gè)線性無關(guān)的格向量，使得向量的長(zhǎng)度不超過γ（n）λ（L）。

1.3 LWE問題

定義2LWE分布（LWE distribution）。在Z中均勻隨機(jī)選擇一個(gè)秘密s，Z×Z上的LWE分布A滿足：均勻隨機(jī)選取a∈Z，從Z上的離散高斯分布χ中抽樣得到e，輸出（a，b=[a，s]+e mod q）。

定義3搜索型容錯(cuò)學(xué)習(xí)問題。從Z中均勻隨機(jī)抽取一個(gè)秘密s，給定m個(gè)從LWE分布A中獨(dú)立抽樣的隨機(jī)對(duì)（a，b）∈Z×Z（隨機(jī)對(duì)中的秘密均為s），求解出s。

定義4判定型容錯(cuò)學(xué)習(xí)問題。給定m個(gè)獨(dú)立抽樣（a，b）∈Z×Z，其中每一個(gè)抽樣的分布要么服從A（服從A分布的所有抽樣，其均勻選擇的秘密固定為s）分布，要么服從Z×Z上均勻分布，判定型容錯(cuò)學(xué)習(xí)問題就是以不可忽略的概率區(qū)分出每一個(gè)抽樣滿足哪一種分布。

1.4 R-LWE問題

定義5R-LWE分布（R-LWE distribution）。令R=Z[x]/（x+1），其中n是2的方冪，R=Z[x]/（x+1），從R中隨機(jī)選取一個(gè)稱為秘密的元素s，χ是R上的一個(gè)分布，R×R上的R-LWE分布A滿足：隨機(jī)均勻選取a∈Rq，從R上的分布χ中抽樣得到e，輸出（a，b=s·a+e mod q）。

定義6搜索型環(huán)容錯(cuò)學(xué)習(xí)（search-R-LWE）問題。從R中均勻隨機(jī)抽取一個(gè)秘密s，給定m個(gè)從R-LWE分布A中獨(dú)立抽樣的隨機(jī)對(duì)（a，b）∈R×R（隨機(jī)對(duì)中的秘密均為s），求解出s。

定義7判定型環(huán)容錯(cuò)學(xué)習(xí)（decision-R-LWE）問題。給定m個(gè)獨(dú)立抽樣（a，b）∈R×R，其中每一個(gè)抽樣的分布要么服從A（服從A分布的所有抽樣，其均勻選擇的秘密固定為s）分布，要么服從R×R上的均勻分布，判定型環(huán)容錯(cuò)學(xué)習(xí)問題就是以不可忽略的概率區(qū)分出每一個(gè)抽樣滿足哪一種分布。2基于LWE問題構(gòu)造密碼方案

2.1 基于LWE問題構(gòu)造基于屬性加密方案

基于屬性加密（attribute-based encryption， ABE）方案是公鑰加密方案的擴(kuò)展， 提供了高效而簡(jiǎn)單的數(shù)據(jù)共享機(jī)制，支持細(xì)粒度的訪問控制。自SAHAI等[9]在2005年歐密會(huì)上提出基于模糊身份加密方案，引入ABE思想后，ABE已成為一種具有應(yīng)用價(jià)值的密碼原語，由此產(chǎn)生了一系列在效率、表達(dá)性、安全性和基本假設(shè)之間實(shí)現(xiàn)各種權(quán)衡的工作[10-19]。

前面提到的大多數(shù)工作的安全性與基于雙線性映射的假設(shè)有關(guān)，鑒于已知量子計(jì)算對(duì)基于群結(jié)構(gòu)的攻擊，構(gòu)建基于格的ABE方案，實(shí)現(xiàn)量子計(jì)算攻擊下的安全性尤為重要。

在AJTAI[1，20]、REGEV[3]等開創(chuàng)性工作的基礎(chǔ)上，第一個(gè)基于格的基于身份加密 （identity-based encryption， IBE）方案被構(gòu)造出來[21-23]，其在選擇模型下是安全的;AGRAWAL等[24]提出一個(gè)具有全安全（full security）的結(jié)構(gòu)。

此后，許多學(xué)者對(duì)基于LWE問題的ABE方案進(jìn)行了研究。BOYEN[25]利用格上的LWE問題，通過建立一種新的適合處理復(fù)雜訪問策略的格操作框架，構(gòu)造出一個(gè)基于密鑰策略的屬性加密（key policy-ABE，KP-ABE）的方案，在標(biāo)準(zhǔn)模型下是安全的。GORBUNOV等[26]構(gòu)造了一個(gè)新的、高效的，用于短密鑰分支程序P的ABE方案，其中短密鑰的長(zhǎng)度是∣P∣+poly（λ），λ是安全參數(shù);在具有多項(xiàng)式近似因子的LWE假設(shè)下，具有選擇性安全（selectively-secure）。BRAKERSKI等[27]針對(duì)部分ABE方案中存在屬性的長(zhǎng)度（表示為二進(jìn)制字符串）必須在初始化期間確定的問題，通過構(gòu)造一個(gè)基于LWE的ABE方案，使得公共參數(shù)的大小在安全參數(shù)中是一個(gè)固定的多項(xiàng)式，利用這些固定長(zhǎng)度參數(shù)，對(duì)任意長(zhǎng)度的屬性進(jìn)行加密;同時(shí)，安全性滿足半選擇性安全（semi-selectively secure），即敵手可以在得到公共參數(shù)之后，但在任何解密密鑰之前選擇挑戰(zhàn)屬性，而在此之前，基于LWE問題的結(jié)構(gòu)只能實(shí)現(xiàn)選擇性安全。AGRAWAL等[28]基于LWE假設(shè)，構(gòu)造了第一個(gè)基于對(duì)稱密鑰屬性用于非確定性有限自動(dòng)機(jī)（nondeterministic finite automata， NFA）加密方案。方案支持長(zhǎng)度無界輸入和長(zhǎng)度無界機(jī)器，即在方案中，私鑰與一個(gè)長(zhǎng)度無界的NFA M有關(guān)，密文與一個(gè)元組（x， m）有關(guān)，x是長(zhǎng)度無界的公開屬性，m是秘密消息比特，解密恢復(fù)m，當(dāng)且僅當(dāng) M（x）=1。TSABARY[29]首次為函數(shù)類t-合取范式（t-conjunctive normal form，t-CNF）構(gòu)造了一個(gè)基于D-LWE、基于密文策略的屬性加密 （ciphertext policy-ABE，CP-ABE）方案，其構(gòu)造支持無限規(guī)模的函數(shù)，即每個(gè)函數(shù)由多項(xiàng)式個(gè)子句組成。這些函數(shù)類包括NP-驗(yàn)證策略（NP-verification policies）、比特固定策略（bit-fixing policies）和t-閾值策略（t-threshold policies）。

2.2 基于LWE問題構(gòu)造全同態(tài)加密方案

全同態(tài)加密（fully homomorphic encryption， FHE）思想，由RIVEST等[30]在1978年提出，允許在不知道私鑰的情況下，對(duì)密文進(jìn)行無限量的運(yùn)算，可以間接地對(duì)原文進(jìn)行相應(yīng)操作。這一開創(chuàng)性的構(gòu)想一經(jīng)提出，整個(gè)學(xué)術(shù)界為之轟動(dòng)，但經(jīng)過幾十年的探索，一直未能找到既滿足全同態(tài)加密的所有條件，又容易證明安全性的方案。

2009年，GENTRY[31]基于理想格提出第一個(gè)FHE方案。在方案中，作者通過自舉（Bootstrapping）密文處理方法，將噪音接近臨界值的密文轉(zhuǎn)變?yōu)樵胍糨^低的密文，從而實(shí)現(xiàn)全同態(tài)加密，但是該方案存在效率低、密鑰尺寸大的問題。這是一個(gè)概念上和實(shí)踐上都不實(shí)用的方案。該方案被稱為第一代FHE方案。

在2011年FOCS（Annual Symposium on Foundations of Computer Science）會(huì)議上，BRAKERSKI等[32]不同于之前的方案（依賴于各種環(huán)中的理想相關(guān)的復(fù)雜性假設(shè)），基于LWE問題，采用重線性技術(shù)（re-linearization technique）控制密文的維數(shù)，利用維數(shù)-模數(shù)約減（dimension-modulus reduction）技術(shù)，避開稀疏子集和假設(shè)（sparse subset-sum assumption），減少了計(jì)算復(fù)雜性，構(gòu)造出第一個(gè)可自舉的基于LWE問題的有限同態(tài)加密方案。在2012年ITCS（Innovations in Theoretical Computer Science Conference）會(huì)議上，BRAKERSKI等[33]基于R-LWE問題，采用密鑰轉(zhuǎn)換技術(shù)（key-switching technique）控制密文維數(shù)膨脹問題，用模數(shù)轉(zhuǎn)換技術(shù)（modulus-switching technique）降低密文運(yùn)算中的噪聲規(guī)模增長(zhǎng)問題，實(shí)現(xiàn)無需自舉就可以做到多項(xiàng)式深度的同態(tài)運(yùn)算。但上述兩個(gè)同態(tài)加密方案的密文用向量表示，通過向量的張量積進(jìn)行密文同態(tài)乘法運(yùn)算會(huì)導(dǎo)致密文的維數(shù)急劇膨脹。上述兩方案被稱為第二代FHE方案。

在2013年的歐密會(huì)上，基于LWE問題，GENTRY等[34]借助近似特征向量（approximate eigenvector）方法，構(gòu)造了一個(gè)FHE方案，簡(jiǎn)稱GSW13方案。相對(duì)之前的方案，GSW13方案中密文由一個(gè)矩陣構(gòu)成，多數(shù)情況下，同態(tài)運(yùn)算的加法和乘法是矩陣的加法和乘法，因此該方案漸進(jìn)性更快，避免了密文維數(shù)膨脹問題，同時(shí)，不需要密鑰轉(zhuǎn)換技術(shù)和模數(shù)轉(zhuǎn)換技術(shù)。相對(duì)于文獻(xiàn)[32-33]中的BV11方案和BGV12方案，GSW13方案在進(jìn)行同態(tài)加密運(yùn)算時(shí)，不需要獲得用戶的求解密鑰（evaluation key），求值器（evaluator）可以在知道一些基本參數(shù)，不知道用戶公鑰的情況下進(jìn)行同態(tài)運(yùn)算。由于需要生成矩陣密文，GSW13方案需要較大的存儲(chǔ)空間。該方案被稱為第三代FHE方案。

ALPERIN-SHERIFF等[35]介紹了構(gòu)造FHE的新方法，避免文獻(xiàn)[36]中因使用Barrington轉(zhuǎn)換帶來的巨大開銷。文獻(xiàn)[35]把解密看作一個(gè)算術(shù)電路，解密中的內(nèi)積可以用一組循環(huán)排列計(jì)算;其利用這一特性，構(gòu)造了一個(gè)自舉程序，該程序比文獻(xiàn)[36]的方案更快地更新密文。HIROMASA等[37]在GSW13加密方案中提出了一種加密矩陣技術(shù)，使用這種技術(shù)來優(yōu)化文獻(xiàn)[36]的自舉方案。GSW13的后續(xù)工作主要是構(gòu)建基于R-LWE的方案[38-40]。

多密鑰全同態(tài)加密（multi-key full homomorphic encryption， MKFHE）可以對(duì)不同公鑰（用戶）下加密的數(shù)據(jù)進(jìn)行任意操作，最終的密文可以由所有相關(guān)用戶共同解密。因此，MKFHE在安全多方計(jì)算（security multi-party computation， MPC）方面具有天然的優(yōu)勢(shì)和應(yīng)用價(jià)值。2012年，LPEZ-ALT等[41]基于NTRU（number theory research unit）密碼體制，提出了第一個(gè)MKFHE方案，但該方案的安全性基于多項(xiàng)式環(huán)上的非標(biāo)準(zhǔn)假設(shè)。在2015年的歐密會(huì)上，CLEAR等[42]構(gòu)造出第一個(gè)基于LWE問題的GSW-多密鑰全同態(tài)加密方案，其安全性可以歸約到理想格上最壞情況困難問題上。

2.3 基于LWE問題構(gòu)造函數(shù)加密方案

函數(shù)加密（functional encryption， FE）方案[43-44]是公鑰加密方案的一種推廣。它克服了公鑰加密方案中固有的全有或全無、基于用戶的數(shù)據(jù)訪問，支持細(xì)粒度、基于角色的訪問，并允許用戶精確地控制由密文透露給給定接收者的信息量。FE允許擁有秘密函數(shù)解密密鑰的用戶獲得被加密消息的特定函數(shù)值，即在用于函數(shù)類F的FE方案中，加密消息x得到密文CT，由函數(shù)f導(dǎo)出秘密函數(shù)解密密鑰dk，持有dk的給定接收者可以獲得f（x），不會(huì)獲得關(guān)于信息x的其他信息。

現(xiàn)在，通用FE方案被視為現(xiàn)代密碼學(xué)的圣杯。一些工作已經(jīng)朝著這個(gè)目標(biāo)取得了進(jìn)展，但沒有從標(biāo)準(zhǔn)假設(shè)中構(gòu)造出通用結(jié)構(gòu)。由于通用的FE方案距離實(shí)現(xiàn)還很遙遠(yuǎn)，不同的工作專注于為特殊的函數(shù)類構(gòu)建FE方案，比如謂詞加密或內(nèi)積函數(shù)加密（inner-product functional encryption，IPFE）方案。

IPFE是FE方案的一種特殊形式。在方案中，被加密的信息是向量x，函數(shù)解密密鑰dky與向量y有關(guān)，向量y與向量x具有相同的維數(shù)，解密得到內(nèi)積<x，y>。ABDALLA等[45]引入的IPFE方案被認(rèn)為是超越全有或全無解密的第一個(gè)高效加密方案;其提出了一個(gè)可以在LWE假設(shè)下實(shí)例化的通用模式，但方案是選擇性安全的，內(nèi)積求解僅限于計(jì)算短整數(shù)向量的整數(shù)內(nèi)積。

針對(duì)文獻(xiàn)[45]中存在的問題，在2016年的歐密會(huì)上，AGRAWAL等[46]提出的構(gòu)造是由密鑰空間上具有同態(tài)性質(zhì)的哈希證明系統(tǒng)（hash proof systems）獲得的，可以抵抗自適應(yīng)攻擊，其基于多提示擴(kuò)展LWE （multi-hint extended-LWE， mheLWE）問題的構(gòu)造，能夠?qū)?nèi)積取素?cái)?shù)模的運(yùn)算進(jìn)行安全的函數(shù)加密，同時(shí)作者證明素?cái)?shù)域上的內(nèi)積，可以用來構(gòu)造用于所有電路有界碰撞的IPFE方案。

GORDON等[47]提出多用戶函數(shù)加密方案（multi-client functional encryption， MCFE）。MCFE方案是FE方案的自然延伸，在MCFE方案中，數(shù)據(jù)來自不同的用戶端，這些用戶可能彼此不信任，并可能被敵手獨(dú)立、自適應(yīng)地破壞。在設(shè)計(jì)MCFE時(shí)需要克服的主要挑戰(zhàn)是，密文的不同部分必須在不能共享任何隨機(jī)性的情況下進(jìn)行設(shè)計(jì)。文獻(xiàn)[47]中的MCFE方案是支持加密標(biāo)簽的，它允許加密器在解密過程中限制可能發(fā)生的混合和匹配（mix-and-match）的數(shù)量，通過只允許對(duì)基于相同標(biāo)簽生成的密文進(jìn)行解密來實(shí)現(xiàn)。JEREMY等[48]在2018年亞密會(huì)上和ABDALLA等[49]在2019年亞密會(huì)上，對(duì)這種柔性形式的FE方案進(jìn)行了研究。前者基于不同的標(biāo)準(zhǔn)假設(shè)提供了一個(gè)通用結(jié)構(gòu)，但其密文大小隨用戶數(shù)量二次方增長(zhǎng);后者基于分布文獻(xiàn)處理（distributed document handling， DDH）假設(shè)給出MCFE方案，該假設(shè)需要較小的內(nèi)積空間，限制了適用范圍。針對(duì)文獻(xiàn)[48-49]中的不足，在隨機(jī)預(yù)言機(jī)模型下，ABDALLA等[50]提出基于MDDH （Matrix- DIFFIE-HELLMAN）， 判定型合數(shù)剩余（decisional composite residuosity， DCR） 和 LWE三種假設(shè)的線性長(zhǎng)度密文結(jié)構(gòu)。在文獻(xiàn)[50]中，基于LWE問題的MCFE方案為L(zhǎng)WE問題引入噪聲項(xiàng)，因此在安全證明期間無法模擬通過加密查詢泄露的信息;作者使用噪聲泛洪技術(shù)（noise flooding techniques）克服這一挑戰(zhàn)，并通過將密文舍入到更小的空間來避免低效率的缺點(diǎn)，這樣，在舍入操作期間噪聲項(xiàng)就消失了。

2.4 基于LWE問題構(gòu)造密鑰交換協(xié)議

密鑰交換協(xié)議使得通信雙方可以在不可信的信道上交換密鑰。第一個(gè)著名的密鑰交換協(xié)議是DIFFIE和HELLMAN[51]提出的，稱為Diffie-Hellman（DH）密鑰交換協(xié)議。它的安全性基于離散對(duì)數(shù)這一數(shù)論困難問題，這一困難問題很難抵御量子計(jì)算機(jī)攻擊[52]。構(gòu)建基于格中困難問題的密鑰交換協(xié)議被認(rèn)為是后量子密鑰交換協(xié)議的候選方案之一。

PEIKERT[53]認(rèn)為基于LWE問題的密鑰交換協(xié)議在技術(shù)上是可行的，但本人并沒有給出具體的方案。LINDNER等[54]給出了基于LWE問題的類DH密鑰交換技術(shù)的框架。文獻(xiàn)[53-54]中，作者試圖要解決的問題是誤差消除，即如何從兩個(gè)近似值中抽取共享秘密，使通信雙方通過計(jì)算協(xié)商得到密鑰。DING[55]提出第一個(gè)可證明安全性的基于LWE問題的密鑰交換協(xié)議，該協(xié)議計(jì)算效率高，可推廣到R-LWE問題中;協(xié)議利用信號(hào)函數(shù)四舍五入，從兩個(gè)非常接近的值中提取共享密鑰，解決了上述誤差消除問題。LWE問題本身可以被視為具有小誤差的某種形式的內(nèi)積，在某些應(yīng)用中可以通過某種方式消除;而該協(xié)議可以看作是這一思想在雙線性配對(duì)情況下的擴(kuò)展，即帶有誤差的雙線性形式配對(duì)。協(xié)議的有效性取決于非交換環(huán)（LWE問題）和交換環(huán)（R-LWE問題）中乘法的結(jié)合性和交換性。

ALKIM等[56]構(gòu)造出一個(gè)新的基于R-LWE問題的密鑰交換協(xié)議;該協(xié)議提出了一個(gè)新的誤差消除算法，主要貢獻(xiàn)是將R-LWE問題中的秘密和誤差服從的離散高斯分布改為二項(xiàng)分布，使得抽樣參數(shù)更加容易。SAARINEN等[57]提出文獻(xiàn)[56]中密鑰交換協(xié)議的一個(gè)變種，并優(yōu)化了文獻(xiàn)[56]中的誤差消除算法，給出了該算法的快速實(shí)現(xiàn)。DING等[58]提出了一種基于小整數(shù)解（short integer solution，SIS）問題和LWE問題的密鑰交換算法。即甲方使用LWE問題來確保他發(fā)送給乙方的內(nèi)容的安全性，乙方使用SIS問題來確保他發(fā)送給甲方的內(nèi)容的安全性。很明顯，系統(tǒng)不是對(duì)稱的。切換后，通過文獻(xiàn)[55]提出的基于LWE問題的密鑰交換中的信號(hào)函數(shù)，可以從兩個(gè)非常接近的值中提取共享密鑰。

2.5 基于LWE問題構(gòu)造數(shù)字簽名方案

數(shù)字簽名方案是密碼學(xué)中的一個(gè)基本原語，是各種高級(jí)密碼協(xié)議的重要組成部分。自問世以來，在標(biāo)準(zhǔn)模型下，學(xué)者提出眾多方案，這些方案的困難性可以歸約到困難的數(shù)論問題上（整數(shù)分解問題、離散對(duì)數(shù)問題等）;鑒于密碼分析的預(yù)期進(jìn)展，為目前使用的簽名方案（如RSA算法和橢圓曲線數(shù)字簽名算法（elliptic curve digital signature algorithm， ECDSA））找到替代方案是很重要的，最有希望取代這些方案的是基于格的簽名方案。

第一個(gè)緊安全性歸約（tight security reduction）基于格的數(shù)字簽名方案是GPV方案[59]，它的實(shí)例化是安全的，但效率不高。在其后幾年構(gòu)造出的基于格的數(shù)字簽名方案中，既沒有緊的歸約性，也沒有可證明安全性的實(shí)例化;雖然可以通過應(yīng)用分叉引理（Forking Lemma）證明這些方案的安全性，但該引理本質(zhì)上導(dǎo)致了不緊的安全性歸約（non-tight security reduction）。

ABDALLA等[60]基于R-LWE問題構(gòu)造了一個(gè)數(shù)字簽名方案，該方案是對(duì)KATZ等[61]方案的改進(jìn)，避開了分叉引理，但是它的緊歸約性涉及到一個(gè)不實(shí)用的大的模數(shù)。GNEYSU等[62]構(gòu)造了一個(gè)基于R-LWE問題的簽名方案。該方案是通過對(duì)文獻(xiàn)[63-64]中方案進(jìn)行組合和優(yōu)化來實(shí)現(xiàn)的，使用文獻(xiàn)[64]中的方法對(duì)文獻(xiàn)[63]中的方案進(jìn)行改進(jìn)，顯示了如何通過將問題從R-SIS改為R-LWE，顯著減小密鑰和簽名的大小。AKLEYLEK等[65]基于R-LWE問題構(gòu)造了第一個(gè)具有可證明實(shí)例化的數(shù)字簽名方案。

上述文獻(xiàn)[60，62，65]中，基于R-LWE問題構(gòu)造的數(shù)字簽名方案，都是隨機(jī)預(yù)言機(jī)模型下安全的。ZHANG等[66]基于LWE問題，構(gòu)造出一個(gè)在標(biāo)準(zhǔn)模型下緊安全的簽名方案來對(duì)抗多用戶自適應(yīng)選擇消息攻擊。

3 優(yōu)勢(shì)和挑戰(zhàn)

3.1 優(yōu)勢(shì)

由于可以將格上最壞情況困難問題歸約到LWE問題及其變體上，基于其構(gòu)造密碼方案時(shí)不需要考慮格上困難問題，就可以達(dá)到抗量子攻擊的目的。在構(gòu)造方案時(shí)，運(yùn)算過程僅涉及到一些簡(jiǎn)單的整數(shù)上代數(shù)運(yùn)算，例如向量、矩陣的運(yùn)算或者特殊代數(shù)結(jié)構(gòu)上的多項(xiàng)式運(yùn)算，故運(yùn)算過程簡(jiǎn)單，效率高，易于實(shí)現(xiàn)。相對(duì)于基于格構(gòu)造的密碼方案，基于LWE問題及其變體構(gòu)造的密碼方案，大幅度減少了方案中的密鑰和密文的尺寸。

在后量子密碼學(xué)中，實(shí)現(xiàn)后量子密碼算法主要有4種方法：基于多變量的密碼算法、基于哈希的密碼算法、基于編碼的密碼算法，基于格的密碼算法?；诙嘧兞康拿艽a算法雖然計(jì)算速度快，但存在公鑰尺寸較大的問題;基于編碼的密碼算法也存在公鑰尺寸大的問題;基于哈希的密碼算法存在輸出長(zhǎng)度較長(zhǎng)的問題。相對(duì)于前3種算法，基于格的算法在安全性、計(jì)算效率、密鑰尺寸上，實(shí)現(xiàn)了更好的平衡。由于基于格的密碼算法的安全性是基于格中困難問題的，在相同的安全性要求下，與前3種算法相比，基于格的密碼算法的公私鑰尺寸更小，計(jì)算效率更高。

3.2 挑戰(zhàn)

本文總結(jié)了基于LWE問題構(gòu)造的5類密碼方案，雖然LWE問題及其變體在各類密碼方案的設(shè)計(jì)和安全性方面有很大的潛力和優(yōu)勢(shì)，但仍然有很多挑戰(zhàn)有待于密碼學(xué)家進(jìn)一步研究、解決。

基于LWE問題及其變體構(gòu)造方案時(shí)，為保證方案的安全性，矩陣的維數(shù)或多項(xiàng)式的階較高，造成存儲(chǔ)開銷過大。同時(shí)，由于安全性要求，矩陣的維數(shù)、系數(shù)的維度和模數(shù)取值較大，相對(duì)于經(jīng)典的密碼方案，基于LWE問題及其變體的密鑰尺寸較大。 運(yùn)算時(shí)，環(huán)上多項(xiàng)式乘法、取模操作等累加到一起，會(huì)造成計(jì)算效率低。

3.2.1 構(gòu)造基于屬性加密方案

目前，基于LWE問題構(gòu)造ABE方案的工作主要圍繞構(gòu)造安全性更高的方案，設(shè)計(jì)高效的CP-ABE方案，以及方案更廣泛的使用范圍開展研究。主要存在以下挑戰(zhàn)：

1）目前的方案，其安全性主要是選擇性安全的，僅有的幾個(gè)全安全的方案，僅僅支持弱的訪問策略。選擇性安全是一種弱的安全，對(duì)敵手的能力有很強(qiáng)的約束，不能抵抗現(xiàn)實(shí)世界中的許多類型的攻擊。

2）目前的方案中更多的是KP-ABE方案，如何構(gòu)造高效的CP-ABE方案仍然是一項(xiàng)具有挑戰(zhàn)性的工作。

3）基于LWE問題，對(duì)于一些重要的訪問策略，是否存在一個(gè)真正去中心化的MA-ABE（multi-authority ABE）密碼方案還需要進(jìn)一步深入研究。

3.2.2 構(gòu)造全同態(tài)加密方案

部分同態(tài)加密方案由于對(duì)運(yùn)算的要求，可以在經(jīng)典密碼學(xué)中實(shí)現(xiàn);但是FHE方案目前只能基于格問題來構(gòu)造，在實(shí)用化方面取得一定進(jìn)展的是第二代、第三代FHE方案，它們都是基于R-LWE問題構(gòu)造的。

目前，在基于LWE問題構(gòu)造FHE方案的工作中， 由于GENTRY的自舉程序是實(shí)現(xiàn)FHE方案的唯一方法，如何對(duì)自舉程序進(jìn)行優(yōu)化是目前的主要工作之一，同時(shí)，對(duì)GSW13方案的優(yōu)化也是一項(xiàng)重要工作?；贚WE問題的FHE方案存在的最大不足就是效率低（自舉程序）和巨大的存儲(chǔ)消耗（矩陣運(yùn)算），如何進(jìn)一步改進(jìn)方案，使方案實(shí)用化是亟須解決的問題。

3.2.3 構(gòu)造函數(shù)加密方案

由于構(gòu)造用于一般函數(shù)的通用FE方案距離實(shí)現(xiàn)還很遙遠(yuǎn)，目前基于LWE問題的FE方案主要是針對(duì)小范圍內(nèi)的特殊函數(shù)，例如線性函數(shù)或多項(xiàng)式，較為熱門的是基于LWE的IPFE方案。該方案主要存在兩個(gè)不足：不能指定接收者的身份和不能認(rèn)證密鑰發(fā)布者的身份，這兩個(gè)不足會(huì)造成在一些應(yīng)用場(chǎng)景中使用該方案時(shí)的安全問題，同時(shí)，如何在更大的范圍構(gòu)造基于LWE問題的FE方案是一項(xiàng)具有挑戰(zhàn)性的工作。

3.2.4 構(gòu)造密鑰交換協(xié)議

目前基于R-LWE問題構(gòu)造的密鑰交換協(xié)議基本上都是根據(jù)PEIKERT[67]建立的Reconciliation技術(shù)實(shí)現(xiàn)的，如何在此基礎(chǔ)上設(shè)計(jì)新的、較實(shí)用的密鑰交換協(xié)議是值得思考的問題。同時(shí)，相對(duì)于經(jīng)典的公鑰算法構(gòu)造的密鑰交換協(xié)議，基于R-LWE問題構(gòu)造的密鑰交換協(xié)議的一個(gè)瓶頸是通信開銷過大;因此，今后工作的一個(gè)重要方向就是在保證基于R-LWE問題構(gòu)造的密鑰交換協(xié)議的安全性和性能平衡的同時(shí)，如何有效地降低通信開銷。

3.2.5 構(gòu)造數(shù)字簽名方案

大多數(shù)基于格的數(shù)字簽名方案的構(gòu)造主要基于兩種途徑：hash-and-sign簽名方法和Fiat-Shamir方法，相對(duì)于第一種方法，第二種方法更加簡(jiǎn)單、高效。近幾年，基于格中困難問題構(gòu)造的數(shù)字簽名方案基本上基于第二種方法，但在構(gòu)造過程中存在的一個(gè)最大挑戰(zhàn)是簽名長(zhǎng)度過大，這也是其不能實(shí)用化的一個(gè)最大障礙。

4 總結(jié)

本文概述了基于LWE問題及其變體構(gòu)造的各類密碼方案，與經(jīng)典密碼方案相比，基于LWE問題及其變體構(gòu)造的密碼方案在抗量子攻擊方面具有很大的潛力，但在效率和實(shí)用性方面還有很大的差距。這表明其還有待于進(jìn)一步完善與發(fā)展，無論是理論研究還是實(shí)用化，基于LWE問題及其變體的密碼方案的設(shè)計(jì)都有很大的理論價(jià)值和實(shí)際意義。參考文獻(xiàn)：

[1]AJTAI M. Generating hard instances of lattice problems （extended abstract）[C]// Symposium on Theory of Computing （STOC 1996）. Philadelphia： ACM， 1996： 99-108.

[2] AJTAI M， DWORK C. A public-key cryptosystem with worst-case/average-case equivalence[C]// Symposium on Theory of Computing （STOC 1997）. El Paso： ACM， 1997： 284-293.

[3] REGEV O. On lattices， learning with errors， random linear codes， and cryptography[C]// Symposium on Theory of Computing （STOC 2005）. Baltimore： ACM， 2005： 84-93.

[4] KAWACHI A， TANAKA K， XAGAWA K. Multi-bit cryptosystems based on lattice problems[C]// Public Key Cryptography （PKC 2007）. Beijing： Springer， 2007： 315-329.

[5] PEIKERT C， WATERS B. Lossy trapdoor functions and their applications[J]. SIAM Journal on Computing， 2011， 40（6）： 1803-1844.

[6] MICCIANCIO D， REGEV O. Lattice-based cryptography[M]// BERNSTEIN D J， BUCHMANN J， DAHMEN E. Post-Quantum Cryptography. New York： Springer， 2009： 147-191.

[7] LYUBASHEVSKY V， PEIKERT C， REGEV O. On ideal lattices and learning with errors over rings[J]. Journal of the ACM， 2013， 60（6）：1-35.

[8] SHOR P W. Algorithms for quantum computation： discrete logarithms and factoring[C]// Foundations of Computer Science （FOCS 1994）. Santa Fe： IEEE， 1994： 124-134.

[9] SAHAI A， WATERS B. Fuzzy identity-based encryption[C]// International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT 2005）. Aarhus： Springer， 2005： 457-473.

[10]BETHENCOURT J， SAHAI A， WATERS B. Ciphertext-policy attribute-based encryption[C]// Symposium on Security and Privacy （S&P 2007）. Berkeley： IEEE， 2007： 321-334.

[11]OSTROVSKY R， SAHAI A， WATERS B. Attribute-based encryption with non-monotonic access structures[C]// Computer and Communications Security （CCS 2007）. Alexandria： ACM， 2007： 195-203.

[12]LEWKO A， OKAMOTO T， SAHAI A， et al. Fully secure functional encryption： attribute-based encryption and （hierarchical） inner product encryption[C]// International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT 2010）. Riviera： Springer， 2010： 62-91.

[13]LEWKO A， WATERS B. Unbounded HIBE and attribute-based encryption[C]// International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT 2011）. Tallinn： Springer， 2011： 547-567.

[14]WATERS B. Ciphertext-policy attribute-based encryption： an expressive， efficient， and provably secure realization[C]// Public Key Cryptography （PKC 2011）. Taormina： Springer， 2011： 53-70.

[15]GARG S， GENTRY C， HALEVI S， et al. Attribute-based encryption for circuits from multilinear maps[C]// International Cryptology Conference （CRYPTO 2013）. Santa Barbara： Springer， 2013： 479-499.

[16]CHEN J， GAY R， WEE H. Improved dual system ABE in prime-order groups via predicate encodings[C] // International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT 2015）. Sofia： Springer， 2015： 595-624.

[17]CHEN J， GONG J， KOWALCZYK L， et al. Unbounded ABE via bilinear entropy expansion， revisited[C]// International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT 2018）. Tel Aviv： Springer， 2018： 503-534.

[18]KOWALCZYK L， WEE H. Compact adaptively secure ABE for NC 1 from k-Lin[C]// International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT 2019）. Darmstadt： Springer， 2019： 3-33.

[19]GONG J， WEE H. Adaptively secure ABE for DFA from k-Lin and more[C]// International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT 2020）.[S.l.]： Springer， 2020： 278-308.

[20]AJTAI M. Generating hard instances of the short basis problem[C]// International Colloquium on Automata， Languages， and Programming （ICALP 1999）. Prague： Springer， 1999： 1-9.

[21]GENTRY C， PEIKERT C， VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions[C]// Symposium on Theory of Computing （STOC 2008）. British Columbia： ACM， 2008： 17-20.

[22]CASH D， HOFHEINZ D， KILTZ E， et al. Bonsai trees， or how to delegate a lattice basis[J]. Journal of Cryptology， 2012， 25（4）： 601-639.

[23]AGRAWAL S， BONEH D， BOYEN X. Efficient lattice （H）IBE in the standard model[C]// International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT 2010）. Nice： Springer， 2010： 553-572.

[24]AGRAWAL S， BONEH D， BOYEN X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE[C]// International Cryptology Conference （CRYPTO 2010）. Santa Barbara： Springer， 2010： 98-115.

[25]BOYEN X. Attribute-based functional encryption on lattices[C]// Theory of Cryptography Conference （TCC 2013）. Tokyo： Springer， 2013： 122-142.

[26]GORBUNOV S， VINAYAGAMURTHY D. Riding on asymmetry： efficient ABE for branching programs[C]// International Conference on the Theory and Application of Cryptology and Information Security （ASIACRYPT 2015）. Auckland： Springer， 2015： 550-574.

[27]BRAKERSKI Z， VAIKUNTANATHAN V. Circuit-ABE from LWE： unbounded attributes and semi-adaptive security[C]// International Cryptology Conference （CRYPTO 2016）. Santa Barbara： Springer， 2016： 363-384.

[28]AGRAWAL S， MAITRA M， YAMADA S. Attribute based encryption （and more） for nondeterministic finite automata from LWE[C]// International Cryptology Conference （CRYPTO 2019）. Santa Barbara： Springer， 2019： 765-797.

[29]TSABARY R. Fully secure attribute-based encryption for -CNF from LWE[C]// International Cryptology Conference （CRYPTO 2019）. Santa Barbara： Springer， 2019： 62-85.

[30]RIVEST R L， ADLEMAN L， DERTOUZOS M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation， 1978， 4（11）： 169-180.

[31]GENTRY C. Fully homomorphic encryption using ideal lattices[C]// Symposium on Theory of Computing （STOC 2009）. Bethesda： ACM， 2009： 169-178.

[32]BRAKERSKI Z， VAIKUNTANATHAN V. Efficient fully homomorphic encryption from （standard） LWE[C]// Foundations of Computer Science （FOCS 2011）. Palm Springs： IEEE， 2011：97-106.

[33]BRAKERSKI Z， GENTRY C， VAIKUNTANATHAN V. （Leveled）Fully homomorphic encryption without bootstrapping[C]// Innovations in Theoretical Computer Science （ITCS 2012）. Cambridge： ACM， 2012： 309-325.

[34]GENTRY C， SAHAI A， WATERS B. Homomorphic encryption from learning with errors， conceptually-simpler， asymptotically-faster， attribute-based[C]// International Cryptology Conference （CRYPTO 2013）. Santa Barbara： Springer， 2013： 75-92.

[35]ALPERIN-SHERIFF J， PEIKERT C. Faster bootstrapping with polynomial error[C]// International Cryptology Conference （CRYPTO 2014）. Santa Barbara： Springer， 2014： 297-314.

[36]BRAKERSKI Z， VAIKUNTANATHAN V. Lattice-based FHE as secure as PKE[C]// Innovations in Theoretical Computer Science （ITCS 2014）. Princeton： ACM， 2014： 1-12.

[37]HIROMASA R， ABE M， OKAMOTO T. Packing messages and optimizing bootstrapping in GSW-FHE[C]// Public Key Cryptography （PKC 2015）. Washington： Springer， 2015： 699-715.

[38]DUCAS L， MICCIANCIO D. FHEW： bootstrapping homomorphic encryption in less than a second[C]// International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT 2015）. Sofia： Springer， 2015： 617-640.

[39]CHILLOTTI I， GAMA N， GEORGIEVA M， et al. Faster fully homomorphic encryption： bootstrapping in less than 0.1 seconds[C]// International Conference on the Theory and Application of Cryptology and Information Security （ASIACRYPT 2016）. Hanoi： Springer， 2016： 3-33.

[40]CHILLOTTI I， GAMA N， GEORGIEVA M， et al. Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[C]// International Conference on the Theory and Application of Cryptology and Information Security （ASIACRYPT 2017）. Hong Kong： Springer， 2017： 377-408.

[41]LPEZ-ALT A， TROMER E， VAIKUNTANATHAN V. On-the-fly multiparty computation on the cloud via multi-key fully homomorphic encryption[C]// Symposium on Theory of Computing （STOC 2012）. New York： ACM， 2012： 1219-1234.

[42]CLEAR M， MCGOLDRICK C. Multi-identity and Multi-key leveled FHE from learning with errors[C]// International Cryptology Conference （CRYPTO 2015）. Santa Barbara： Springer， 2015： 630-656.

[43]BONEH D， SAHAI A， WATERS B. Functional encryption： Definitions and challenges[C]// Theory of Cryptography Conference （TCC 2011）. Providence： Springer， 2011： 253-273.

[44]O’NEILL A. Definitional issues in functional encryption[DB/OL]. （2011-03-19）[2021-10-13]. https：//eprint.iacr.org/2010/556.pdf.

[45]ABDALLA M， BOURSE F， CARO A D， et al. Simple functional encryption schemes for inner products[C]// Public Key Cryptography （PKC 2015）. Washington： Springer， 2015： 733-751.

[46]AGRAWAL S， LIBERT B， STEHLE D. Fully secure functional encryption for inner products， from standard assumptions[C]// International Cryptology Conference （CRYPTO 2016）. Santa Barbara： Springer， 2016： 333-362.

[47]GORDON S D， KATZ J， LIU F H， et al. Multi-input functional encryption[C]// International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT 2014）. Copenhagen： Springer， 2014： 578-602.

[48]JEREMY E， SANS D， GAY R， et al. Decentralized multi-client functional encryption for inner product[C]//International Conference on the Theory and Application of Cryptology and Information Security （ASIACRYPT 2018）. Brisbane： Springer， 2018： 703-732.

[49]ABDALLA M， BENHAMOUDA F， GAY， R. From single-input to multi-client inner-product functional encryption[C]// International Conference on the Theory and Application of Cryptology and Information Security （ASIACRYPT 2019）. Kobe： Springer， 2019： 552-582.

[50]ABDALLA M， BOURSE F， MARIVAL H， et al. Multi-client inner-product functional encryption in the random-oracle model[C]// Security and Cryptography for Networks （SCN 2020）. Amalfi： Springer， 2020： 525-545.

[51]DIFFIE W， HELLMAN M. New directions in cryptography[J]. IEEE Transactions on Information Theory， 1976， 22（6）： 644-654.

[52]SHOR P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review， 1999， 41（2）： 303-332.

[53]PEIKERT C. Some recent progress in lattice-based cryptography[C]// Theory of Cryptography Conference （TCC 2009）. San Francisco： Springer， 2009： 72-72.

[54]LINDNER R， PEIKERT， C. Better key sizes （and attacks） for LWE-based encryption[C]// The Cryptographers’ Track at the RSA Conference （CT-RSA 2011）. San Francisco： Springer， 2011： 319-339.

[55]DING J T， XIE X， LIN X D. A simple provably secure key exchange scheme based on the learning with errors problem[DB/OL]. （2014-07-29）[2021-10-13]. https：//eprint.iacr.org/2012/688.pdf.

[56]ALKIM E， DUCAS L， POPPELMANN T， et al. Post-quantum key exchange： a new hope[C]// 25th USENIX Security Symposium （USENIX Security 2016）. Austin： Springer， 2016： 327-343.

[57]SAARINEN， MARKKU-JUHANI O. HILA5： on reliability， reconciliation， and error correction for ring-LWE encryption[C]// Selected Areas in Cryptography （SAC 2017）. Ottawa： Springer， 2018： 192-212.

[58]DING J T， SCHMITT K， ZHANG Z. A Key exchange based on the short integer solution problem and the learning with errors problem[C]// Codes， Cryptology and Information Security （C2SI 2019）. Rabat： Springer， 2019： 105-117.

[59]GENTRY C， PEIKERT C， VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions[C]// Symposium on Theory of Computing （STOC 2008）. British Columbia： ACM， 2008： 197-206.

[60]ABDALLA M， FOUQUE P-A， LYUBASHEVSKY V， et al. Tightly-secure signatures from lossy identification schemes[C]// International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT 2012）. Cambridge： Springer， 2012： 572-590.

[61]KATZ J， WANG N. Efficiency improvements for signature schemes with tight Security reductions[C]// Computer and Communications Security （CCS2003）. Washington： ACM， 2003： 155-164.

[62]GNEYSU T， LYUBASHEVSKY V， POPPELMANN T. Practical lattice-based cryptography： a signature scheme for embedded systems[C]// Cryptographic Hardware and Embedded Systems （CHES 2012）. Leuven： Springer， 2012： 530-547.

[63]LYUBASHEVSKY V. Fiat-Shamir with aborts： applications to lattice and factoring-based signatures[C]// International Conference on the Theory and Application of Cryptology and Information Security （ASIACRYPT 2009）. Tokyo： Springer， 2009： 598-616.

[64]LYUBASHEVSKY V. Lattice signatures without trapdoors[C]// International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT 2012）. Cambridge： Springer， 2012： 738-755.

[65]AKLEYLEK S， BINDEL N， BUCHMANN J， et al. An efficient lattice-based signature scheme with provably secure instantiation[C]// International Conference on Cryptology in Africa （AFRICACRYPT 2016）. Fes： Springer， 2016： 44-60.

[66]ZHANG X， LIU S， PAN J X， et al. Tightly secure signature schemes from the LWE and subset sum assumptions[J]. Theoretical Computer Science， 2019， 795： 326-344.

[67]PEIKERT C. Lattice cryptography for the internet[C]//Post-Quantum Cryptography （PQCrypto 2014）. Waterloo： Springer， 2014： 197-219.

（責(zé)任編輯：周曉南）

A Survey on the Construction of Cryptography

Scheme Based on LWE Problem

YANG Nan TIAN Youliang

（1.College of Computer Science and Technology，Guizhou University，Guiyang 550025，China;

2.College of Mathematics and Statistics， Qiannan Normal University for Nationalities， Duyun

558000， China;

3.State Key Laboratory of Public Big Data，Guiyang 550025，China）Abstract： In the era of

post-quantum cryptography， how to design a cryptosystem resistant to quantum computing

attack is the main task of post-quantum cryptography. Lattice-based public key

cryptosystem is considered to be the cryptosystem most resistant to quantum threats. The

cryptosystem based on learning with Errors （LWE） problem is one of the two lattice-based

cryptography schemes with the best practical prospect. This paper summarizes LWE-based

cryptographic schemes and existing challenges in current research from five aspects of LWE

-based construction， attribute-based encryption schemes， full homomorphic encryption

schemes， functional encryption schemes， key exchange protocols， and digital signature

schemes.

Key words： learning with errors; attribute-based encryption; full homomorphic encryption;

functional encryption; key exchange; digital signature