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

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

2、.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年，AJTAI1取得開創(chuàng)性成果，構(gòu)造出整數(shù)格中的隨機(jī)格類，第一次將任意格上一類困難問題的最壞情況問題歸約到求解隨機(jī)格類的平均困難情況上，使得基于格問題構(gòu)造可證明安全性的密碼體制成為可能。AJTAI等2在1997

3、年的計(jì)算理論研討會(huì)（symposiumontheoryofcomputing，STOC）上，基于格上唯一最短向量問題（uniqueshortestvectorproblem，uSVP）的困難性，構(gòu)造出第一個(gè)基于格的公鑰密碼體制。隨后，基于格的公鑰密碼體制不斷出現(xiàn)，但存在密鑰尺寸過大、效率不高或缺乏安全性證明的問題。2022年，REGEV3提出容錯(cuò)學(xué)習(xí)（learningwitherrors，LWE）問題，利用一個(gè)量子多項(xiàng)式規(guī)約算法，將求解平均困難情況的LWE問題歸約到求解任意的n維格上最壞情況困難問題判定型近似最短向量問題（decisionalapproximateshortestvectorp

4、roblem，GapSVP）、近似最短獨(dú)立向量問題（approximateshortestindependentvectorsproblem，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問題的公鑰加密方案，其加密過

5、程是對明文逐位加密，每次只能加密1bit，效率較低。為進(jìn)一步提高效率，在不增加密文大小的情況下，KAWACHI等4提出基于LWE問題的多比特公鑰加密方案。PEIKERT等5給出更大明文空間上的基于LWE問題的有損陷門函數(shù)（lossytrapdoorfunctions，lossyTDFs），隨后MICCIANICO等6對該方案進(jìn)行優(yōu)化。由于LWE使用中固有的二次開銷，造成上述方案的效率相當(dāng)?shù)?。為解決這一問題，2022年，LYUBASHEVSKY等7構(gòu)造出LWE的一個(gè)代數(shù)變體環(huán)-LWE（Ring-LWE，R-LWE）。該方案相對于LWE方案的主要優(yōu)勢是減少密鑰尺寸，降低開銷。R-LWE問題的困難性

6、可以歸約到任意理想格上的近似最短向量問題（approximateshortestvectorproblem，SVP）上。與LWE問題類似，R-LWE問題有兩個(gè)主要的版本：搜索型R-LWE（Search-R-LWE）問題和判定型R-LWE（Decision-R-LWE）問題。1994年，SHOR8提出著名的Shor量子算法，可以在多項(xiàng)式時(shí)間內(nèi)高效解決大整數(shù)分解和離散對數(shù)問題，對當(dāng)時(shí)主流公鑰密碼體制構(gòu)成潛在威脅。設(shè)計(jì)可以抵抗量子計(jì)算攻擊的密碼體制是后量子密碼的主要任務(wù)，基于格的公鑰密碼被認(rèn)為是最有可能抵御量子計(jì)算威脅的密碼體制。在美國國家標(biāo)準(zhǔn)與技術(shù)研究院（nationalinstituteofst

7、andardsandtechnology，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|xZ，in其中：向量組a，a是格L的一個(gè)基;m是格L的維數(shù);n是格L的秩;常用的格是整數(shù)格。1.2格中困難問題最短向

8、量問題（shortestvectorproblem，SVP）。對于給定的一個(gè)格，找到它的最短非零格向量。近似最短向量問題（SVP）。L是一個(gè)m維格，實(shí)數(shù)d1，找到一個(gè)格向量vL，使得vd1（L）。-唯一最短向量問題（uSVP）。給定一個(gè)格L，滿足（L）（L），找到格中最短非零格向量。判定型近似最短向量問題（GapSVP）。L是一個(gè)m維格，實(shí)數(shù)d0，若（L）d，則yes，若（L）（n）d，則no。近似最短獨(dú)立向量問題（SIVP）。L是一個(gè)秩為n的格，找到n個(gè)線性無關(guān)的格向量，使得向量的長度不超過（n）（L）。1.3LWE問題定義2LWE分布（LWEdistribution）。在Z中均勻隨機(jī)選擇一

