梁志闖 鄭婕妤 趙運(yùn)磊,2

1（復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 200433）

2（密碼科學(xué)技術(shù)國家重點(diǎn)實(shí)驗(yàn)室 北京 100036）

（zcliang21@m.fudan.edu.cn）

密碼學(xué)是現(xiàn)代網(wǎng)絡(luò)安全的基石.現(xiàn)階段廣泛使用的公鑰密碼體制，如公鑰加密、密鑰封裝、數(shù)字簽名等，多數(shù)是基于經(jīng)典的困難問題構(gòu)造的，如求解大整數(shù)分解、（橢圓）離散對數(shù)等困難問題.這些密碼方案在當(dāng)今互聯(lián)網(wǎng)協(xié)議，如SSL/TLS，?PSec 等中扮演了無可替代的角色，如保證通信內(nèi)容的機(jī)密性、通信雙方的身份認(rèn)證、消息的完整性等.盡管針對這些數(shù)論問題目前最好的經(jīng)典求解算法的時間復(fù)雜度是指數(shù)或亞指數(shù)級別，至少是超多項(xiàng)式級別的，但近些年來隨著量子計(jì)算的飛速發(fā)展，已有相關(guān)研究表明存在多項(xiàng)式時間的量子算法可以完全求解它們.例如，美國科學(xué)家Shor[1]提出可在量子計(jì)算機(jī)中以多項(xiàng)式時間求解大整數(shù)分解和（橢圓）離散對數(shù)問題的量子算法.量子計(jì)算相關(guān)技術(shù)的發(fā)展日新月異.考慮到量子計(jì)算技術(shù)對現(xiàn)有公鑰密碼的顛覆性威脅，目前很多國家、公司和學(xué)術(shù)界已提前研究和布局能夠抵抗量子攻擊的密碼學(xué)—后量子密碼學(xué)（post-quantum cryptography，PQC）.

事實(shí)上，早在2016 年，美國國家標(biāo)準(zhǔn)技術(shù)研究所（National ?nstitute of Standards and Technology，N?ST）已經(jīng)正式開啟了對公鑰加密（public key encryption，PKE）方案、密鑰封裝方案（key encapsulation mechanism，KEM）和數(shù)字簽名這3 種密鑰原語的后量子密碼方案標(biāo)準(zhǔn)征集活動，且目前已經(jīng)評選出第3輪結(jié)果并選定擬標(biāo)準(zhǔn)化的方案[2].我國也在2019 年舉行后量子密碼算法競賽，并于2020 年評選出獲獎方案[3].

目前，后量子密碼學(xué)的類型主要分為：基于哈希的、基于多變量的、基于同源的、基于編碼的以及基于格的.其中基于格構(gòu)造的后量子密碼方案不僅具有平均情形到最糟情形的困難性規(guī)約，還在安全性、通信帶寬和計(jì)算效率等方面表現(xiàn)均衡.在美國N?ST和我國舉辦的后量子密碼方案征集活動中，基于格的密碼方案占據(jù)多數(shù).例如，N?ST 第1 輪64 個方案中的26 個[4]、第2 輪26 個方案中的12 個[5]、第3 輪15 個方案中的7 個[6]以及擬標(biāo)準(zhǔn)化4 個方案中的3個[2]均為基于格構(gòu)造的密碼方案.我國后量子密碼算法設(shè)計(jì)競賽獲獎方案共14 個，其中有11 個均為基于格構(gòu)造的.基于格的方案在設(shè)計(jì)PKE 和KEM 時主要基于一般格、理想格、模格和NTRU 格.常用的格困難問題主要分為2 類：第1 類是{R,M}LWE/LWR 問題[7-10]；第2 類是NTRU 格相關(guān)問題[11-13].

NTRU 最早由Hoffstein 等人[14]于1996 年美密會討論環(huán)節(jié)中提出，但它在1997 年遭遇格攻擊[15].隨后Hoffstein 等人對方案安全性方面進(jìn)行補(bǔ)救，并于1998 年正式提出NTRU 加密方案（NTRU-HPS）[11].該方案是第1 個基于格困難問題構(gòu)造的現(xiàn)實(shí)的公鑰加密方案.NTRU 相關(guān)問題目前已經(jīng)是許多密碼方案中的基礎(chǔ)元件[16-18].在N?ST 的后量子密碼方案征集項(xiàng)目中，基于NTRU 格的方案具有舉足輕重的地位.具體而言，F(xiàn)alcon 數(shù)字簽名[19]基于NTRU 格構(gòu)造，且是N?ST 后量子密碼方案標(biāo)準(zhǔn)征集擬標(biāo)準(zhǔn)化的數(shù)字簽名之一.另外，在N?ST 第3 輪中，NTRU KEM[20]（包含NTRU-HRSS 和NTRUEncrypt）是4 個決賽KEM 方案之 一，NTRU Prime KEM[21]（包 含SNTRU Prime 和NTRU LPRime）是5 個候選方案之一.盡管目前N?ST 選擇了基于模格的Kyber[22]作為唯一的擬標(biāo)準(zhǔn)化KEM方案[2]，而基于NTRU 格的方案沒能被N?ST 選為擬標(biāo)準(zhǔn)化KEM 方案，但N?ST 官方報(bào)告聲稱如果Kyber相關(guān)專利問題未能得到很好地解決，仍可能會放棄Kyber 而啟用NTRU KEM[23].另外，在2011 年NTRUEncrypt 方案便已入選X9.98 標(biāo)準(zhǔn)并應(yīng)用于金融服務(wù)企業(yè)之中[24].自2022 年4 月起，國際標(biāo)準(zhǔn)OpenSSH更新了版本9.0 之后，OpenSSH 便采用了NTRU Prime KEM 方案結(jié)合X25519 ECDH 方案的混合模式，以抵抗“先捕獲后解密”攻擊[25].另外，有關(guān)基于NTRU 格的方案的研究并不應(yīng)因此而止步不前，對基于NTRU格的方案的設(shè)計(jì)和分析理應(yīng)得到更充分、深入和全面的研究.

基于NTRU 格設(shè)計(jì)的KEM 備受青睞，主要原因有3 點(diǎn)：1）基于NTRU 格的KEM 具有堅(jiān)固的安全保障.自NTRU 被提出至今，有關(guān)NTRU 的攻擊和密碼分析對基于NTRU 格的KEM 安全性產(chǎn)生的影響非常有限.事實(shí)上，大多數(shù)基于NTRU 相關(guān)困難問題設(shè)計(jì)的密碼方案至今沒被攻破.2）有關(guān)NTRU 的專利已失效.在1997 年，NTRU 加密系統(tǒng)獲得了專利，但在2017 年NTRU 相關(guān)核心專利已到期.3）大多數(shù)基于NTRU 格的KEM 結(jié)構(gòu)簡單，便于實(shí)現(xiàn)，同時加解密算法的運(yùn)算速度快[20-21].

近些年來，針對基于NTRU 格的KEM 有2 點(diǎn)可優(yōu)化的方向：

1）計(jì)算效率方面.基于NTRU 格的KEM 如NTRUHRSS[20]和SNTRU Prime[21]在計(jì)算效率方面遜色于基于{R,M}LWE 的方案.主要是因?yàn)楹笳吣軌蚴褂酶咝У臄?shù)論變換（number theoretic transform，NTT）來計(jì)算多項(xiàng)式乘法.近些年來，文獻(xiàn)[26-27]基于NTT 友好的多項(xiàng)式環(huán)來構(gòu)造出基于NTRU 格的KEM，使得方案中的多項(xiàng)式運(yùn)算得到高效計(jì)算.

2）密文尺寸方面.降低密文尺寸對網(wǎng)絡(luò)協(xié)議，如TLS 和?oT 資源受限設(shè)備通信都具有積極的作用.盡管密文壓縮在基于LWE 及其變體的KEM 中是一項(xiàng)成熟的技術(shù)，但對基于NTRU 格的KEM 來說，目前相關(guān)研究極少.常見的NTRU 的加密方案的密文形式一般為c=phr+mmodq，其中h為公鑰（一般h=g/f），q為方案模數(shù)，g、f為秘密多項(xiàng)式；r為采樣得到的秘密多項(xiàng)式，m為待加密的明文，p為明文空間模數(shù).這可視為m通過編碼到密文c的低位.解密算法將c乘以私鑰f，得到cfmodq=pgr+mf.隨后通過乘f的逆，或當(dāng)f=pf′+1 時可通過模p消除雜項(xiàng)來恢復(fù)明文.這種解密機(jī)制要求被消除的雜項(xiàng)為p的倍數(shù).所以一旦密文c被壓縮，壓縮帶來的誤差往往集中在c的低位，從而破壞m的有效信息，此時便無法正確解密得到原始的m.

