1.4 基于格的后量子密碼

在現(xiàn)有的后量子密碼方案中，格密碼（Lattice-Based Cryptography，LBC）依靠獨(dú)特的困難問(wèn)題規(guī)約結(jié)果，被認(rèn)為是最有可能成為下一代公鑰密碼標(biāo)準(zhǔn)的新型密碼結(jié)構(gòu)，引起了很多研究者的高度關(guān)注和重視。格的概念最早由Guass于18世紀(jì)提出，后經(jīng)過(guò)Lageange等人的發(fā)展，逐漸形成了一套關(guān)于格的數(shù)學(xué)理論[8]。在相當(dāng)長(zhǎng)的一段時(shí)間內(nèi)，密碼界的研究者更側(cè)重于研究解決格困難問(wèn)題的算法和格理論在密碼分析中的應(yīng)用[9]。在密碼學(xué)中，格理論最初僅僅是一種對(duì)公鑰密碼算法進(jìn)行安全性分析的工具。1996年，Ajtai開(kāi)創(chuàng)性地提出了一種構(gòu)造一類(lèi)隨機(jī)格的方法，給出了格困難問(wèn)題從最壞情況到平均情況的規(guī)約證明[31]。基于Ajtai的這項(xiàng)研究，研究者隨后便開(kāi)始利用隨機(jī)格構(gòu)建單向陷門(mén)函數(shù)、公鑰加密、抗碰撞的哈希函數(shù)和數(shù)字簽名等一系列的密碼方案。1997年，Ajtai和Dwork提出了具有里程碑意義的首個(gè)基于格的公鑰加密方案——Ajtai-Dwork密碼體制[32]。該方案的安全性規(guī)約工作于2003年得到了Regev的完善[33]。同年，Goldreich、Goldwasser和Halevi等人提出了更易理解且實(shí)用的GGH密碼體制。這是一種基于格的公鑰加密和數(shù)字簽名方案，缺點(diǎn)是缺少最壞情況下的安全性證明[34]。盡管后來(lái)Micciancio改進(jìn)了GGH密碼體制[35]，但它的安全性問(wèn)題仍然沒(méi)有得到解決。1998年，Hoffstein等人首次提出了NTRU[36]這一使用多項(xiàng)式環(huán)設(shè)計(jì)的密碼體制，全面優(yōu)化了加解密速度和密鑰長(zhǎng)度。盡管NTRU密碼體制的設(shè)計(jì)利用了格的結(jié)構(gòu)性，但無(wú)法找到已知的格困難問(wèn)題進(jìn)行嚴(yán)格的安全性規(guī)約分析。

使得格密碼真正意義上同時(shí)兼顧實(shí)用性、高效率和可證明安全性的研究工作來(lái)自Regev于2005年發(fā)表的論文[37]。Regev給出了第一個(gè)基于誤差學(xué)習(xí)（Learning With Errors，LWE）問(wèn)題構(gòu)造的公鑰加密方案，標(biāo)志著格密碼進(jìn)入了一個(gè)全新的時(shí)期。2010年，V.Lyubashevsky和C.Peikert等人進(jìn)一步基于環(huán)域上的LWE（Ring-LWE）問(wèn)題設(shè)計(jì)了Ring-LWE公鑰加密方案[38]，有效緩解了LWE公鑰加密方案中過(guò)大的密鑰尺寸而帶來(lái)的存儲(chǔ)問(wèn)題。2011年，R.Lindner和C.Peikert對(duì)Ring-LWE公鑰加密方案進(jìn)行了更為全面的安全性分析，平衡了算法的時(shí)間復(fù)雜度，給出了不同安全等級(jí)下安全參數(shù)的計(jì)算，使得基于Ring-LWE問(wèn)題設(shè)計(jì)的格密碼方案有更加易于實(shí)現(xiàn)的密鑰和密文尺寸[39]。2017年，Albrecht等人給出了MLWE到RLWE的規(guī)約證明[16]，為基于MLWE問(wèn)題構(gòu)建密碼方案的安全性提供了理論基礎(chǔ)。LWE問(wèn)題及其變體一直都是格密碼學(xué)中最為熱門(mén)的研究領(lǐng)域。研究者基于LWE問(wèn)題及其變體構(gòu)建了許多公鑰密碼方案，包括公鑰加密方案[17-18]、密鑰交換協(xié)議（如NewHope[19]、Frodo[20]、Kyber[21]）、數(shù)字簽名方案[22-23]和偽隨機(jī)數(shù)生成函數(shù)[24-25]等。