9、個(gè)秘密s，ZZ上的LWE分布A滿足：均勻隨機(jī)選取aZ，從Z上的離散高斯分布中抽樣得到e，輸出（a，b=a，s+emodq）。定義3搜索型容錯(cuò)學(xué)習(xí)問題。從Z中均勻隨機(jī)抽取一個(gè)秘密s，給定m個(gè)從LWE分布A中獨(dú)立抽樣的隨機(jī)對（a，b）ZZ（隨機(jī)對中的秘密均為s），求解出s。定義4判定型容錯(cuò)學(xué)習(xí)問題。給定m個(gè)獨(dú)立抽樣（a，b）ZZ，其中每一個(gè)抽樣的分布要么服從A（服從A分布的所有抽樣，其均勻選擇的秘密固定為s）分布，要么服從ZZ上均勻分布，判定型容錯(cuò)學(xué)習(xí)問題就是以不可忽略的概率區(qū)分出每一個(gè)抽樣滿足哪一種分布。1.4R-LWE問題定義5R-LWE分布（R-LWEdistribution）。令R=Zx/

10、（x+1），其中n是2的方冪，R=Zx/（x+1），從R中隨機(jī)選取一個(gè)稱為秘密的元素s，是R上的一個(gè)分布，RR上的R-LWE分布A滿足：隨機(jī)均勻選取aRq，從R上的分布中抽樣得到e，輸出（a，b=sa+emodq）。定義6搜索型環(huán)容錯(cuò)學(xué)習(xí)（search-R-LWE）問題。從R中均勻隨機(jī)抽取一個(gè)秘密s，給定m個(gè)從R-LWE分布A中獨(dú)立抽樣的隨機(jī)對（a，b）RR（隨機(jī)對中的秘密均為s），求解出s。定義7判定型環(huán)容錯(cuò)學(xué)習(xí)（decision-R-LWE）問題。給定m個(gè)獨(dú)立抽樣（a，b）RR，其中每一個(gè)抽樣的分布要么服從A（服從A分布的所有抽樣，其均勻選擇的秘密固定為s）分布，要么服從RR上的均勻分布，

11、判定型環(huán)容錯(cuò)學(xué)習(xí)問題就是以不可忽略的概率區(qū)分出每一個(gè)抽樣滿足哪一種分布。2基于LWE問題構(gòu)造密碼方案2.1基于LWE問題構(gòu)造基于屬性加密方案基于屬性加密（attribute-basedencryption，ABE）方案是公鑰加密方案的擴(kuò)展，提供了高效而簡單的數(shù)據(jù)共享機(jī)制，支持細(xì)粒度的訪問控制。自SAHAI等9在2022年歐密會(huì)上提出基于模糊身份加密方案，引入ABE思想后，ABE已成為一種具有應(yīng)用價(jià)值的密碼原語，由此產(chǎn)生了一系列在效率、表達(dá)性、安全性和基本假設(shè)之間實(shí)現(xiàn)各種權(quán)衡的工作10-19。前面提到的大多數(shù)工作的安全性與基于雙線性映射的假設(shè)有關(guān)，鑒于已知量子計(jì)算對基于群結(jié)構(gòu)的攻擊，構(gòu)建基于格的

12、ABE方案，實(shí)現(xiàn)量子計(jì)算攻擊下的安全性尤為重要。在AJTAI1，20、REGEV3等開創(chuàng)性工作的基礎(chǔ)上，第一個(gè)基于格的基于身份加密（identity-basedencryption，IBE）方案被構(gòu)造出來21-23，其在選擇模型下是安全的;AGRAWAL等24提出一個(gè)具有全安全（fullsecurity）的結(jié)構(gòu)。此后，許多學(xué)者對基于LWE問題的ABE方案進(jìn)行了研究。BOYEN25利用格上的LWE問題，通過建立一種新的適合處理復(fù)雜訪問策略的格操作框架，構(gòu)造出一個(gè)基于密鑰策略的屬性加密（keypolicy-ABE，KP-ABE）的方案，在標(biāo)準(zhǔn)模型下是安全的。GORBUNOV等26構(gòu)造了一個(gè)新的、高

13、效的，用于短密鑰分支程序P的ABE方案，其中短密鑰的長度是P+poly（），是安全參數(shù);在具有多項(xiàng)式近似因子的LWE假設(shè)下，具有選擇性安全（selectively-secure）。BRAKERSKI等27針對部分ABE方案中存在屬性的長度（表示為二進(jìn)制字符串）必須在初始化期間確定的問題，通過構(gòu)造一個(gè)基于LWE的ABE方案，使得公共參數(shù)的大小在安全參數(shù)中是一個(gè)固定的多項(xiàng)式，利用這些固定長度參數(shù)，對任意長度的屬性進(jìn)行加密;同時(shí)，安全性滿足半選擇性安全（semi-selectivelysecure），即敵手可以在得到公共參數(shù)之后，但在任何解密密鑰之前選擇挑戰(zhàn)屬性，而在此之前，基于LWE問題的結(jié)構(gòu)只能