文獻(xiàn)[28-29]對基于NTRU 格的KEM 的密文壓縮進(jìn)行了探索，但是文獻(xiàn)[28-29]的方案有2 點(diǎn)不足.第1 點(diǎn)不足是這些方案都基于2 種困難性假設(shè)來構(gòu)建KEM.其中文獻(xiàn)[28]是基于NTRU 假設(shè)[11]和RLWE 假設(shè)[9]，文獻(xiàn)[29]是基于NTRU 假設(shè)和RLWR假設(shè)[8].引入過多的困難性假設(shè)會導(dǎo)致方案建立在更理想化的假設(shè)上.同時，分析這些方案的安全強(qiáng)度則需要分析2 種困難性問題的安全強(qiáng)度，并取2 個安全強(qiáng)度的最小值.所以，方案的安全性很大程度上取決于安全強(qiáng)度更低的困難性問題.NTRU 相關(guān)困難問題的安全性經(jīng)過20 多年的密碼分析現(xiàn)今仍然安全；RLWE 和RLWR 是較之更新的問題而需要進(jìn)一步密碼分析和驗(yàn)證.為得到更為穩(wěn)定的安全保障，僅基于NTRU 相關(guān)困難問題設(shè)計(jì)的KEM 值得深入地研究和探索.第2 點(diǎn)不足是文獻(xiàn)[28-29]的方案均使用糾錯碼和復(fù)雜的糾錯機(jī)制來恢復(fù)明文信息.其中文獻(xiàn)[28]使用可尺度E8格糾錯碼；文獻(xiàn)[29]使用改進(jìn)的Babai算法.盡管糾錯碼具有良好的糾錯能力從而有效恢復(fù)信息，但是KEM 使用糾錯碼會帶來2 個缺點(diǎn)：1）糾錯碼增加了方案遭遇側(cè)信道攻擊的風(fēng)險(xiǎn)[30]，特別是計(jì)時攻擊[31]；2）糾錯碼導(dǎo)致實(shí)現(xiàn)更復(fù)雜、更耗時，且更容易出錯.為了設(shè)計(jì)更安全且便于實(shí)現(xiàn)的KEM，設(shè)計(jì)者應(yīng)該避免使用糾錯碼.所以，對基于NTRU 格的KEM 來說，在不使用糾錯碼的情況下，如何得到可壓縮密文的構(gòu)造依然需要進(jìn)一步探索.

在我國，后量子密碼被我國科協(xié)列為60 個我國亟待解決的重大科技難題之一.盡管我國2019 年密碼算法設(shè)計(jì)競賽的獲獎方案大多數(shù)是基于格構(gòu)造的，且包含基于NTRU 格的FatSeal 簽名[3]，但是在它們之中并沒有基于NTRU 格的PKE 和KEM.在當(dāng)前國內(nèi)外網(wǎng)絡(luò)空間安全愈發(fā)重要的大背景下，我國研究團(tuán)隊(duì)理應(yīng)自主研制高性能、多樣化的后量子密碼方案.考慮到基于NTRU 格的方案在國際上（特別是N?ST后量子密碼標(biāo)準(zhǔn)征集項(xiàng)目）的重要地位，本文主要關(guān)注基于NTRU 格構(gòu)造高效的PKE 和KEM，并針對目前可優(yōu)化方向，如計(jì)算效率方面和密文尺寸方面，提出一套基于NTRU 格構(gòu)造的可壓縮密文的實(shí)用化公鑰密碼系統(tǒng).本文旨在為后續(xù)同類后量子密碼方案的研究和優(yōu)化提供重要參考.同時，這方面的研究工作對我國未來的后量子密碼標(biāo)準(zhǔn)的選拔、制定、推廣和實(shí)際應(yīng)用都具有重要的現(xiàn)實(shí)意義.

本文的貢獻(xiàn)主要有4 點(diǎn)：

1）基于NTT 友好環(huán) Zq[x]/(xn-xn/2+1)構(gòu)造了一個基于NTRU 格的可壓縮密文的密鑰封裝方案LTRU.該方案包含了?ND-CPA 安全的公鑰加密方案LTRU.PKE 和?ND-CCA 安全的密鑰封裝方案LTRU.KEM.本文的LTRU 僅基于NTRU 單向困難性假設(shè)構(gòu)建.LTRU 能夠避免引入過多假設(shè)，從而避免方案假設(shè)過強(qiáng)和過于理想化.同時LTRU 不使用糾錯碼，從而實(shí)現(xiàn)更簡單，且降低了遭遇側(cè)信道攻擊的風(fēng)險(xiǎn).已知LTRU 是第1 個僅基于NTRU 類型假設(shè)且不使用糾錯碼也能壓縮密文的密鑰封裝方案.

2）提供了針對128 b 安全強(qiáng)度的LTRU 參數(shù)集.這使得LTRU 不僅達(dá)到了目標(biāo)安全強(qiáng)度（實(shí)際上達(dá)到129 b 量子安全強(qiáng)度），還具有與安全性匹配的、可忽略的錯誤率（2-154），同時通信帶寬小于其他NTRU方案.具體而言，與N?ST 第3 輪決賽方案NTRUHRSS 相比，LTRU 的經(jīng)典安全強(qiáng)度和量子安全強(qiáng)度分別增強(qiáng)6 b 和5 b，并且LTRU 的公鑰尺寸降低14.6%，密文尺寸降低26.0%，總帶寬降低20.3%.

3）提出了一種高效的混合基NTT 算法.該算法能夠有效計(jì)算環(huán) Z2917[x]/(x648-x324+1)上的多項(xiàng)式運(yùn)算，利用3 次單位根的性質(zhì)來有效減少基-3 FFT trick步驟中一半的乘法數(shù)量，并利用1-迭代Karatsuba 算法來有效減少點(diǎn)乘中的乘法數(shù)量.通過具體實(shí)現(xiàn)的效率分析可知，跟未使用1-迭代Karatsuba 算法和單位根的性質(zhì)優(yōu)化乘法數(shù)量的NTT 算法相比，本文NTT 在正向變換、點(diǎn)乘和逆向變換的CPU 周期數(shù)分別降低24.9%，20.6%，26.8%，總共降低25.3%.

4）提供LTRU 的C 實(shí)現(xiàn)和AVX2 實(shí)現(xiàn).實(shí)驗(yàn)結(jié)果表明，與NTRU-HRSS 的AVX2 實(shí)現(xiàn)相比，LTRU在密鑰生成和解封裝算法上分別快了10.9 倍和1.7倍，封裝算法的速度則與NTRU-HRSS 的速度相當(dāng).

1 相關(guān)工作

近些年來，陸續(xù)有基于NTRU 格的方案被提出.Stehlé等人[32]基于2 次冪分圓環(huán) Z[x]/(xn+1)（其中n為2 次冪）來設(shè)計(jì)基于NTRU 變體的PKE，并證明了公鑰的安全性.隨后，Wang 等人[33]將該方案推廣至任意的分圓環(huán).但是這2 個方案因?yàn)楣€尺寸過大而無法應(yīng)用于實(shí)際的場景中.Jarvis 等人[34]將NTRUHPS 推廣至Eisenstein 整數(shù)環(huán) Z[ω]/(xn-1)（其中ω=exp(2π i/3)）.該方案在密鑰尺寸和性能方面比NTRU-HPS 更有優(yōu)勢.Hülsing 等人[35]全面提升NTRUHPS 的密鑰尺寸、密文尺寸和效率，并提出了NTRUHRSS.NTRU-HRSS 曾是N?ST 后量子方案征集項(xiàng)目第3 輪決賽方案之一[20].Bernstein 等人[36]考慮到NTRU 類型方案使用的多項(xiàng)式環(huán)或因豐富的代數(shù)結(jié)構(gòu)而遭受相關(guān)攻擊，提出了使用代數(shù)結(jié)構(gòu)更少的環(huán)Zq[x]/(xn-x-1)的NTRU 變體方案：NTRU Prime（其中n,q均為素?cái)?shù)）.NTRU-prime 曾是N?ST 后量子方案征集項(xiàng)目第3 輪候選方案之一[20].

為了追求更高的實(shí)現(xiàn)效率，Lyubashevsky 等人[26]在多項(xiàng)式環(huán) Z7681[x]/(x768-x384+1)上構(gòu)造了針對128 b安全強(qiáng)度的NTTRU 方案.隨后，Duman 等人[27]將該方案推廣至更一般的n并選擇對應(yīng)的q.但是這些方案均是遵循傳統(tǒng)NTRU 的框架，并不能對密文進(jìn)行壓縮.

Fouque 等人[29]提出BAT 方案.BAT 與傳統(tǒng)NTRU類型的KEM 的構(gòu)造有所區(qū)別，但與Falcon 數(shù)字簽名方案[19]有眾多相似之處.BAT 的私鑰是一組陷門基，這一點(diǎn)與Falcon 相似，但區(qū)別于其他NTRU 類型KEM 的私鑰f.直觀地理解，BAT 使用的糾錯碼機(jī)制相當(dāng)于對含有2 個未知數(shù)的方程求解出秘密多項(xiàng)式和噪音多項(xiàng)式，并用來恢復(fù)明文.BAT 通過將密文構(gòu)造為RLWR 實(shí)例的方式來降低密文的尺寸.然而，為生成陷門基作為私鑰，BAT 的密鑰生成算法速度比常見的NTRU 類型KEM 的速度慢約1 000 倍.其次，為降低密文尺寸而構(gòu)造的RLWR 實(shí)例使用二元的秘密分布（即秘密多項(xiàng)式的系數(shù)選自{0,1}），而關(guān)于該問題的安全性目前還是公開問題且還需要進(jìn)一步研究.另外，BAT 缺少匹配128 b 安全強(qiáng)度的參數(shù)集，因?yàn)樗褂? 次冪分圓環(huán) Z[x]/(xn+1)，且n=512和n=1 024，而前者的安全強(qiáng)度略低于128 b，后者的安全強(qiáng)度則遠(yuǎn)高于128 b.

2 預(yù)備知識

本節(jié)主要介紹一些符號說明、基本定義和密碼原語等.

2.1 符號說明和基本定義

1）本文記 Z 為整數(shù)環(huán)，n和q為 某些整數(shù).定 義集合Zq=Z/qZ ?{0,1,…,q-1}.對 于實(shí)數(shù)x∈R，符 號表示對x四舍五入后的值.本文主要使用分圓多項(xiàng)式環(huán) R:=Z[x]/(xn-xn/2+1) 及其商環(huán)Rq:=R/qR=Zq[x]/(xn-xn/2+1)，其中n=2i3j，i≥0，j＞1，且此時xn-xn/2+1是 3n階分圓多項(xiàng)式.環(huán) R（或 Rq）中的元素均是多項(xiàng)式，本文使用符號f的冪級數(shù)形式（或fi∈Zq）.一個函數(shù) ε:N →[0,1]是可忽略的，指的是對任意的正數(shù)c以及充分大的 λ，ε(λ)＜1/λc成立.