基于LWE問(wèn)題及其變體的密碼方案雖然兼具了安全性和高效性，但也存在固有的缺陷。LWE方案的安全性主要依賴(lài)向公鑰和密文引入隨機(jī)、獨(dú)立的誤差。該誤差來(lái)自對(duì)噪聲分布的采樣。這就導(dǎo)致基于LWE問(wèn)題及其變體的方案始終存在公鑰和密文體積較大的問(wèn)題，在實(shí)現(xiàn)時(shí)需要消耗大量的存儲(chǔ)空間和帶寬來(lái)保存和傳輸數(shù)據(jù)。為了解決這個(gè)問(wèn)題，Banerjee等人于2012年提出了帶舍入學(xué)習(xí)困難（Learning With Rounding，LWR）問(wèn)題，并證明在特定的參數(shù)選取下，LWR問(wèn)題和LWE問(wèn)題的復(fù)雜度等價(jià)[26]。在此基礎(chǔ)上，Alwen[27]、Bogdanov[28]和Alperin-Sheriff[29]等人陸續(xù)對(duì)LWR問(wèn)題的安全性進(jìn)行了進(jìn)一步的證明。LWR問(wèn)題可以看作LWE問(wèn)題的“去隨機(jī)化版本”。與LWE問(wèn)題不同的是，LWR問(wèn)題中的誤差是通過(guò)模域的轉(zhuǎn)換結(jié)合四舍五入運(yùn)算而確定性地引入的。這種方法避免了向每個(gè)樣本的內(nèi)積添加隨機(jī)誤差項(xiàng)，減小了公鑰和密文的體積。LWR問(wèn)題也演變出RLWR問(wèn)題和MLWR問(wèn)題等變體，均可以看作LWE體系中對(duì)應(yīng)問(wèn)題的衍生。LWR問(wèn)題及其變體的提出為格密碼方案的設(shè)計(jì)提供了新的思路，但由于LWR問(wèn)題特殊的參數(shù)選取導(dǎo)致了一些能夠應(yīng)用到LWE問(wèn)題中的高效數(shù)學(xué)算法，如NTT變換，無(wú)法應(yīng)用到LWR問(wèn)題中，以至于基于LWR問(wèn)題的密碼方案面臨運(yùn)算效率較低的問(wèn)題。在相當(dāng)長(zhǎng)的一段時(shí)間內(nèi)，基于LWR問(wèn)題構(gòu)建密碼算法并不屬于格密碼學(xué)中熱門(mén)的研究?jī)?nèi)容。隨著許多優(yōu)化方法的提出和一些優(yōu)秀的實(shí)現(xiàn)實(shí)例的證明，這種狀況正在逐漸發(fā)生改變。

隨著格密碼的不斷發(fā)展，公鑰長(zhǎng)度與密文長(zhǎng)度得到了更好的優(yōu)化，運(yùn)算性能得到了全面的提升，安全性分析也更加完備。具體而言，格密碼的優(yōu)點(diǎn)主要體現(xiàn)在三個(gè)方面：

（1）擁有完備的安全性證明。當(dāng)前的格密碼方案主要是基于SIS、LWE、Ring-LWE和Module-LWE等問(wèn)題構(gòu)建的，其安全性均已被證明建立在解決最壞情況下最短向量問(wèn)題（Shortest Vector Problem，SVP）和最短線性無(wú)關(guān)向量問(wèn)題（Shortest Independent Vector Problem，SIVP）等格困難問(wèn)題的困難程度上。

（2）高效且易于實(shí)現(xiàn)。格密碼方案通常僅需要十幾位的向量、矩陣和多項(xiàng)式模運(yùn)算，相較于RSA、ECC等需要幾百位以上的大數(shù)模乘、模冪運(yùn)算的密碼方案，更易于實(shí)現(xiàn)。格密碼方案的運(yùn)算流程簡(jiǎn)單，有更高的運(yùn)算速度。

（3）靈活性強(qiáng)，用途廣泛。格密碼的安全參數(shù)易于設(shè)計(jì)并選取，能被廣泛應(yīng)用于多樣化、具有不同安全需求的密碼系統(tǒng)。另外，格密碼不僅可以用于構(gòu)造公鑰加密、密鑰封裝機(jī)制和數(shù)字簽名等方案，還能用于構(gòu)建單向陷門(mén)函數(shù)（Trapdoor Functions）、屬性加密方案（Attribute-Based Encryption）和同態(tài)加密方案（Homomorphic Encryption）等高級(jí)密碼學(xué)應(yīng)用。

表1-3中列出了NIST PQC項(xiàng)目中各類(lèi)后量子密碼方案的實(shí)際性能及數(shù)量的具體對(duì)比。可以看到，在眾多的后量子密碼方案中，基于格的后量子密碼方案，即格密碼方案，憑著自身眾多優(yōu)異的特點(diǎn)，在NIST PQC項(xiàng)目的三輪評(píng)選中方案總數(shù)始終保持第一，毫無(wú)疑問(wèn)地成為最有潛力的一類(lèi)后量子密碼方案。目前，在經(jīng)過(guò)第三輪PQC標(biāo)準(zhǔn)化會(huì)議的評(píng)審后，剩余的7個(gè)主選方案中，基于格的方案有CRYSTALS-KYBER（簡(jiǎn)稱(chēng)Kyber）、NTRU（Theory Research Unit）、SABER（也稱(chēng)Saber）、FALCON和CRYSTALS-DILITHIUM等5個(gè)，占據(jù)了絕大多數(shù)；基于編碼的方案為Classic McEliece；基于多變量的方案為Rainbow。

表1-3 后量子密碼方案對(duì)比

后量子時(shí)代下的信息安全如圖1-3所示。可以預(yù)見(jiàn)，在傳統(tǒng)公鑰密碼體制面臨安全隱患的未來(lái)，從無(wú)處不在的物聯(lián)網(wǎng)終端設(shè)備到超大規(guī)模的云計(jì)算平臺(tái)、智能電網(wǎng)、工業(yè)應(yīng)用、車(chē)輛聯(lián)網(wǎng)、醫(yī)學(xué)檢測(cè)等，都有望部署格密碼來(lái)保障后量子時(shí)代下的信息安全。

圖1-3 后量子時(shí)代下的信息安全