14、實(shí)現(xiàn)選擇性安全。AGRAWAL等28基于LWE假設(shè)，構(gòu)造了第一個(gè)基于對稱密鑰屬性用于非確定性有限自動(dòng)機(jī)（nondeterministicfiniteautomata，NFA）加密方案。方案支持長度無界輸入和長度無界機(jī)器，即在方案中，私鑰與一個(gè)長度無界的NFAM有關(guān)，密文與一個(gè)元組（x，m）有關(guān)，x是長度無界的公開屬性，m是秘密消息比特，解密恢復(fù)m，當(dāng)且僅當(dāng)M（x）=1。TSABARY29首次為函數(shù)類t-合取范式（t-conjunctivenormalform，t-CNF）構(gòu)造了一個(gè)基于D-LWE、基于密文策略的屬性加密（ciphertextpolicy-ABE，CP-ABE）方案，其構(gòu)造支持無

15、限規(guī)模的函數(shù)，即每個(gè)函數(shù)由多項(xiàng)式個(gè)子句組成。這些函數(shù)類包括NP-驗(yàn)證策略（NP-verificationpolicies）、比特固定策略（bit-fixingpolicies）和t-閾值策略（t-thresholdpolicies）。2.2基于LWE問題構(gòu)造全同態(tài)加密方案全同態(tài)加密（fullyhomomorphicencryption，F(xiàn)HE）思想，由RIVEST等30在1978年提出，允許在不知道私鑰的情況下，對密文進(jìn)行無限量的運(yùn)算，可以間接地對原文進(jìn)行相應(yīng)操作。這一開創(chuàng)性的構(gòu)想一經(jīng)提出，整個(gè)學(xué)術(shù)界為之轟動(dòng)，但經(jīng)過幾十年的探索，一直未能找到既滿足全同態(tài)加密的所有條件，又容易證明安全性的方案。

16、2022年，GENTRY31基于理想格提出第一個(gè)FHE方案。在方案中，作者通過自舉（Bootstrapping）密文處理方法，將噪音接近臨界值的密文轉(zhuǎn)變?yōu)樵胍糨^低的密文，從而實(shí)現(xiàn)全同態(tài)加密，但是該方案存在效率低、密鑰尺寸大的問題。這是一個(gè)概念上和實(shí)踐上都不實(shí)用的方案。該方案被稱為第一代FHE方案。在2022年FOCS（AnnualSymposiumonFoundationsofComputerScience）會(huì)議上，BRAKERSKI等32不同于之前的方案（依賴于各種環(huán)中的理想相關(guān)的復(fù)雜性假設(shè)），基于LWE問題，采用重線性技術(shù)（re-linearizationtechnique）控制密文的維數(shù)

17、，利用維數(shù)-模數(shù)約減（dimension-modulusreduction）技術(shù)，避開稀疏子集和假設(shè)（sparsesubset-sumassumption），減少了計(jì)算復(fù)雜性，構(gòu)造出第一個(gè)可自舉的基于LWE問題的有限同態(tài)加密方案。在2022年ITCS（InnovationsinTheoreticalComputerScienceConference）會(huì)議上，BRAKERSKI等33基于R-LWE問題，采用密鑰轉(zhuǎn)換技術(shù)（key-switchingtechnique）控制密文維數(shù)膨脹問題，用模數(shù)轉(zhuǎn)換技術(shù)（modulus-switchingtechnique）降低密文運(yùn)算中的噪聲規(guī)模增長問題，實(shí)現(xiàn)無

18、需自舉就可以做到多項(xiàng)式深度的同態(tài)運(yùn)算。但上述兩個(gè)同態(tài)加密方案的密文用向量表示，通過向量的張量積進(jìn)行密文同態(tài)乘法運(yùn)算會(huì)導(dǎo)致密文的維數(shù)急劇膨脹。上述兩方案被稱為第二代FHE方案。在2022年的歐密會(huì)上，基于LWE問題，GENTRY等34借助近似特征向量（approximateeigenvector）方法，構(gòu)造了一個(gè)FHE方案，簡稱GSW13方案。相對之前的方案，GSW13方案中密文由一個(gè)矩陣構(gòu)成，多數(shù)情況下，同態(tài)運(yùn)算的加法和乘法是矩陣的加法和乘法，因此該方案漸進(jìn)性更快，避免了密文維數(shù)膨脹問題，同時(shí)，不需要密鑰轉(zhuǎn)換技術(shù)和模數(shù)轉(zhuǎn)換技術(shù)。相對于文獻(xiàn)32-33中的BV11方案和BGV12方案，GSW13方