2）模約減.對于某正整數(shù)q，符號r′=rmodq表示r落在 [0,q)∩Z 中的代表元r′.符號r′=rmod±q表示r落在中的代表元r′.另外，符號r′≡rmodq′表示r′和r模q同余.

3）元素的范數(shù)[37].對于元素v∈Zq，定義它的?∞范數(shù) ‖v‖∞為 ||vmod±q||.對于環(huán) R（或 Rq）中的元素w，它的 ?∞范數(shù)為

4）壓縮函數(shù)和解壓縮函數(shù)[37].對于正整數(shù)q和d，定義壓縮函數(shù)

以及解壓縮函數(shù)

且對于任意的x∈Zq，有

5）集合和分布.對于集合D，記x←$D表示從D中均勻隨機(jī)選 取x.如果D是一個概率分布，x←D表示根據(jù)分布D采樣得到x.本文主要使用的分布為：采樣 (a1,a2,…,aη,b1,b2,…,bη)←${0,1}2η，然后輸出根據(jù)分布D，采樣多項(xiàng)式f指的是f的每一個系數(shù)均根據(jù)D采樣得到.

2.2 密碼原語

1）公鑰加密方案

一個公鑰加密方案PKE 包含KeyGen,Enc,Dec3個概率多項(xiàng)式時間（probabilistic polynomial time，PPT）算法，記其明文空間為 M.密鑰生成算法KeyGen輸出公私鑰對 (pk,sk).加密算法Enc輸入公鑰pk和明文m∈M，輸出密文ct.本文在必要時使用Enc(pk,m;coin) 顯式表示加密算法使用的隨機(jī)數(shù)為coin.確定性的解密算法Dec輸入密文ct和私鑰sk，輸出m∈M，或者 ⊥表示解密失敗.公鑰加密方案的解密錯誤率δ定義為

其中期望作用于 (pk,sk)←KeyGen上，式（1）概率取自加密算法Enc使用的隨機(jī)數(shù).一個公鑰加密方案是抗原像恢復(fù)意義下的選擇明文PRE-CPA（preimage resistance under chosen-plaintext attacks）安全的[27]，指的是對于任意PPT 敵手 A，其優(yōu)勢是可忽略的：

一個公鑰加密方案是不可區(qū)分意義下的選擇明文?ND-CPA（indistinguishability under chosen-plaintext attacks）安全的，指的是對于任意PPT 敵手 A，其優(yōu)勢是可忽略的：

2）密鑰封裝方案

一個密鑰封裝方案KEM 包含KeyGen,Encaps,Decaps3 個PPT 算法.記其導(dǎo)出密鑰空間為 K.密鑰生成算法KeyGen輸出公私鑰對 (pk,sk).密鑰封裝算法Encaps輸入公鑰pk，輸出密文ct和密鑰K∈K.確定性的解封裝算法Decaps輸入密文ct和私鑰sk，輸出K∈K，或者 ⊥表示解封裝失敗.密鑰封裝方案的錯誤率 δ定義為Pr[Decaps(sk,ct)≠K:(ct,K)←Encaps(pk)]＜δ，其中概率取自 (pk,sk)←KeyGen和封裝算法Encaps使用的隨機(jī)數(shù).一個密鑰封裝方案是不可區(qū)分意義下的選擇密文?ND-CCA（indistinguishability under chosenciphertext attacks）安全的，指的是對于任意PPT 敵手A，其優(yōu)勢是可忽略的：

2.3 NTRU 單向困難性假設(shè)

定義1.NTRU 單向困難性假設(shè)[12-13].給定NTRU公鑰加密方案的公鑰h以及PPT 加密算法Enc，則NTRU 單向函數(shù)是指

其中Enc(h,(r,e)) 指的是以h，e，r作為加密算法的輸入，在NTRU 公鑰加密方案中 Le一般是它的明文空間，Lr一般是它的隨機(jī)數(shù)空間.

NTRU 單向問題NTRU-OW（NTRU one-wayness）指的是給定公鑰h和密文多項(xiàng)式c，計(jì)算得到 (r,e).NTRU 單向問題是困難的，指的是對于任意PPT 敵手A，其優(yōu)勢是可忽略的：

通俗來講，NTRU 單向困難性假設(shè)是指沒有PPT敵手能夠從公鑰h和密文c中恢復(fù)出 (r,e).原始的NTRU-HPS 方案[11]便蘊(yùn)含了NTRU 單向困難性假設(shè)，直到文獻(xiàn)[12-13]將NTRU 單向困難性假設(shè)提煉出來，并應(yīng)用在基于NTRU 格的方案（如NAEP 方案）的安全性證明之中.

2.4 ACWC0 轉(zhuǎn)換

定義2.ACWC0轉(zhuǎn)換[27].記PKE1=（KeyGen1,Enc1,Dec1）為公鑰加密方案，其明文空間記為 M1.令F :{0,1}*→{0,1}λ為哈希函數(shù)，λ為某正整數(shù).ACWC0通過算法1～3 將PKE1=（KeyGen1,Enc1,Dec1）轉(zhuǎn)換得到另一個公鑰加密方案PKE2=（KeyGen2,Enc2,Dec2），其明文空間為 M2={0,1}λ.

算法1.密鑰生成算法KeyGen2.

根據(jù)文獻(xiàn)[27]中的引理2.2 和定理3.3，PKE2方案在隨機(jī)預(yù)言機(jī)模型（random oracle model，ROM）[38]下的?ND-CPA 安全性由定理1 給出.

定理1.在隨機(jī)預(yù)言機(jī)模型下，對于任意的攻擊PKE2的?ND-CPA 安全性的敵手 A，存在攻擊PKE1的PRECPA 安全性的敵手 B，其運(yùn)行時間與 A相當(dāng)，使得

另外，根據(jù)文獻(xiàn)[27]中的引理2.2 和定理3.4，可得定理2 關(guān)于PKE2方案在量子隨機(jī)預(yù)言機(jī)模型（quantum random oracle model，QROM）[39]下 的?NDCPA 安全性.

定理2.在量子隨機(jī)預(yù)言機(jī)模型下，對于任意的攻擊PKE2的?ND-CPA 安全性的量子敵手 A，存在攻擊PKE1的PRE-CPA 安全性的量子敵手 B，其運(yùn)行時間與 A相當(dāng)，使得

其中dF是 A 查詢 F的深度.

可見，ACWC0轉(zhuǎn)換能夠?qū)⒁粋€PRE-CPA 安全的公鑰加密方案轉(zhuǎn)換得到另一個?ND-CPA 安全的公鑰加密方案.本文將在3.1 節(jié)中提出的公鑰加密方案便是通過ACWC0轉(zhuǎn)換得到的.

2.5 數(shù)論變換（NTT）

NTT 是快速傅里葉變換（fast Fourier transform，F(xiàn)FT）在有限域上的特殊形式.NTT 是計(jì)算高次多項(xiàng)式乘法最高效的算法，其復(fù)雜度為O(nlogn)，其中n為被乘多項(xiàng)式的維度.簡單地說，基于NTT 計(jì)算多項(xiàng)式乘 法h=fg的過程為h=INT T(NT T(f)?NT T(g))，其中 NT T 表示正向變換，INT T 表示逆向變換，“ ?”表示點(diǎn)乘.本文沿用文獻(xiàn)[40]有關(guān)多項(xiàng)式乘法的符號和術(shù)語，F(xiàn)FT trick 是計(jì)算NTT 的一種快速算法，其計(jì)算過程本質(zhì)是基于多項(xiàng)式環(huán)形式的中國剩余定理（Chinese remainder theorem，CRT），即給定兩兩互素的多項(xiàng)式g1,g2,…,gk，有CRT 同構(gòu)

并且 φ(f)=(fmodg1,fmodg2,…,fmodgk).記 ζ 在Zq中可逆.對于經(jīng)典的基-2 FFT trick 的情況，有CRT 同構(gòu)：

其中 ρ是3 次單位根.混合基NTT 指的是在計(jì)算NTT過程含有多種FFT trick.

2.6 Karatsuba 算法

定義3.1-迭代Karatsuba 算法[43].設(shè)a,b,c,d為 某些數(shù)或多項(xiàng)式.1-迭代Karatsuba 算法指的是為了計(jì)算t1=ac，t2=ad+bc和t3=bd，可以先計(jì)算t1和t3，然 后通過t2=(a+b)(c+d)-t1-t3計(jì)算t2.該算法能在增加3 個加（減）法的代價上，減少1 個乘法.

3 本文方案及其分析

下面介紹本文提出的基于NTRU 格構(gòu)造的可壓縮密文的密鑰封裝方案LTRU.LTRU 包括一個?NDCPA 安全的公鑰加密方案LTRU.PKE，以及一個?NDCCA 安全的密鑰封裝方案LTRU.KEM，其中該KEM通過FO（Fujisaki-Okamoto）轉(zhuǎn)換[44-45]得到.LTRU.PKE是由底層公鑰加密方案PKE′=（KeyGen,Enc′,Dec′）結(jié)合文獻(xiàn)[27]的ACWC0轉(zhuǎn)換得到的.底層公鑰加密方案PKE′將在3.4 節(jié)中展示，但它只能滿足PRECPA 安全性，并且目前還沒有相關(guān)文獻(xiàn)論證FO 轉(zhuǎn)換將PRE-CPA 安全的公鑰加密方案轉(zhuǎn)換得到?NDCCA 安全的KEM 的規(guī)約上界.本文通過增加ACWC0轉(zhuǎn)換，將底層公鑰加密方案PKE′轉(zhuǎn)換得到?ND-CPA安全的LTRU.PKE，然后便能通過FO 轉(zhuǎn)換得到?NDCCA 安全的KEM.

