基于LWE問題構(gòu)造密碼方案綜述

楊楠　田有亮

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

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

中圖分類號：TP309.7文獻標志碼：A

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

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

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

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

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

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

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

1 基本知識

1.1 格

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

L=L（a，…，a）

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

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

1.2 格中困難問題

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

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

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

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

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

1.3 LWE問題

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

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

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

1.4 R-LWE問題

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

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

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

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

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

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

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

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

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

在2011年FOCS（Annual Symposium on Foundations of Computer Science）會議上，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），減少了計算復(fù)雜性，構(gòu)造出第一個可自舉的基于LWE問題的有限同態(tài)加密方案。在2012年ITCS（Innovations in Theoretical Computer Science Conference）會議上，BRAKERSKI等[33]基于R-LWE問題，采用密鑰轉(zhuǎn)換技術(shù)（key-switching technique）控制密文維數(shù)膨脹問題，用模數(shù)轉(zhuǎn)換技術(shù)（modulus-switching technique）降低密文運算中的噪聲規(guī)模增長問題，實現(xiàn)無需自舉就可以做到多項式深度的同態(tài)運算。但上述兩個同態(tài)加密方案的密文用向量表示，通過向量的張量積進行密文同態(tài)乘法運算會導(dǎo)致密文的維數(shù)急劇膨脹。上述兩方案被稱為第二代FHE方案。

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

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

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

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

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

現(xiàn)在，通用FE方案被視為現(xiàn)代密碼學(xué)的圣杯。一些工作已經(jīng)朝著這個目標取得了進展，但沒有從標準假設(shè)中構(gòu)造出通用結(jié)構(gòu)。由于通用的FE方案距離實現(xià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方案被認為是超越全有或全無解密的第一個高效加密方案;其提出了一個可以在LWE假設(shè)下實例化的通用模式，但方案是選擇性安全的，內(nèi)積求解僅限于計算短整數(shù)向量的整數(shù)內(nèi)積。

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

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

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

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

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

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

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

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

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

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

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

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

3.1 優(yōu)勢

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

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

3.2 挑戰(zhàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 總結(jié)

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

[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