19、案在進(jìn)行同態(tài)加密運(yùn)算時(shí)，不需要獲得用戶的求解密鑰（evaluationkey），求值器（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ù)來

20、優(yōu)化文獻(xiàn)36的自舉方案。GSW13的后續(xù)工作主要是構(gòu)建基于R-LWE的方案38-40。多密鑰全同態(tài)加密（multi-keyfullhomomorphicencryption，MKFHE）可以對不同公鑰（用戶）下加密的數(shù)據(jù)進(jìn)行任意操作，最終的密文可以由所有相關(guān)用戶共同解密。因此，MKFHE在安全多方計(jì)算（securitymulti-partycomputation，MPC）方面具有天然的優(yōu)勢和應(yīng)用價(jià)值。2022年，LPEZ-ALT等41基于NTRU（numbertheoryresearchunit）密碼體制，提出了第一個(gè)MKFHE方案，但該方案的安全性基于多項(xiàng)式環(huán)上的非標(biāo)準(zhǔn)假設(shè)。在2022年的歐

21、密會(huì)上，CLEAR等42構(gòu)造出第一個(gè)基于LWE問題的GSW-多密鑰全同態(tài)加密方案，其安全性可以歸約到理想格上最壞情況困難問題上。2.3基于LWE問題構(gòu)造函數(shù)加密方案函數(shù)加密（functionalencryption，F(xiàn)E）方案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)

22、于信息x的其他信息?，F(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-productfunctionalencryption，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í)例化的通用

23、模式，但方案是選擇性安全的，內(nèi)積求解僅限于計(jì)算短整數(shù)向量的整數(shù)內(nèi)積。針對文獻(xiàn)45中存在的問題，在2022年的歐密會(huì)上，AGRAWAL等46提出的構(gòu)造是由密鑰空間上具有同態(tài)性質(zhì)的哈希證明系統(tǒng)（hashproofsystems）獲得的，可以抵抗自適應(yīng)攻擊，其基于多提示擴(kuò)展LWE（multi-hintextended-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-clientfunctionalencryption，MCFE）。MCFE方案

24、是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ù)量，通過只允許對基于相同標(biāo)簽生成的密文進(jìn)行解密來實(shí)現(xiàn)。JEREMY等48在2022年亞密會(huì)上和ABDALLA等49在2022年亞密會(huì)上，對這種柔性形式的FE方案進(jìn)行了研究。前者基于不同的標(biāo)準(zhǔn)假設(shè)提供了一個(gè)通用結(jié)構(gòu)，但其密文大小隨用戶數(shù)量二次方增長;后者基于分布文獻(xiàn)

25、處理（distributeddocumenthandling，DDH）假設(shè)給出MCFE方案，該假設(shè)需要較小的內(nèi)積空間，限制了適用范圍。針對文獻(xiàn)48-49中的不足，在隨機(jī)預(yù)言機(jī)模型下，ABDALLA等50提出基于MDDH（Matrix-DIFFIE-HELLMAN），判定型合數(shù)剩余（decisionalcompositeresiduosity，DCR）和LWE三種假設(shè)的線性長度密文結(jié)構(gòu)。在文獻(xiàn)50中，基于LWE問題的MCFE方案為LWE問題引入噪聲項(xiàng)，因此在安全證明期間無法模擬通過加密查詢泄露的信息;作者使用噪聲泛洪技術(shù)（noisefloodingtechniques）克服這一挑戰(zhàn)，并通過將密文

26、舍入到更小的空間來避免低效率的缺點(diǎn)，這樣，在舍入操作期間噪聲項(xiàng)就消失了。2.4基于LWE問題構(gòu)造密鑰交換協(xié)議密鑰交換協(xié)議使得通信雙方可以在不可信的信道上交換密鑰。第一個(gè)著名的密鑰交換協(xié)議是DIFFIE和HELLMAN51提出的，稱為Diffie-Hellman（DH）密鑰交換協(xié)議。它的安全性基于離散對數(shù)這一數(shù)論困難問題，這一困難問題很難抵御量子計(jì)算機(jī)攻擊52。構(gòu)建基于格中困難問題的密鑰交換協(xié)議被認(rèn)為是后量子密鑰交換協(xié)議的候選方案之一。PEIKERT53認(rèn)為基于LWE問題的密鑰交換協(xié)議在技術(shù)上是可行的，但本人并沒有給出具體的方案。LINDNER等54給出了基于LWE問題的類DH密鑰交換技術(shù)的框架

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