3.1 LTRU 的構(gòu)造

LTRU.PKE 的具體構(gòu)造見算法4～6.記其明文空間為 M={0,1}λ，其中 λ 為正整數(shù).記多項(xiàng)式環(huán)為Rq=Zq[x]/(xn-xn/2+1)，其中n和q是環(huán)參數(shù).記d和p為 正整數(shù)，且p和q互素.需要說明的是，在算法4～6 中，為了給出一般的構(gòu)造框架，本文使用的分布 ψ 泛指 R上的某分布，但事實(shí)上，在3.3 節(jié)的具體參數(shù)選擇方面，本文實(shí)例化 ψ 為參數(shù) η=2 的分布（定 義見2.1 節(jié)）.令F :{0,1}*→{0,1}λ為哈希函數(shù).本文主要考慮p=2以及 λ=256 的情況.可 視 {0,1}n中的元素是維度為n、系數(shù)為0 或1 的多項(xiàng)式.壓縮函數(shù)Compress和解壓縮函數(shù)Decompress的具體計(jì)算過程見2.1 節(jié).

算法4.密鑰生成算法LTRU.PKE.KeyGen.

可見，LTRU.PKE 應(yīng)用了ACWC0轉(zhuǎn)換[27]，見算法5 行③以及算法6 行③.LTRU.KEM 是由LTRU.PKE通過轉(zhuǎn)換得到，其中是文獻(xiàn)[45]提出的FO轉(zhuǎn)換的一個變體.LTRU.KEM 的密鑰生成算法KeyGen與LTRU.PKE 的KeyGen相 同.LTRU.KEM 的封裝算法和解封裝算法分別見算法7 和算法8.記K為LTRU.KEM 的導(dǎo)出密鑰空間，為方便起見，本文令K={0,1}256.記 COINS為LTRU 公鑰加密方案中加密算法所使用的隨機(jī)數(shù)空間.記H :{0,1}*→K×COINS為哈希函數(shù).實(shí)際上，H能夠拆分為2 部分 H1和 H2，記 H1為 H 映射到 COINS 的部分，H2為 H 映射到K的部分.在算法7 的行②中可以先使用 H1生成coin，在行③中計(jì)算得到密文c之后，再使用 H2生成共享密鑰K.

算法7.封裝算法LTRU.KEM.Encaps.

算法8.解封裝算法LTRU.KEM.Decaps.

3.2 錯誤率分析

則LTRU 的錯誤率為 δ.

證明.

從2.1 節(jié)的壓縮函數(shù)Compress和解壓縮函數(shù)Decompress的定義可知，算法6 行①的c′可以表示為

由于LTRU 中h=g/f和f=2f′+1，則可得

本文計(jì)算錯誤率的方法論和Python 腳本源自文獻(xiàn)[22,26,37].值得注意的是，文獻(xiàn)[26]將環(huán)Z[x]/(xnxn/2+1) 上的多項(xiàng)式的乘積的系數(shù)視為由n/2個形如ab+b′(a+a′) 的元組構(gòu)成，其中a,a′,b,b′的分布由被乘多項(xiàng)式的分布決定.盡管該環(huán)上的多項(xiàng)式的乘積另外還包含形如ab+a′b′的元組，文獻(xiàn)[26]建議全部使用ab+b′(a+a′)的形式，因?yàn)樵撔问骄哂懈鼘挿旱姆植?，且能得到更保守估?jì)的錯誤率結(jié)果.

3.3 參數(shù)選擇

本節(jié)給出LTRU 的推薦參數(shù)集，其主要針對128 b安全強(qiáng)度，如表1 所示.Rq是多項(xiàng)式環(huán)，維數(shù)n和模數(shù)q是環(huán)參數(shù).本文選擇NTT 友好的q，旨在q允許在Rq上執(zhí)行高效的多項(xiàng)式乘法和除法，具體細(xì)節(jié)見第4 節(jié).p是明文空間模數(shù)；d是壓縮參數(shù)；ψ是概率分布，本文主要考慮分布即參數(shù)為 η=2 的分布，的定義見2.1 節(jié)；|pk|，|ct|，B.W.分別是公鑰尺寸、密文尺寸和帶寬（公鑰尺寸+密文尺寸），單位均為B；Sec-（C,Q）是該參數(shù)集的NTRU 安全強(qiáng)度（單位為b），C 表示經(jīng)典安全強(qiáng)度，Q 表示量子安全強(qiáng)度，安全強(qiáng)度的分析見3.5 節(jié)；δ是該參數(shù)集的錯誤率，其細(xì)節(jié)見3.2 節(jié).

Table 1 Recommended Parameter Set of LTRU表1 LTRU 的推薦參數(shù)集

3.4 安全規(guī)約

下面將基于NTRU 單向困難性假設(shè)，證明LTRU.PKE 是?ND-CPA 安全的.

定理4.?ND-CPA 安全性.對于任意的概率多項(xiàng)式時間敵手 A，存在概率多項(xiàng)式時間敵手 B，其運(yùn)行時間與 A相當(dāng)，使得：

證明.LTRU.PKE 方案由底層公鑰加密方案PKE′=（KeyGen,Enc′,Dec′）結(jié)合文獻(xiàn)[27]的ACWC0轉(zhuǎn)換得到，其中底層公鑰加密方案PKE′的KeyGen算法與LTRU.PKE 方案的一致，Enc′算法和Dec′算法分別見算法9 和算法10.

算法9.加密算法PKE′.Enc′.

算法10.解密算法PKE′.Dec′.

由定理1 和定理2 可知，當(dāng)?shù)讓庸€加密方案PKE′滿足PRE-CPA 安全性時，經(jīng)過ACWC0轉(zhuǎn)換得到的LTRU.PKE 方案滿足?ND-CPA 安全性.下面將通過Game-Hopping 技術(shù)[46]來證明底層公鑰加密方案PKE′的PRE-CPA 安全性.

記 A 是攻擊PKE′方案的PRE-CPA 安全性的概率多項(xiàng)式時間敵手.考慮游戲G0和G1.記事件S ucci為敵手 A 在游戲Gi中獲勝，即游戲Gi的輸出滿足c=c*.

游戲G0是 關(guān)于PKE′方案原始的PRE-CPA 游戲.根據(jù)PRE-CPA 安全性的定義，可知

游戲G1是在游戲G0的基礎(chǔ)上，取消對行⑦挑戰(zhàn)密文c*的壓縮操作.所以，敵手 A 在游戲G1中擁有的挑戰(zhàn)密文的信息至少比在游戲G0中的多.可見，游戲G0的困難性至少與游戲G1的相同，則

整合游戲G0和G1中的概率可知，對于概率多項(xiàng)式時間敵手 A，存在概率多項(xiàng)式時間敵手 B，使得

再根據(jù)定理1 和定理2，由PKE′方案的PRE-CPA 安全性可得到LTRU.PKE 的?ND-CPA 安全性，其對應(yīng)的規(guī)約上界正如定理4 所示.綜上，命題得證.證畢.

從定理4 可知，若NTRU 單向困難性問題是困難的，那么LTRU.PKE 是?ND-CPA 安全的.由于LTRU.KEM 是從?ND-CPA 安全的LTRU.PKE 通 過變換得到，根據(jù)文獻(xiàn)[45,47]，LTRU.KEM 在經(jīng)典隨機(jī)預(yù)言機(jī)和量子隨機(jī)預(yù)言機(jī)下的?ND-CCA 安全性由定理5給出.

定理5.?ND-CCA 安全性[45,47].在記 γ 和 δ分別是LTRU.PKE 的弱spread 參數(shù)[45,47]和解密錯誤率.對于任意攻擊LTRU.KEM 的 ?ND-CCA 安全性的概率多項(xiàng)式時間敵手 A，存在攻擊LTRU.PKE 的?ND-CPA安全性的概率多項(xiàng)式時間敵手 B，使得：

1）在經(jīng)典隨機(jī)預(yù)言機(jī)模型下，將 H建模為經(jīng)典隨機(jī)預(yù)言機(jī)，A查詢至多qH次 H，查詢至多qD次解封裝預(yù)言機(jī)，B的運(yùn)行時間和 A的相當(dāng)，則有

2）在量子隨機(jī)預(yù)言機(jī)模型下，A 和 B為量子敵手，且將 H建模為量子隨機(jī)預(yù)言機(jī)，A以量子方式查詢至多qH次 H，以經(jīng)典方式查詢至多qD次解封裝預(yù)言機(jī)，則有

其中qT:=2(qH+qD)，并且

3.5 安全強(qiáng)度

對于基于NTRU 格構(gòu)造的KEM 來說，格攻擊是目前最有效的攻擊.本節(jié)主要從常用的格攻擊來分析LTRU 的安全強(qiáng)度.

1）NTRU 格

起初，基于NTRU 格構(gòu)造的方案均是依賴于多項(xiàng)式環(huán)上的困難性問題.然而，Coppersmith 等人[15]提出針對基于NTRU 格構(gòu)造方案的格攻擊，它的核心思想是構(gòu)造NTRU 格.本文方案的公鑰對應(yīng)的NTRU格L(B)?Z2n的基矩陣為

其中In是n維單位矩陣，Rot(h)是h的循環(huán)移位矩陣，即它的第i行向量對應(yīng)xihmodxn-xn/2+1.文獻(xiàn)[15]提出，秘密 (f,g) 及其循環(huán)移位向量是格 L(B)的最短向量.事實(shí)上，NTRU 類型方案的格攻擊流程為：通過格基約化算法求解格 L(B)的唯一最短向量問題（unique-short vector problem，u-SVP），找到該最短向量之后轉(zhuǎn)化得到方案的私鑰[15].

2）原始攻擊

原始攻擊通過構(gòu)造一個整數(shù)嵌入格，如Kannan嵌入[48]和Bai-Galbraith 嵌入[49]等來求解u-SVP 問題.目前主要的格基約化算法為BKZ 算法[50-51].給定格L(B)的一組基，BKZ 算法運(yùn)行時將格劃分為多個低維度格，并把這些低維度格的維度記為b.然后在b維格中求解最短向量問題（short vector problem，SVP），所使用的方法有篩法和枚舉.根據(jù)文獻(xiàn)[52]的core-SVP 方法論，對于b維格上求解SVP 問題，目前最優(yōu)的經(jīng)典算法的復(fù)雜度為 20.292b，最優(yōu)的量子算法的復(fù)雜度為 20.265b.core-SVP 方法論將這些復(fù)雜度視為求解b維格SVP 問題的復(fù)雜度，并將得到的BKZ 算法的復(fù)雜度作為原始攻擊的復(fù)雜度估計(jì).本文將基于core-SVP 方法論給本文方案提供一個保守估計(jì)的安全強(qiáng)度，并基于文獻(xiàn)[22,37,52]提供的計(jì)算安全強(qiáng)度的Python 腳本來計(jì)算LTRU 在原始攻擊下的經(jīng)典安全強(qiáng)度和量子安全強(qiáng)度，其詳細(xì)結(jié)果如表1 所示.

3）其他攻擊

對偶攻擊主要通過將判定型LWE 問題規(guī)約為短整數(shù)解問題（short integer solution problem，S?S）的方式來求解判定型LWE 問題.由于對偶攻擊不適用于NTRU 類型的方案[53]，故本文不考慮對偶攻擊對LTRU的影響.過度拉伸NTRU 攻擊[54]的適用范圍為模數(shù)q遠(yuǎn)大于秘密多項(xiàng)式系數(shù)的情況.由于LTRU 的模數(shù)q數(shù)值較小，不滿足該情況，故本文不考慮該攻擊.混合攻擊[55]是格攻擊和中間相遇攻擊的提升版本，但混合攻擊對于有著稀疏分布的秘密多項(xiàng)式系數(shù)和噪音多項(xiàng)式系數(shù)的方案能取得顯著效果.然而對于LTRU，混合攻擊不如原始攻擊有效，因?yàn)長TRU 的秘密 (f,g)并非稀疏分布，不符合混合攻擊的條件.

3.6 分析和討論

1）多項(xiàng)式環(huán)

本文LTRU 方案使用第 3n個分圓多項(xiàng)式環(huán)Zq[x]/(xn-xn/2+1)，其中n的形式為 3l×2e，q為某些素?cái)?shù).主要原因是，當(dāng)選擇合適的q，如NTT 友好的q時，存在高效的NTT 算法計(jì)算該環(huán)上的多項(xiàng)式乘法和除法.同時，n的選擇具有更大的靈活性，因?yàn)閚能夠選擇576，768，864，972，1 152，1 296 等數(shù)值.當(dāng)選擇其他的n值時，LTRU 能夠達(dá)到其他的安全強(qiáng)度（如192 b和256 b），而不再局限于128 b 的安全強(qiáng)度.但是，本文主要針對128 b 的安全強(qiáng)度，故選擇n=648.相比而言，NTRU-HRSS[20]使用多項(xiàng)式環(huán) Zq[x]/(xn-1)，其中n為素?cái)?shù)，q為2 次冪；SNTRU Prime[21]使用多項(xiàng)式環(huán)Zq[x]/(xn-x-1)，其中n，q均為素?cái)?shù).這些多項(xiàng)式環(huán)不是NTT 友好環(huán)，所以這些多項(xiàng)式環(huán)上的多項(xiàng)式乘法和除法更復(fù)雜，且耗時更多.

2）明文空間模數(shù)p

與其他NTRU 方案如文獻(xiàn)[20-21,26-27]中的方案不同，本文LTRU 使用的明文空間模數(shù)p=2，且只需出現(xiàn)在私鑰f中，即f=pf′+1，而無需在公鑰h以及解密算法中出現(xiàn).但是，NTRU 方案[20-21,26-27]使用模數(shù)p=3.甚至，由于NTRU 類型方案要求q和p互素，而NTRU-HRSS[20]由于使用2 次冪的模數(shù)q，所以它使用了與q互素的最小整數(shù)p=3.

3）糾錯機(jī)制

常見的NTRU 類型方案[20-21,26-27]的密文形式為c=phr+mmodq，這可以視為明文m編碼在密文c的低位.其恢復(fù)明文m的方式主要通過計(jì)算cfmodq之后再模p來消去雜項(xiàng).這種糾錯機(jī)制依賴于雜項(xiàng)是p的倍數(shù).與之不同的是，LTRU 在底層公鑰加密方案PKE′中首先將明文m提升q/2 倍，相當(dāng)于把明文m編碼到密文c的高位，隨后在解密算法中只要求雜項(xiàng)的范數(shù)小于 1/2，而不必要求其為p的倍數(shù).同時可以看到，LTRU 不使用糾錯碼來恢復(fù)明文.糾錯碼雖然能夠高效地實(shí)現(xiàn)糾錯來恢復(fù)明文，但是糾錯碼使得代碼實(shí)現(xiàn)更復(fù)雜且增加遭遇側(cè)信道攻擊的風(fēng)險(xiǎn)，如文獻(xiàn)[30]針對糾錯碼提出了有效的側(cè)信道攻擊.

4）密文壓縮

LTRU 的密文壓縮操作見算法5 的行②.本文的LTRU 是第1 個僅基于NTRU 單向困難性假設(shè)構(gòu)造的、不使用糾錯碼也能夠壓縮密文的密鑰封裝方案.LTRU 的密鑰壓縮參數(shù)d可根據(jù)需求自行調(diào)整.對于其他NTRU 類型方案[20-21,26-27]，如果它們壓縮密文，那么壓縮過程會在密文的低位帶來誤差，而編碼在密文低位的明文m的有效信息會被這些誤差破壞，使得正確的明文m難以恢復(fù)出來；同時在解密算法中雜項(xiàng)也不再是p的倍數(shù)，所以也無法通過模p來消去雜項(xiàng)以恢復(fù)正確的明文m.

4 高效的混合基數(shù)論變換

本節(jié)將介紹本文提出的一種混合基NTT 算法，其能高效地計(jì)算本文推薦參數(shù)集LTRU-648 所使用的 環(huán) Zq[x]/(xn-xn/2+1)，n=648，q=2 917上的多項(xiàng)式乘法和除法，且利用了1-迭代Karatsuba 算法和單位根的性質(zhì)減少乘法的數(shù)量，以提高計(jì)算效率.

對于 Zq[x]/(xn-xn/2+1)，n=648，q=2 917，可 知Zq中存在 3n/2 次本原單位根 ζ=2，其中ζ為k次本原單位根是指ζk≡1modq且ζi≠1modq，0＜i＜k.

4.1 正向變換

為方便理解，圖1 展示了混合基NTT 對應(yīng)的CRT 同構(gòu)樹形圖.本文的混合基NTT 的計(jì)算過程主要依靠逐層CRT 分解.

Fig.1 The tree map of CRT isomorphism圖1 CRT 同構(gòu)的樹形圖

類似于文獻(xiàn)[26]提出的第1 層CRT 同構(gòu)，對于Zq[x]/(xn-xn/2+1)，有

其中 ζ1+ζ2=1 和 ζ1ζ2=1.容易求得，ζ2=1-ζ1和取ζ1=ζn/4modq以 及 ζ2=ζ5n/4modq，對于任意的f∈Zq[x]/(xn-xn/2+1)，可得

由于 ζ1fn/2只需計(jì)算1 次而可使用2 次，故式（2）（3）總計(jì)只需n/2 個乘法和n個加（減）法.

1）基-2 FFT trick 步驟

可利用CRT 對 Zq[x]/(xn/2-ζ1) 和 Zq[x]/(xn/2-ζ2)進(jìn)行基-2 FFT trick 步驟的分解.對于每個基-2 FFT trick步驟形如

其中r為 ζ 的某次冪，對于f′∈Zq[x]/(x2m-r2)，可得

其中每個r fi′只需計(jì)算1 次而可使用2 次.這使得每層的基-2 FFT trick 步驟所需乘法數(shù)量從n個銳減到n/2個.

2）基-3 FFT trick 步驟

對于n=648，基-2 FFT trick 步驟可進(jìn)行1 層，直至得到4 個形如 Zq[x]/(x162-ζ81)的項(xiàng).此時本文采用基-3 FFT trick.每個基-3 FFT trick 步驟均形如

其中r為 ζ 的某次冪，ρ=ζn/3modq為3 次單位根.Zq[x]/(x3m-r3) 中的多項(xiàng)式f′′可以表示為

其中fa,fb,fc均為m-1 次多項(xiàng)式.由于 ρ3=1 modq，可得

注意到ρ2+ρ+1=0 modq，則 ρ2=-ρ-1 modq.類似于文獻(xiàn)[56]，此時有

以及

于是可得

注意到，r fb,r2fc,ρ(r fb-r2fc)都只需要計(jì)算1 次而能夠多次使用.并且只需存儲和使用本原單位根r和r2以及3 次單位根 ρ，而無需存儲其他值如 ρr，ρ2r2，ρ2r，ρr2.易知，使用3 次單位根的性質(zhì)之后，每層的基-3 FFT trick 步驟所需乘法數(shù)量從 2n個銳減到n個.