28、于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ù)解（shortintegersolution，SIS）問題和LWE問題的密鑰交換算法。即甲方使用LWE問題來確保他發(fā)送給乙方的內(nèi)容的安全性，乙方使用SIS問題來確保他發(fā)送給甲方的內(nèi)容的安全性。很明顯，系統(tǒng)不是對稱的。切換后，通過文獻(xiàn)55提出的基于LWE問題的密鑰交換中的信號(hào)函數(shù)，可以從兩

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

30、它的實(shí)例化是安全的，但效率不高。在其后幾年構(gòu)造出的基于格的數(shù)字簽名方案中，既沒有緊的歸約性，也沒有可證明安全性的實(shí)例化;雖然可以通過應(yīng)用分叉引理（ForkingLemma）證明這些方案的安全性，但該引理本質(zhì)上導(dǎo)致了不緊的安全性歸約（non-tightsecurityreduction）。ABDALLA等60基于R-LWE問題構(gòu)造了一個(gè)數(shù)字簽名方案，該方案是對KATZ等61方案的改進(jìn)，避開了分叉引理，但是它的緊歸約性涉及到一個(gè)不實(shí)用的大的模數(shù)。GNEYSU等62構(gòu)造了一個(gè)基于R-LWE問題的簽名方案。該方案是通過對文獻(xiàn)63-64中方案進(jìn)行組合和優(yōu)化來實(shí)現(xiàn)的，使用文獻(xiàn)64中的方法對文獻(xiàn)63中的方案

31、進(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)模型下緊安全的簽名方案來對抗多用戶自適應(yīng)選擇消息攻擊。3優(yōu)勢和挑戰(zhàn)3.1優(yōu)勢由于可以將格上最壞情況困難問題歸約到LWE問題及其變體上，基于其構(gòu)造密碼方案時(shí)不需要考慮格上困難問題，就可以達(dá)到抗量子攻擊的目的。在構(gòu)造方案時(shí)，運(yùn)算過程僅涉及到一些簡單的整數(shù)上代數(shù)運(yùn)算，例如向量、矩陣的運(yùn)算或者特殊

32、代數(shù)結(jié)構(gòu)上的多項(xiàng)式運(yùn)算，故運(yùn)算過程簡單，效率高，易于實(shí)現(xiàn)。相對于基于格構(gòu)造的密碼方案，基于LWE問題及其變體構(gòu)造的密碼方案，大幅度減少了方案中的密鑰和密文的尺寸。在后量子密碼學(xué)中，實(shí)現(xiàn)后量子密碼算法主要有4種方法：基于多變量的密碼算法、基于哈希的密碼算法、基于編碼的密碼算法，基于格的密碼算法。基于多變量的密碼算法雖然計(jì)算速度快，但存在公鑰尺寸較大的問題;基于編碼的密碼算法也存在公鑰尺寸大的問題;基于哈希的密碼算法存在輸出長度較長的問題。相對于前3種算法，基于格的算法在安全性、計(jì)算效率、密鑰尺寸上，實(shí)現(xiàn)了更好的平衡。由于基于格的密碼算法的安全性是基于格中困難問題的，在相同的安全性要求下，與前3種

33、算法相比，基于格的密碼算法的公私鑰尺寸更小，計(jì)算效率更高。3.2挑戰(zhàn)本文總結(jié)了基于LWE問題構(gòu)造的5類密碼方案，雖然LWE問題及其變體在各類密碼方案的設(shè)計(jì)和安全性方面有很大的潛力和優(yōu)勢，但仍然有很多挑戰(zhàn)有待于密碼學(xué)家進(jìn)一步研究、解決。基于LWE問題及其變體構(gòu)造方案時(shí)，為保證方案的安全性，矩陣的維數(shù)或多項(xiàng)式的階較高，造成存儲(chǔ)開銷過大。同時(shí)，由于安全性要求，矩陣的維數(shù)、系數(shù)的維度和模數(shù)取值較大，相對于經(jīng)典的密碼方案，基于LWE問題及其變體的密鑰尺寸較大。運(yùn)算時(shí)，環(huán)上多項(xiàng)式乘法、取模操作等累加到一起，會(huì)造成計(jì)算效率低。3.2.1構(gòu)造基于屬性加密方案目前，基于LWE問題構(gòu)造ABE方案的工作主要圍繞構(gòu)造