正向變換中基-3 FFT trick 步驟可進(jìn)行4 層，直到將Zq[x]/(xn-xn/2+1) 分解得到n/2個模2 次多項(xiàng)式的環(huán).換句話說，即有

其中 τ(i) 表示第i個環(huán)中 ζ的冪且序號從0 開始.對于f∈Zq[x]/(xn-xn/2+1)，其正向變換的結(jié)果記為

為方便后文書寫，本文使用符號 NT T表示上述的正向變換過程.正向變換 NT T的偽代碼見算法11.

算法11.正向變換 NT T.

4.2 逆向變換

逆向變換可由正向變換的逆過程得到.本文使用符號 INT T表示逆向變換.值得注意的是，在計(jì)算基-3 逆向FFT trick 時，同樣可利用3 次單位根的性質(zhì)減少乘法的數(shù)量.沿用4.1 節(jié)的符號和Zq[x]/(x3m-r3) 示例，在基-3 逆向FFT trick 中，從fx,fy,fz計(jì)算得到f′′.由f′′=fa+fbxm+fcx2m可知，這等價于得到fa,fb,fc.先計(jì)算

利用ρ2=-ρ-1 modq，進(jìn)一步可得

以及

于是可得

其中倍數(shù) 3-1可延遲處理.故易知，基于3 次單位根的性質(zhì)，每層的基-3 逆向FFT trick 步驟所需乘法數(shù)量從 2n個銳減到n個.

另外，對于基-2 逆向FFT trick，在此沿用4.1 節(jié)的示例，從fl=f′modxm-r和fr=f′modxm+r計(jì)算得到f′∈Zq[x]/(x2m-r2)的步驟為

其中fl,i和fr,i分別表示fl和fr的第i個系數(shù)，倍數(shù) 2-1同樣可延遲處理.易知，每層的基-2 逆向FFT trick 步驟共需要n/2個乘法.再合計(jì)上基-3 逆向FFT trick 步驟延遲處理的倍數(shù)，在整個逆向變換結(jié)束之時，需要乘以總的倍數(shù) (n/2)-1modq.

逆向變換 INT T 的偽代碼見算法12.

算法12.逆向變換 INT T.

4.3 點(diǎn) 乘

原本需要5 個乘法，現(xiàn)在只需要4 個乘法.使用1-迭代Karatsuba 算法計(jì)算點(diǎn)乘的偽代碼見算法13.

算法13.點(diǎn)乘.

4.4 基于混合基NTT 的多項(xiàng)式運(yùn)算

基于混合基NTT 計(jì)算多項(xiàng)式乘法h=fg∈Zq[x]/(xn-xn/2+1)的過程為

另外，本文同樣使用該混合基NTT 計(jì)算多項(xiàng)式除法h=g/f∈Zq[x]/(xn-xn/2+1)，即計(jì)算LTRU 方案中的公鑰h.具體而言，其計(jì)算過程為

算法14.計(jì)算低次數(shù)多項(xiàng)式的逆.

5 實(shí)現(xiàn)細(xì)節(jié)

本文給出了LTRU 的便攜C 實(shí)現(xiàn)和優(yōu)化AVX2實(shí)現(xiàn).下面將簡要介紹LTRU 的一些實(shí)現(xiàn)細(xì)節(jié).值得注意的是，LTRU 的所有實(shí)現(xiàn)均采用了常數(shù)時間實(shí)現(xiàn)技巧，以抵抗一些潛在的側(cè)信道攻擊，特別是計(jì)時攻擊[31].

5.1 基本構(gòu)件

本文使用的模數(shù)q=2 917是低于16 b 的素?cái)?shù)，所以Zq[x]/(xn-xn/2+1) 中的多項(xiàng)式能夠使用長度為n、類型為16 b 有符號整型的數(shù)組來存儲.

1）哈希函數(shù)

本文中使用的哈希函數(shù)均使用SHA3 系列函數(shù)來實(shí)例化.具體而言，使用SHA3-256 實(shí)例化哈希函數(shù) F，使用SHA3-512 實(shí)例化哈希函數(shù) H.其中 H以明文消息m作為輸入，得到64 B 的輸出，其中前32 B 作為導(dǎo)出的共享密鑰，后32 B 作為種子并使用SHAKE128 來生成加密算法所需的隨機(jī)數(shù).

2）秘密多項(xiàng)式

本文使用的秘密多項(xiàng)式如f′,g,r都是根據(jù)分布采樣得到.每采樣一個系數(shù)需要4 個隨機(jī)比特，所以采樣一個多項(xiàng)式需要 4n個比特，即n/2字節(jié).

3）約減算法

在計(jì)算多項(xiàng)式系數(shù)的加法和乘法時，計(jì)算結(jié)果存在超出16 b 有符號整型的有效表示范圍的可能性.此時需要使用約減算法將計(jì)算結(jié)果約減到 [0,q).本文使用Barrett 約減算法[57]和Montgomery 約減算法[58].其中Barrett 約減算法主要用于系數(shù)加法后的約減；而Montgomery 約減算法主要用于系數(shù)和系數(shù)相乘，或者系數(shù)和本原單位根相乘時的約減.

4）消息的存儲形式

注意到在LTRU 加密算法中，多項(xiàng)式e是系數(shù)范圍取自 {0,1} 的多項(xiàng)式，所以可以將e視為大小為n的比特串.實(shí)際上，本文使用n/8 個字節(jié)（即n位）來存儲并表示e，這樣能夠減少將e在多項(xiàng)式和比特串之間轉(zhuǎn)換的過程，提高效率.

5）公私鑰和密文

5.2 C 實(shí)現(xiàn)

本節(jié)提供LTRU 的C 實(shí)現(xiàn)的細(xì)節(jié).本文使用第4節(jié)的高效的混合基NTT 來計(jì)算LTRU-648 的多項(xiàng)式乘法和除法（即計(jì)算公鑰h）.測試設(shè)備為：硬件配置為2.3 GHz 的?ntel?Core? i7-10510U CPU 和16 GB 內(nèi)存的筆記本電腦，且關(guān)閉Turbo Boost 和Hyperthreading.操作系統(tǒng)為：核為Linux Kernel 4.4.0 的Ubuntu 20.04 LTS 操作系統(tǒng)，且gcc 版本為9.4.0.編譯參數(shù)為：-Wallmarch=native-mtune=native-O3-fomit-framepointer-Wnounknown-pragmas.

本文LTRU 的C 實(shí)現(xiàn)只涉及到整型算術(shù)操作，特別是16 b 有符號整型算術(shù).在NTT 的實(shí)現(xiàn)中，由于C 語言的“%”運(yùn)算符不是常數(shù)時間實(shí)現(xiàn)，其執(zhí)行時間和輸入數(shù)據(jù)長度密切相關(guān)，存在泄露秘密數(shù)據(jù)的可能性，故本文轉(zhuǎn)向使用常數(shù)時間實(shí)現(xiàn)的Barrett約減算法和Montgomery 約減算法.對于正向NTT 變換，本文使用延遲規(guī)約策略[59]來減少約減的次數(shù).具體而言，對于乘法中使用的Montgomery 約減，其輸出值范圍為 [-q,q].本文使用的模數(shù)q為12 b，所以在6層FFT trick 之后，正向NTT 變換輸出的多項(xiàng)式范圍在 [-7q,7q]之間，這顯然在16 b 有符號整型的有效表示范圍之內(nèi).故中間計(jì)算過程無需進(jìn)行額外的Barrett 約減，而只需要在正向NTT 變換結(jié)束時進(jìn)行1 次Barrett 約減.

5.3 AVX2 實(shí)現(xiàn)

本節(jié)提供LTRU 的AVX2 實(shí)現(xiàn)細(xì)節(jié).AVX2 實(shí)現(xiàn)主要優(yōu)化的運(yùn)算包括：多項(xiàng)式加法/乘法/除法、模約減算法等.但是，SHA3 系列哈希函數(shù)并沒采用AVX2 優(yōu)化實(shí)現(xiàn)，而是繼續(xù)采用C 語言的實(shí)現(xiàn).這是因?yàn)镾HA3 系列哈希函數(shù)難以向量化實(shí)現(xiàn)，而目前最高效的實(shí)現(xiàn)是基于C 語言的[52].另外，NTT 運(yùn)算非常耗時，所以NTT 運(yùn)算是AVX2 優(yōu)化的主要目標(biāo).下面主要介紹本文提出的混合基NTT 的AVX2 實(shí)現(xiàn)細(xì)節(jié).

AVX2 指令集的載入/存儲指令一次性載入/存儲的數(shù)據(jù)長度為256 b.換句話說，指令能夠一次性載入/存儲16 個多項(xiàng)式系數(shù)，因?yàn)槊總€系數(shù)使用16 b 有符號整型表示.但是，每個多項(xiàng)式共有 648個系數(shù)，其中648 并非16 的整數(shù)倍.為了能夠使用AVX2 指令集的載入/存儲指令，將648 個系數(shù)對相鄰的16 個系數(shù)進(jìn)行劃分，得到40 個劃分單位以及剩下的8 個系數(shù)，然后對每個劃分單位進(jìn)行數(shù)據(jù)對齊.這種方法雖然便于使用載入/存儲指令，但不便于在NTT 運(yùn)算中計(jì)算基-2 FFT trick 步驟和基-3 FFT trick 步驟.

為了方便使用AVX2 指令集的載入/存儲指令，同時方便計(jì)算基-2 FFT trick 步驟和基-3 FFT trick 步驟，本文采用2 個系數(shù)填充過程：

1）將648 個系數(shù)對相鄰的12 個系數(shù)進(jìn)行劃分，得到54 個劃分單位；