34、安全性更高的方案，設(shè)計(jì)高效的CP-ABE方案，以及方案更廣泛的使用范圍開展研究。主要存在以下挑戰(zhàn)：1）目前的方案，其安全性主要是選擇性安全的，僅有的幾個(gè)全安全的方案，僅僅支持弱的訪問策略。選擇性安全是一種弱的安全，對敵手的能力有很強(qiáng)的約束，不能抵抗現(xiàn)實(shí)世界中的許多類型的攻擊。2）目前的方案中更多的是KP-ABE方案，如何構(gòu)造高效的CP-ABE方案仍然是一項(xiàng)具有挑戰(zhàn)性的工作。3）基于LWE問題，對于一些重要的訪問策略，是否存在一個(gè)真正去中心化的MA-ABE（multi-authorityABE）密碼方案還需要進(jìn)一步深入研究。3.2.2構(gòu)造全同態(tài)加密方案部分同態(tài)加密方案由于對運(yùn)算的要求，可以在經(jīng)典

35、密碼學(xué)中實(shí)現(xiàn);但是FHE方案目前只能基于格問題來構(gòu)造，在實(shí)用化方面取得一定進(jìn)展的是第二代、第三代FHE方案，它們都是基于R-LWE問題構(gòu)造的。目前，在基于LWE問題構(gòu)造FHE方案的工作中，由于GENTRY的自舉程序是實(shí)現(xiàn)FHE方案的唯一方法，如何對自舉程序進(jìn)行優(yōu)化是目前的主要工作之一，同時(shí)，對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方案主要是針對小范圍內(nèi)的

36、特殊函數(shù)，例如線性函數(shù)或多項(xiàng)式，較為熱門的是基于LWE的IPFE方案。該方案主要存在兩個(gè)不足：不能指定接收者的身份和不能認(rèn)證密鑰發(fā)布者的身份，這兩個(gè)不足會(huì)造成在一些應(yīng)用場景中使用該方案時(shí)的安全問題，同時(shí)，如何在更大的范圍構(gòu)造基于LWE問題的FE方案是一項(xiàng)具有挑戰(zhàn)性的工作。3.2.4構(gòu)造密鑰交換協(xié)議目前基于R-LWE問題構(gòu)造的密鑰交換協(xié)議基本上都是根據(jù)PEIKERT67建立的Reconciliation技術(shù)實(shí)現(xiàn)的，如何在此基礎(chǔ)上設(shè)計(jì)新的、較實(shí)用的密鑰交換協(xié)議是值得思考的問題。同時(shí)，相對于經(jīng)典的公鑰算法構(gòu)造的密鑰交換協(xié)議，基于R-LWE問題構(gòu)造的密鑰交換協(xié)議的一個(gè)瓶頸是通信開銷過大;因此，今后工作

37、的一個(gè)重要方向就是在保證基于R-LWE問題構(gòu)造的密鑰交換協(xié)議的安全性和性能平衡的同時(shí)，如何有效地降低通信開銷。3.2.5構(gòu)造數(shù)字簽名方案大多數(shù)基于格的數(shù)字簽名方案的構(gòu)造主要基于兩種途徑：hash-and-sign簽名方法和Fiat-Shamir方法，相對于第一種方法，第二種方法更加簡單、高效。近幾年，基于格中困難問題構(gòu)造的數(shù)字簽名方案基本上基于第二種方法，但在構(gòu)造過程中存在的一個(gè)最大挑戰(zhàn)是簽名長度過大，這也是其不能實(shí)用化的一個(gè)最大障礙。4總結(jié)本文概述了基于LWE問題及其變體構(gòu)造的各類密碼方案，與經(jīng)典密碼方案相比，基于LWE問題及其變體構(gòu)造的密碼方案在抗量子攻擊方面具有很大的潛力，但在效率和實(shí)用

38、性方面還有很大的差距。這表明其還有待于進(jìn)一步完善與發(fā)展，無論是理論研究還是實(shí)用化，基于LWE問題及其變體的密碼方案的設(shè)計(jì)都有很大的理論價(jià)值和實(shí)際意義。參考文獻(xiàn)：1AJTAIM.Generatinghardinstancesoflatticeproblems（extendedabstract）C/SymposiumonTheoryofComputing（STOC1996）.Philadelphia：ACM，1996：99-108.2AJTAIM，DWORKC.Apublic-keycryptosystemwithworst-case/average-caseequivalenceC/Sympos

39、iumonTheoryofComputing（STOC1997）.ElPaso：ACM，1997：284-293.3REGEVO.Onlattices，learningwitherrors，randomlinearcodes，andcryptographyC/SymposiumonTheoryofComputing（STOC2022）.Baltimore：ACM，2022：84-93.4KAWACHIA，TANAKAK，XAGAWAK.Multi-bitcryptosystemsbasedonlatticeproblemsC/PublicKeyCryptography（PKC2022）.Bei