2）把每一個劃分單位里面的12 個系數(shù)拓展到16 個系數(shù)，即保留原12 個系數(shù)位置不變，在它們末尾的位置填充4 個0.

通過這2 個系數(shù)填充過程，得到864 個系數(shù)，以及新的54 個劃分單位，每個劃分單位包含16 個系數(shù).此時每個劃分單位能夠一次性被載入到寄存器之中.在完成寄存器一系列計(jì)算、存儲回內(nèi)存位置后，多項(xiàng)式系數(shù)提取的過程為：

1）將864 個系數(shù)對相鄰的16 個系數(shù)進(jìn)行劃分，得到54 個劃分單位；

2）在每一個劃分單位中提取前面的12 個系數(shù)，舍棄末尾的4 個0.

通過這2 個系數(shù)提取過程，得到原始長度的多項(xiàng)式數(shù)組.系數(shù)填充過程和系數(shù)提取過程如圖2 所示.

Fig.2 The padding and extraction of coefficients圖2 系數(shù)的填充與提取

這種填充過程應(yīng)用在多項(xiàng)式的NTT 運(yùn)算，如正向變換、逆向變換、點(diǎn)乘和求逆之中.另外，這種填充過程使得NTT 運(yùn)算以12 倍的并行度進(jìn)行計(jì)算，區(qū)別于通常的16 倍的并行度計(jì)算.這是因?yàn)榇藭r每個寄存器只能一次性處理原始多項(xiàng)式的12 個系數(shù)，而非原始多項(xiàng)式的16 個系數(shù).由于AVX2 指令集的載入/存儲指令耗時較多，所以應(yīng)該減少內(nèi)存訪問的次數(shù).常用的方法是合并處理NTT 運(yùn)算中的若干層.本文合并正向變換的第2 層和第3 層的計(jì)算.在此期間，僅需載入一次數(shù)據(jù)，無需額外的訪問內(nèi)存和數(shù)據(jù)載入/存儲便能夠完成第2 層和第3 層的計(jì)算，這能夠降低因載入/存儲指令帶來的CPU 周期數(shù)的消耗.本文通過vmovdqa指令完成數(shù)據(jù)的載入/存儲.在分別載入多項(xiàng)式系數(shù)和本原單位根之后，通過vpmulhw指令和vpmullw指令分別計(jì)算它們乘積的高位和低位，這樣能夠高效地計(jì)算它們的Montgomery約減的值.本文的AVX2 實(shí)現(xiàn)將一些常用的代碼段通過macro封裝起來，這使得整體代碼簡潔和可讀性強(qiáng).

5.4 常數(shù)時間實(shí)現(xiàn)

計(jì)時攻擊[31]是一種常見的側(cè)信道攻擊，它指的是敵手可以根據(jù)密碼方案在軟硬件環(huán)境中的執(zhí)行時間等信息來推斷所執(zhí)行的運(yùn)算操作和內(nèi)容訪問情況，繼而攻擊者可以根據(jù)所獲取的側(cè)信道信息來推算出該操作所涉及的一些秘密信息，如私鑰或者一些秘密值.目前來說，密碼方案的實(shí)現(xiàn)幾乎都需要考慮計(jì)時攻擊，并應(yīng)該采用常數(shù)時間實(shí)現(xiàn)策略.因此，本文的LTRU 實(shí)現(xiàn)過程采用了常數(shù)時間實(shí)現(xiàn)策略.最重要的是，本文并沒使用非常數(shù)時間的指令來操作秘密數(shù)據(jù)，以及沒使用依賴于秘密數(shù)據(jù)的判斷分支語句，也沒訪問依賴于秘密數(shù)據(jù)尋址的內(nèi)存地址.計(jì)算NTT 過程中取模使用到的Barrett 約減算法和Montgomery 約減算法均是常數(shù)時間實(shí)現(xiàn)[59]，且算法本身對任意合適的模數(shù)均成立.至于采樣秘密多項(xiàng)式f′,g,r，本文均以常數(shù)時間的方式來采樣.每次固定使用4 b 來生成1 個多項(xiàng)式系數(shù).顯然，生成秘密多項(xiàng)式的時間也是恒定的.

6 比較和分析

本節(jié)將比較混合基NTT 算法與未使用1-迭代Karatsuba 算法和單位根的性質(zhì)優(yōu)化乘法數(shù)量的NTT算法，以及比較本文LTRU 和其他NTRU 類型密鑰封裝方案如NTRU-HRSS[20]，SNTRU Prime[21]，NTTRU[26]，NTRU-A[27]，CTRU[28]，BAT[29]，還有基于模格的密鑰封裝方案如N?ST 標(biāo)準(zhǔn)化方案Kyber[22].

表2 給出了混合基NTT 算法與未使用1-迭代Karatsuba 算法和單位根的性質(zhì)優(yōu)化乘法數(shù)量的NTT算法在理論乘法復(fù)雜度分析和具體實(shí)現(xiàn)的CPU 周期數(shù)的比較.

Table 2 Comparison Between Mixed-Radix NTT and Unoptimized NTT表2 混合基NTT 和未優(yōu)化的NTT 的比較

表3 和表4 展示了本文LTRU 和其他方案對比的詳細(xì)情況.為方便比較，在此選取與這些方案安全強(qiáng)度接近的參數(shù)集，但CTRU 和Kyber 并沒有接近128 b量子安全強(qiáng)度的參數(shù)集，所以在此選取它們的推薦參數(shù)集.SNTRU Prime 選取SNTRU Prime-761 參數(shù)集，NTRU-A 選取參數(shù)集，CTRU 選取CTRU-768 參數(shù)集，BAT 選取BAT-512 參數(shù)集，Kyber 選取Kyber-768 參數(shù)集.其中NTRU-HRSS，SNTRU Prime-761，Kyber-768 的數(shù)據(jù)和開源代碼來自它們的N?ST第3 輪材料.NTTRU 的數(shù)據(jù)和開源代碼來自文獻(xiàn)[26].的數(shù)據(jù)來自文獻(xiàn)[27]，CTRU-768 的數(shù)據(jù)來自文獻(xiàn)[28]，BAT-512 的數(shù)據(jù)來自文獻(xiàn)[29].

Table 3 Comparison Between LTRU and Other Schemes表3 LTRU 和其他方案的對比

Table 4 Comparison of Implementation Efficiency of Schemes表4 方案的實(shí)現(xiàn)效率對比 kcycle

6.1 NTT 算法的比較

值得注意的是，本文的混合基NTT 和未優(yōu)化的混合基NTT 在多項(xiàng)式環(huán) Zq[x]/(xn-xn/2+1)首層CRT同構(gòu)具有相同的乘法復(fù)雜度：正向變換時需要n/2個乘法，逆向變換時需要 3n/2個乘法.為方便比較乘法復(fù)雜度，在此記基-2 FFT trick 和基-3 FFT trick 的層數(shù)分別為l2和l3.在本文的混合基NTT 中，每層基-2 FFT trick 的正向變換和逆向變換均需要n/2個乘法.每層基-3 FFT trick 的正向變換和逆向變換均需要n個乘法.然而，未優(yōu)化的NTT 每層基-3 FFT trick 的正向變換和逆向變換均需要 2n個乘法.因?yàn)? 種NTT 算法的求逆運(yùn)算相同，于是求逆運(yùn)算具有相同的乘法復(fù)雜度，故可以省去對它們的求逆運(yùn)算的比較.

從表2 可以看出，在比較多項(xiàng)式乘法復(fù)雜度時，本文NTT 比未優(yōu)化的NTT 在正向變換、點(diǎn)乘和逆向變換方面分別減少了nl3，n/2，nl3個乘法，總計(jì)減少2nl3+n/2 個乘法.具體而言，選取參數(shù)n=648和q=2 917 時，此時層數(shù)分別為l2=1,l3=4.測試數(shù)據(jù)均由C 語言實(shí)現(xiàn)，并采用O3 優(yōu)化指令.從具體實(shí)現(xiàn)的CPU 周期數(shù)來看，相比未優(yōu)化的NTT，本文NTT在正向變換、點(diǎn)乘和逆向變換的CPU 周期數(shù)分別降低24.9%，20.6%，26.8%，總共降低25.3%.

6.2 方案的性能比較

在表3 中，困難性假設(shè)指的是該方案所基于的困難性問題.底層PKE 指的是該密鑰封裝方案所蘊(yùn)含的底層公鑰加密方案的屬性，其中?ND-CPA 指不可區(qū)分意義下的選擇明文安全性，OW-CPA 指單向意義下的選擇明文安全性，DPKE 指確定性的公鑰加密方案，RPKE 指隨機(jī)性的公鑰加密方案.|pk|，|ct|，B.W.分別指它們的公鑰尺寸、密文尺寸和帶寬（公鑰尺寸+密文尺寸），單位均是 B.Sec-（C,Q）是方案的安全強(qiáng)度，C 表示經(jīng)典安全強(qiáng)度，Q 表示量子安全強(qiáng)度.δ指方案的錯誤率.

6.3 方案的效率比較

在表4 中，KeyGen，Encaps，Decaps對應(yīng)的列分別給出這些密鑰封裝方案在密鑰生成算法、密鑰封裝算法和解封裝算法運(yùn)行10 000 次的平均CPU 周期，單位是kcycle.