40、jing：Springer，2022：315-329.5PEIKERTC，WATERSB.LossytrapdoorfunctionsandtheirapplicationsJ.SIAMJournalonComputing，2022，40（6）：1803-1844.6MICCIANCIOD，REGEVO.Lattice-basedcryptographyM/BERNSTEINDJ，BUCHMANNJ，DAHMENE.Post-QuantumCryptography.NewYork：Springer，2022：147-191.7LYUBASHEVSKYV，PEIKERTC，REGEVO.Onid

41、eallatticesandlearningwitherrorsoverringsJ.JournaloftheACM，2022，60（6）：1-35.8SHORPW.Algorithmsforquantumcomputation：discretelogarithmsandfactoringC/FoundationsofComputerScience（FOCS1994）.SantaFe：IEEE，1994：124-134.9SAHAIA，WATERSB.Fuzzyidentity-basedencryptionC/InternationalConferenceontheTheoryandAppl

42、icationsofCryptographicTechniques（EUROCRYPT2022）.Aarhus：Springer，2022：457-473.10BETHENCOURTJ，SAHAIA，WATERSB.Ciphertext-policyattribute-basedencryptionC/SymposiumonSecurityandPrivacy（SP2022）.Berkeley：IEEE，2022：321-334.11OSTROVSKYR，SAHAIA，WATERSB.Attribute-basedencryptionwithnon-monotonicaccessstructu

43、resC/ComputerandCommunicationsSecurity（CCS2022）.Alexandria：ACM，2022：195-203.12LEWKOA，OKAMOTOT，SAHAIA，etal.Fullysecurefunctionalencryption：attribute-basedencryptionand（hierarchical）innerproductencryptionC/InternationalConferenceontheTheoryandApplicationsofCryptographicTechniques（EUROCRYPT2022）.Rivier

44、a：Springer，2022：62-91.13LEWKOA，WATERSB.UnboundedHIBEandattribute-basedencryptionC/InternationalConferenceontheTheoryandApplicationsofCryptographicTechniques（EUROCRYPT2022）.Tallinn：Springer，2022：547-567.14WATERSB.Ciphertext-policyattribute-basedencryption：anexpressive，efficient，andprovablysecurereali

45、zationC/PublicKeyCryptography（PKC2022）.Taormina：Springer，2022：53-70.15GARGS，GENTRYC，HALEVIS，etal.Attribute-basedencryptionforcircuitsfrommultilinearmapsC/InternationalCryptologyConference（CRYPTO2022）.SantaBarbara：Springer，2022：479-499.16CHENJ，GAYR，WEEH.ImproveddualsystemABEinprime-ordergroupsviapred

46、icateencodingsC/InternationalConferenceontheTheoryandApplicationsofCryptographicTechniques（EUROCRYPT2022）.Sofia：Springer，2022：595-624.17CHENJ，GONGJ，KOWALCZYKL，etal.UnboundedABEviabilinearentropyexpansion，revisitedC/InternationalConferenceontheTheoryandApplicationsofCryptographicTechniques（EUROCRYPT2

47、022）.TelAviv：Springer，2022：503-534.18KOWALCZYKL，WEEH.CompactadaptivelysecureABEforNC1fromk-LinC/InternationalConferenceontheTheoryandApplicationsofCryptographicTechniques（EUROCRYPT2022）.Darmstadt：Springer，2022：3-33.19GONGJ，WEEH.AdaptivelysecureABEforDFAfromk-LinandmoreC/InternationalConferenceontheT

48、heoryandApplicationsofCryptographicTechniques（EUROCRYPT2022）.S.l.：Springer，2022：278-308.20AJTAIM.GeneratinghardinstancesoftheshortbasisproblemC/InternationalColloquiumonAutomata，Languages，andProgramming（ICALP1999）.Prague：Springer，1999：1-9.21GENTRYC，PEIKERTC，VAIKUNTANATHANV.Trapdoorsforhardlatticesan

49、dnewcryptographicconstructionsC/SymposiumonTheoryofComputing（STOC2022）.BritishColumbia：ACM，2022：17-20.22CASHD，HOFHEINZD，KILTZE，etal.Bonsaitrees，orhowtodelegatealatticebasisJ.JournalofCryptology，2022，25（4）：601-639.23AGRAWALS，BONEHD，BOYENX.Efficientlattice（H）IBEinthestandardmodelC/InternationalConfere

50、nceontheTheoryandApplicationsofCryptographicTechniques（EUROCRYPT2022）.Nice：Springer，2022：553-572.24AGRAWALS，BONEHD，BOYENX.Latticebasisdelegationinfixeddimensionandshorter-ciphertexthierarchicalIBEC/InternationalCryptologyConference（CRYPTO2022）.SantaBarbara：Springer，2022：98-115.25BOYENX.Attribute-bas