需要說明的是，NTRU-HRSS，SNTRU Prime-761，NTTRU，Kyber-768 的C 實(shí)現(xiàn)數(shù)據(jù)均是將它們的開源C 代碼在同一平臺上運(yùn)行得到的，旨在為它們的C 實(shí)現(xiàn)效率提供直觀的對比.至于NTRU-HRSS，SNTRU Prime-761，Kyber-768 的AVX2 實(shí)現(xiàn)的測試數(shù)據(jù)則是取自SUPERCUP（代號為supercop-20220506，測試設(shè)備為3.0GHz ?ntel Xeon E3-1 220 v6）[60]；SUPERCUP能夠提供密碼方案的AVX2 實(shí)現(xiàn)最新最快的測試數(shù)據(jù).NTTRU 的AVX2 測試數(shù)據(jù)取自文獻(xiàn)[26].NTRU-的AVX2 測試數(shù)據(jù)則取自文獻(xiàn)[27]，BAT-512 的AVX2 測試數(shù)據(jù)則取自文獻(xiàn)[29]，CTRU-768 的C 實(shí)現(xiàn)和AVX2 實(shí)現(xiàn)的測試數(shù)據(jù)均是取自文獻(xiàn)[28].需要注意的是，文獻(xiàn)[27-28]沒有提供開源C 代碼和AVX2代碼，文獻(xiàn)[29]只提供AVX2 代碼.且文獻(xiàn)[27,29]只提供AVX2 實(shí)現(xiàn)的測試數(shù)據(jù)，故為公平比較，表4 只展示和BAT-512 的AVX2 實(shí)現(xiàn)的測試數(shù)據(jù)，而不再展示它們的C 實(shí)現(xiàn)的測試數(shù)據(jù).

6.4 分析和結(jié)論

經(jīng)表3 和表4 的數(shù)據(jù)分析，與其他基于NTRU 格的密鑰封裝方案NTRU-HRSS[20]，SNTRU Prime[21]，NTTRU[26]，NTRU-A[27]，CTRU[28]，BAT[29]，還有基于模格的密鑰封裝方案Kyber[22]相比，本文的LTRU 具有4 點(diǎn)優(yōu)勢：

1）小的公鑰尺寸、密文尺寸和帶寬

與NTRU-HRSS，SNTRU Prime-761，NTTRU，CTRU-768，Kyber-768 對比，LTRU 具有更小的密文尺寸和更小的通信帶寬.具體地，與NTRUHRSS 對比，LTRU 的公鑰尺寸降低14.6%，密文尺寸降低26.0%，帶寬降低20.3%.與SNTRU Prime-761 相比，LTRU 的公鑰尺寸降低16.1%，密文尺寸降低19.0%，帶寬降低17.4%.與Kyber-768 相比，LTRU 的公鑰尺寸 降低17.9%，密文尺寸降低22.6%，帶寬降低20.2%.LTRU 和具有相同長度的公鑰尺寸，但是LTRU 的密文尺寸更小，降低了13.4%.由于BAT-512 使用復(fù)雜的糾錯碼使得它能使用更小的模數(shù)，從而它的帶寬比LTRU 的更有優(yōu)勢，但復(fù)雜的糾錯碼導(dǎo)致它的密鑰生成比LTRU 的密鑰生成慢了3個數(shù)量級.

2）均衡的安全強(qiáng)度、錯誤率和帶寬

由于LTRU 的目標(biāo)安全強(qiáng)度為128 b，所以它的錯誤率 2-154可視為可忽略.NTRU-HRSS 和BAT-512的量子安全強(qiáng)度只有124 b，并沒達(dá)到128 b.而Kyber-768 具有166 b 量子安全強(qiáng)度.CTRU-768 具有164 b量子安全強(qiáng)度，與128 b 的間距過大，造成過剩的安全性.SNTRU Prime-761，NTTRU，雖然達(dá)到了128 b 安全強(qiáng)度，但其帶寬都比LTRU 的帶寬大.注意到NTRU-HRSS 和SNTRU Prime-761 均為零錯誤率，但是它們需要使用更大的模數(shù)q，這無疑增加了通信帶寬.所以，與其他方案對比，LTRU 達(dá)到了128 b 安全強(qiáng)度，且具有與安全強(qiáng)度匹配的、可忽略的錯誤率，同時能夠節(jié)省通信帶寬.

3）強(qiáng)的底層PKE 方案安全性

由于Kyber-768 是基于MLWE 困難性假設(shè)的，而其他方案都是基于NTRU 相關(guān)的困難性假設(shè)，所以為了公平對比，在此只比較LTRU，NTRU-HRSS，SNTRU Prime-761，NTTRU，CTRU-768，BAT-512 的底層PKE 方案安全性.從表3 可以看到，LTRU，CTRU-768，BAT-512 的底層PKE 方案能夠達(dá)到?NDCPA 安全性，而NTRU-HRSS，SNTRU Prime-761，NTTRU，的底層PKE 方案均是OW-CPA 安全的.其中CTRU-768 和BAT-512 均基于2 個困難性假設(shè)，唯有LTRU 僅基于NTRU-OW 假設(shè)而達(dá)到?ND-CPA安全性.不容忽視的是，對底層PKE 方案來說，?NDCPA 安全性比OW-CPA 安全性更強(qiáng).

4）高效的實(shí)現(xiàn)

從表4 可知，LTRU 具有出色的實(shí)現(xiàn)效率.具體而言，與NTRU-HRSS 的C 實(shí)現(xiàn)相比，LTRU 在密鑰生成、封裝和解封裝等算法上分別快了1 462.3 倍、58.5 倍和90.0 倍；與NTRU-HRSS 的AVX2 實(shí)現(xiàn)相比，LTRU在密鑰生成算法和解封裝算法上分別快了10.9 倍和1.7 倍，其封裝算法的速度與NTRU-HRSS 的相當(dāng).另外，與SNTU Prime-761 的AVX2 實(shí)現(xiàn)相比，LTRU 在密鑰生成、封裝和解封裝等算法上分別快了30.9 倍、1.7 倍和1.4 倍.主要原因是LTRU 使用了本文提出的高效的混合基NTT 計(jì)算多項(xiàng)式運(yùn)算，而NTRUHRSS 和SNTU Prime-761 使用的多項(xiàng)式環(huán)不是NTT友好的，它們只能使用效率更低的算法計(jì)算多項(xiàng)式運(yùn)算.與CTRU-768 相比，LTRU 的C 實(shí)現(xiàn)在密鑰生成、封裝和解封裝等算法都更有優(yōu)勢，AVX2 實(shí)現(xiàn)在解封裝算法的速度與CTRU-768 的相當(dāng).與BAT-512 的AVX2 實(shí)現(xiàn)相比，LTRU 在密鑰生成算法上快了3 個數(shù)量級，在解封裝算法上快了1.7 倍.

與Kyber-768 相比，LTRU 的實(shí)現(xiàn)效率全面占優(yōu).具體而言，與Kyber-768 的AVX2 實(shí)現(xiàn)相比，LTRU 在密鑰生成、封裝和解封裝等算法上分別快了1.7 倍、2.3 倍和1.3 倍.這得益于LTRU 在密鑰生成算法中使用高效混合基NTT 以及在加密和解密算法中只需要計(jì)算1 個多項(xiàng)式乘法.然而，Kyber 在密鑰生成算法和加密算法中均需要使用拒絕采樣生成矩陣且需要計(jì)算多項(xiàng)式矩陣-向量乘法，其中解封裝算法中還有重加密和重新計(jì)算多項(xiàng)式矩陣-向量乘法的過程，這些操作明顯更加耗時.與之對比，LTRU 方案具有運(yùn)算簡單、實(shí)現(xiàn)高效等特點(diǎn).

7 總結(jié)

基于NTRU 格的密碼系統(tǒng)具有結(jié)構(gòu)簡潔、強(qiáng)安全保障、不受專利影響等優(yōu)勢，有利于設(shè)計(jì)實(shí)用化高效的后量子密碼方案.本文提出了一個僅基于NTRU 單向困難性假設(shè)構(gòu)造的、不使用糾錯碼也能夠壓縮密文的密鑰封裝方案LTRU.LTRU 包含一個?ND-CPA 安全的公鑰加密方案LTRU.PKE 以及一個?ND-CCA 安全的密鑰封裝方案LTRU.KEM.本文還提供了針對128 b 安全強(qiáng)度的參數(shù)集，及其對應(yīng)的C 實(shí)現(xiàn)和AVX2 實(shí)現(xiàn).針對LTRU 所使用的環(huán)Z2917[x]/(x648-x324+1)上的多項(xiàng)式乘法和除法，本文提出了一種高效的混合基NTT 算法，該算法結(jié)合單位根的性質(zhì)和1-迭代Karatsuba 算法來減少乘法的數(shù)量，以提高計(jì)算效率.本文實(shí)驗(yàn)結(jié)果表明，與N?ST 標(biāo)準(zhǔn)化方案Kyber-768 相比，LTRU 的公鑰尺寸降低17.9%，密文尺寸降低22.6%，帶寬降低20.2%；與N?ST 第3 輪決賽方案NTRU-HRSS 相比，LTRU 的經(jīng)典安全強(qiáng)度和量子安全強(qiáng)度分別增強(qiáng)6 b 和5 b，以及公鑰尺寸降低14.6%，密文尺寸降低26.0%，帶寬降低20.3%，并且LTRU 的實(shí)現(xiàn)效率優(yōu)于NTRU-HRSS.

未來工作主要包括2 點(diǎn)：1）對本文提出的LTRU在多平臺上實(shí)現(xiàn)，包括ARM Cortex-M4 實(shí)現(xiàn)和FPGA實(shí)現(xiàn)等；2）提出更多的LTRU 參數(shù)集，使其滿足更多的應(yīng)用場景，如資源受限的?oT 設(shè)備和智能卡等.

作者貢獻(xiàn)聲明：梁志闖負(fù)責(zé)方案的設(shè)計(jì)和論文撰寫；鄭婕妤負(fù)責(zé)方案的實(shí)現(xiàn)；趙運(yùn)磊負(fù)責(zé)論文修改.