51、edfunctionalencryptiononlatticesC/TheoryofCryptographyConference（TCC2022）.Tokyo：Springer，2022：122-142.26GORBUNOVS，VINAYAGAMURTHYD.Ridingonasymmetry：efficientABEforbranchingprogramsC/InternationalConferenceontheTheoryandApplicationofCryptologyandInformationSecurity（ASIACRYPT2022）.Auckland：Springer，20

52、22：550-574.27BRAKERSKIZ，VAIKUNTANATHANV.Circuit-ABEfromLWE：unboundedattributesandsemi-adaptivesecurityC/InternationalCryptologyConference（CRYPTO2022）.SantaBarbara：Springer，2022：363-384.28AGRAWALS，MAITRAM，YAMADAS.Attributebasedencryption（andmore）fornondeterministicfiniteautomatafromLWEC/International

53、CryptologyConference（CRYPTO2022）.SantaBarbara：Springer，2022：765-797.29TSABARYR.Fullysecureattribute-basedencryptionfor-CNFfromLWEC/InternationalCryptologyConference（CRYPTO2022）.SantaBarbara：Springer，2022：62-85.30RIVESTRL，ADLEMANL，DERTOUZOSML.OndatabanksandprivacyhomomorphismsJ.FoundationsofSecureCom

54、putation，1978，4（11）：169-180.31GENTRYC.FullyhomomorphicencryptionusingideallatticesC/SymposiumonTheoryofComputing（STOC2022）.Bethesda：ACM，2022：169-178.32BRAKERSKIZ，VAIKUNTANATHANV.Efficientfullyhomomorphicencryptionfrom（standard）LWEC/FoundationsofComputerScience（FOCS2022）.PalmSprings：IEEE，2022：97-106.

55、33BRAKERSKIZ，GENTRYC，VAIKUNTANATHANV.（Leveled）FullyhomomorphicencryptionwithoutbootstrappingC/InnovationsinTheoreticalComputerScience（ITCS2022）.Cambridge：ACM，2022：309-325.34GENTRYC，SAHAIA，WATERSB.Homomorphicencryptionfromlearningwitherrors，conceptually-simpler，asymptotically-faster，attribute-basedC/

56、InternationalCryptologyConference（CRYPTO2022）.SantaBarbara：Springer，2022：75-92.35ALPERIN-SHERIFFJ，PEIKERTC.FasterbootstrappingwithpolynomialerrorC/InternationalCryptologyConference（CRYPTO2022）.SantaBarbara：Springer，2022：297-314.36BRAKERSKIZ，VAIKUNTANATHANV.Lattice-basedFHEassecureasPKEC/Innovationsi

57、nTheoreticalComputerScience（ITCS2022）.Princeton：ACM，2022：1-12.37HIROMASAR，ABEM，OKAMOTOT.PackingmessagesandoptimizingbootstrappinginGSW-FHEC/PublicKeyCryptography（PKC2022）.Washington：Springer，2022：699-715.38DUCASL，MICCIANCIOD.FHEW：bootstrappinghomomorphicencryptioninlessthanasecondC/InternationalConf

58、erenceontheTheoryandApplicationsofCryptographicTechniques（EUROCRYPT2022）.Sofia：Springer，2022：617-640.39CHILLOTTII，GAMAN，GEORGIEVAM，etal.Fasterfullyhomomorphicencryption：bootstrappinginlessthan0.1secondsC/InternationalConferenceontheTheoryandApplicationofCryptologyandInformationSecurity（ASIACRYPT2022

59、）.Hanoi：Springer，2022：3-33.40CHILLOTTII，GAMAN，GEORGIEVAM，etal.FasterpackedhomomorphicoperationsandefficientcircuitbootstrappingforTFHEC/InternationalConferenceontheTheoryandApplicationofCryptologyandInformationSecurity（ASIACRYPT2022）.HongKong：Springer，2022：377-408.41LPEZ-ALTA，TROMERE，VAIKUNTANATHANV

60、.On-the-flymultipartycomputationonthecloudviamulti-keyfullyhomomorphicencryptionC/SymposiumonTheoryofComputing（STOC2022）.NewYork：ACM，2022：1219-1234.42CLEARM，MCGOLDRICKC.Multi-identityandMulti-keyleveledFHEfromlearningwitherrorsC/InternationalCryptologyConference（CRYPTO2022）.SantaBarbara：Springer，202