董 經(jīng), 蔡彬彬, 吳宇森, 高 飛, 秦素娟, 溫巧燕

1. 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京 100876

2. 密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京 100878

1 引言

上述對(duì)NTRU 公鑰密碼的量子算法分析都是依托于量子搜索算法, 即Grover 算法. 那么是否仍存在其他量子算法可以實(shí)現(xiàn)對(duì)NTRU 的攻擊？本文發(fā)現(xiàn), Claw-Finding 量子算法[20]對(duì)NTRU 密碼的分析具有同樣的攻擊效果. 但是, 原始Claw-Finding 算法針對(duì)的函數(shù)輸出值為單比特, 而分析NTRU 中所構(gòu)造的函數(shù)輸出為比特串. 因此, 本文對(duì)原Claw-Finding 算法做了適當(dāng)修改, 并應(yīng)用修改的Claw-Finding量子算法實(shí)現(xiàn)對(duì)NTRU 密碼的攻擊. 在攻擊復(fù)雜度與文獻(xiàn)[19] 相等的情況下, 本文給出的量子攻擊避免了應(yīng)用Grover 算法時(shí)強(qiáng)量子Oracle 的前提假設(shè), 且不需要文獻(xiàn)[19] 在每次Oracle 疊加查詢時(shí)維護(hù)指數(shù)大列表O(f3).

2 預(yù)備知識(shí)

2.1 NTRU 公鑰密碼基礎(chǔ)

在介紹NTRU 公鑰密碼之前, 首先介紹算法中涉及的數(shù)學(xué)知識(shí).

定義1 (模) 給定正整數(shù)m, 整數(shù)a,b, 若滿足m|(a-b), 則稱a,b模m同余, 記為a ≡b(modm).

定義1 中式子a ≡b(modm) 稱為模m的同余式,m稱為同余式的模. 在NTRU 密碼算法中涉及到的多項(xiàng)式的模, 與上述定義中的整數(shù)模含義一致. 在數(shù)學(xué)上, 對(duì)于模運(yùn)算有以下性質(zhì):

定理1 給定整數(shù)A,B以及模數(shù)k, 若有A ≡B(modk), 那么對(duì)于任意整數(shù)C, 都有(A+C)≡(B+C) (modk) 成立.

定義2 (環(huán)) 若包含兩種代數(shù)運(yùn)算的代數(shù)系統(tǒng)(A,+,*) 滿足以下條件:

(1) (A,+) 構(gòu)成交換群;

(2) (A,*) 構(gòu)成半群;

(3)* 運(yùn)算關(guān)于+ 運(yùn)算滿足左、右分配律;則稱(A,+,*) 是一個(gè)環(huán). 這里+ 和* 是二元運(yùn)算. 通常情況下, + 運(yùn)算為環(huán)中的加法,* 運(yùn)算為環(huán)中的乘法. 在NTRU 密碼算法中二元運(yùn)算是加法和乘法.

定義3 (截尾多項(xiàng)式環(huán), truncated polynomial ring)R= Z[x]/(xN-1) 表示N-1 次整數(shù)多項(xiàng)式的集合. 用N維向量[a0,a1,··· ,aN-1] 表示(N-1) 次整數(shù)多項(xiàng)式a=a0+a1x+···+aN-1xN-1,R上的加法運(yùn)算+ 和乘法運(yùn)算* 如下:

(1) [a0,a1,··· ,aN-1]+[b0,b1,··· ,bN-1]=[a0+b0,a1+b1,··· ,aN-1+bN-1];

(2) [a0,a1,··· ,aN-1]*[b0,b1,··· ,bN-1] = [c0,c1,··· ,cN-1], 其中k階系數(shù)ck為:ck=a0bk+a1bk-1+···+akb0+ak+1bN-1+ak+2bN-2+···+aN-1bk+1=∑i+j≡k(modN)aibj.

則(R,+,*) 構(gòu)成的代數(shù)系統(tǒng)稱為截尾多項(xiàng)式環(huán), 也稱為卷積多項(xiàng)式環(huán), 用R= Z[x]/(xN-1) 表示, 其中Z 表示整數(shù).

特別地, NTRU 公鑰密碼中所用到的多項(xiàng)式環(huán)的系數(shù)均為整數(shù). 本文介紹的多項(xiàng)式環(huán)R中元素的多項(xiàng)式表示和向量表示將不再區(qū)分. 假設(shè)多項(xiàng)式a是R中的截尾多項(xiàng)式環(huán), 若關(guān)于模整數(shù)q有a*A= 1(modq), 則稱多項(xiàng)式A為截尾多項(xiàng)式環(huán)a的逆元.

NTRU 公鑰密碼系統(tǒng)中主要用到了三個(gè)截尾多項(xiàng)式環(huán), 形式如下:

多項(xiàng)式環(huán)Rp和Rq分別由多項(xiàng)式環(huán)R的系數(shù)模上p和q所得. 下面給出在NTRU 密碼中用到的三值多項(xiàng)式的定義.

定義4 (三值多項(xiàng)式) 設(shè)d1和d2是正整數(shù), 定義

T(d1,d2) 中的多項(xiàng)式稱為三值多項(xiàng)式.

NTRU 密碼算法主要由三個(gè)整數(shù)參數(shù)(N,p,q)和四個(gè)度最多為N-1 的三值多項(xiàng)式集合Lf,Lg,Lr,Lm共同決定. 正整數(shù)N決定了在NTRU 中所有多項(xiàng)式的度最多為N- 1. 正整數(shù)p,q為NTRU密碼算法中模運(yùn)算的模數(shù), 滿足gcd (p,q) = 1, 且一般情況下q遠(yuǎn)大于p. 本文中用* 表示截尾多項(xiàng)式環(huán)上的卷積運(yùn)算. 例如多項(xiàng)式A(x) = 1 + 2x+ 3x2和B(x) = 1 +x, 此時(shí)N= 3. 卷積運(yùn)算C(x)=A*B=1+3x+5x2+3x3=1+3x+5x2+3=4+3x+5x2. 這個(gè)運(yùn)算包括了環(huán)上的加法和乘法, 并且運(yùn)算結(jié)果的多項(xiàng)式的度最多仍為N-1. 三個(gè)三值多項(xiàng)式集合Lf,Lg,Lr的選取參照定義4, 而明文多項(xiàng)式Lm由通信過程中的發(fā)送方選取. 在本文中我們討論的參數(shù)集中均有正整數(shù)p=3. NTRU 密碼算法可分為三部分: 密鑰生成算法、加密算法、解密算法. 由于本文只關(guān)心在獲取公鑰信息后如何得到私鑰的信息, 所以只討論密鑰生成算法, 而并不具體推導(dǎo)加密和解密算法的過程. 對(duì)于NTRU 密碼系統(tǒng)工作的具體流程, 在文獻(xiàn)[1] 均有詳細(xì)討論. 為描述方便, 我們將通信雙方用Alice 和Bob 表示, 其中Alice表示發(fā)送方, Bob 為接收方.

2.2 NTRU 公鑰密碼密鑰生成算法

首先, Bob 選擇多項(xiàng)式f(x)∈Lf(df+1,df),g(x)∈Lg(dg,dg), 其中參數(shù)(df,dg) 由NTRU 相應(yīng)的參數(shù)集給定, 多項(xiàng)式f(x) 稱為私鑰多項(xiàng)式,g(x) 為生成多項(xiàng)式. 隨后Bob 計(jì)算私鑰多項(xiàng)式f(x) 的模逆fp(x),fq(x), 其中fp(x)∈Rp,fq(x)∈Rq, 且滿足

若私鑰多項(xiàng)式f(x) 的模逆fp(x) 或fq(x) 有一個(gè)不存在, Bob 需要重新選擇f(x). 最后Bob 通過式子h(x) =pfq(x)*g(x) (modq) 得到公鑰多項(xiàng)式h(x), 符號(hào)* 為前面提到的卷積運(yùn)算. 計(jì)算完成后, Bob將公鑰h發(fā)送給Alice. 這里f(x),fp(x),fq(x) 和g為Bob 私有, Alice 并不知道.

考慮到NTRU 密碼中用到的是卷積運(yùn)算, 如果私鑰足夠稀疏(即多項(xiàng)式系數(shù)非零項(xiàng)越少), 卷積計(jì)算速度越快, 密碼算法的效率越高. 基于此, 研究學(xué)者們提出NTRU 密碼算法參數(shù)集的另一種工作模式——乘積多項(xiàng)式模式[1,19,21](對(duì)應(yīng)的上述方式稱為直接選擇模式). 顧名思義, 在乘積多項(xiàng)式模式下Bob 選擇私鑰多項(xiàng)式f(x) 時(shí)不直接選擇私鑰, 而是選擇三個(gè)小系數(shù)多項(xiàng)式f1(x),f2(x),f3(x) 共同組成私鑰多項(xiàng)式, 即f(x) =f1(x)f2(x)+f3(x), 這里fi(x)∈Lfi(dfi,dfi),i= 1,2,3. 由于f1(x),f2(x),f3(x)中的非零項(xiàng)遠(yuǎn)小于零項(xiàng), 形成的向量比直接選擇的私鑰多項(xiàng)式向量更稀疏. 計(jì)算公鑰時(shí), Bob 仍舊按照h(x)=pfq(x)*g(x) (modq) 得到公鑰h(x), 然后在通信過程中將公鑰h(x) 發(fā)送給Alice. Alice 用接收到的公鑰h(x) 對(duì)消息進(jìn)行加密并發(fā)送給Bob, 最后Bob 通過f(x),fp(x) 進(jìn)行解密得到Alice 發(fā)送的消息. NTRU 加解密的具體計(jì)算過程參考文獻(xiàn)[1,22–24]. 為分析方便, 本文中省略多項(xiàng)式表示中的自變量,如將f(x) 記為f.

3 NTRU 公鑰密碼的量子搜索算法攻擊

2015 年Fluhrer 基于Grover 搜索算法提出對(duì)NTRU 密碼的量子攻擊[19], 包括兩種密鑰恢復(fù)攻擊和兩種明文恢復(fù)攻擊. 這里我們僅介紹文獻(xiàn)[19] 給出的第一種密鑰恢復(fù)攻擊. 值得注意的是, NTRU 密碼算法中每一個(gè)參數(shù)集都會(huì)給定安全參數(shù)k, 這一參數(shù)表明攻擊者對(duì)參數(shù)集執(zhí)行任何攻擊復(fù)雜度都不低于2k.

由密鑰生成算法的公鑰生成等式h=pfq*g(modq) 可得, 卷積運(yùn)算經(jīng)過簡(jiǎn)單的數(shù)學(xué)轉(zhuǎn)換易表示為向量的乘積形式:

其中H表示公鑰h的循環(huán)轉(zhuǎn)移矩陣. 若公鑰h的向量形式為h=h0,h1,··· ,hN-1, 那么相應(yīng)的H可表示為

觀察等式(4)可以發(fā)現(xiàn), 除了p是一個(gè)固定常數(shù), 其他參數(shù)都是向量或者矩陣. 因此, 如果在等式兩邊同時(shí)模p可得

在乘積多項(xiàng)式模式下, 式(6)可表示為

根據(jù)定理1 有

文獻(xiàn)[19] 的攻擊思想是根據(jù)小系數(shù)多項(xiàng)式f3的系數(shù)多樣性, 存儲(chǔ)所有可能的(f3,(-f3H(modq))(modp))的值,如存在某個(gè)列表L中. 隨后,在f1f2上應(yīng)用Grover 算法搜索f1f2滿足(f1f2H(modq))(modp) 的值在列表L中, 即搜索滿足(-f3H(modq)) (modp) = (f1f2H(modq)) (modp). 因此,Grover 算法的搜索空間為|f1f2|. 為進(jìn)一步降低搜索復(fù)雜度, 文獻(xiàn)[19] 引用了以下引理:

引理1 給定兩個(gè)多項(xiàng)式A,B ∈F[x]/(xN-1),AB表示兩個(gè)多項(xiàng)式的乘積. 若有A′=xmA, 則有(xmA)B=xm(AB) 成立, 即A′B=xm(AB).

引理2 給定兩個(gè)多項(xiàng)式A,B ∈F[x]/(xN- 1),AB表示兩個(gè)多項(xiàng)式的乘積. 若有A′=xmA,B′=x-mB, 則有(xmA)(x-mB)=AB成立, 即A′B′=AB.

引理1 中若m是正整數(shù), 則xm表示多項(xiàng)式向右移動(dòng)了m位. 若m是負(fù)整數(shù), 則xm表示多項(xiàng)式向左移動(dòng)了m位. 引理1 表明, 多項(xiàng)式A′B和AB的系數(shù)是相等的, 唯一不同的是系數(shù)的位置移動(dòng)了m位. 根據(jù)引理1, 式子fH=pg(modq) 有xmfH=pxmg(modq). 若用多項(xiàng)式xmf對(duì)密文(通常用e(x) 表示) 進(jìn)行解密操作, 可以得到明文(通常用m(x) 表示) 的循環(huán)移位多項(xiàng)式xmm(x), 攻擊者僅通過計(jì)算xmm(x) 的循環(huán)轉(zhuǎn)移即可獲得明文消息m(x). 因此, 若多項(xiàng)式對(duì)(f′(x),g′(x)) 滿足fH=pg(modq), 則多項(xiàng)式f′(x) 便可以作為NTRU 密碼的私鑰多項(xiàng)式對(duì)密文進(jìn)行解密. 同樣地, 在等式(8)中,目標(biāo)(f1f2,f3) 也有((xmf1f2)H(modq)) (modp) = (-xmf3H(modq)) (modp) 成立, 即滿足等式(8)的多項(xiàng)式對(duì)((f1f2)′,f′3) 組成的多項(xiàng)式f′就很有可能可以作為NTRU 的私鑰多項(xiàng)式. 在NTRU 的密碼分析中, 通常認(rèn)為攻擊者得到私鑰(明文) 多項(xiàng)式的任意循環(huán)轉(zhuǎn)移多項(xiàng)式, 都可攻破NTRU 公鑰密碼.應(yīng)用引理1 和2 后可得, 等式(8)中f1f2的搜索空間由|f1f2| 降為|f1f2|/N,f3的搜索空間由|f3| 降為|f3|/N. 該攻擊在具體參數(shù)集上的分析見表1. 其中k表示安全參數(shù), 指列表維護(hù)大小指每次Oracle 查詢需要查詢列表(f3,(-f3H(modq)) (modp)) 的大小.

表1 文獻(xiàn)[19] 在具體參數(shù)集上的分析Table 1 Analysis of quantum attack of Ref. [19] on parameter sets

4 NTRU 密碼的量子算法攻擊分析及改進(jìn)

通過上述分析可以發(fā)現(xiàn), 若預(yù)先將(f3,(-f3H(modq)) (modp)) 的值存在列表L中, Grover 搜索的量子Oracle 為以下形式:

這里有匹配的意思是指滿足等式(-f3H(modq)) (modp) = (f1f2H(modq)) (modp). 如在參數(shù)集EES593EP1 中,f1f2的搜索空間為2271.165, 提前存儲(chǔ)下來(lái)的(f3,(-f3H(modq)) (modp)) 的列表L的大小為O(2107.285). 在文獻(xiàn)[19] 中, 該攻擊是基于上述量子OracleOc(x)能以常數(shù)復(fù)雜度(即O(1))實(shí)現(xiàn)判斷某個(gè)f1f2對(duì)應(yīng)的(f1f2H(modq)) (modp) 的值是否存在于列表L中. 而實(shí)際上, 這一操作的復(fù)雜度不能以常數(shù)時(shí)間實(shí)現(xiàn). 換句話說, 該量子Oracle 的假設(shè)增大了該量子攻擊算法的實(shí)現(xiàn)難度, 無(wú)法達(dá)到文獻(xiàn)[19] 聲明的攻擊效果.

因此,為了避免上述攻擊的強(qiáng)量子Oracle 假設(shè)和維護(hù)指數(shù)大的列表L所帶來(lái)的消耗,本文基于Claw-Finding 量子算法[20]設(shè)計(jì)了新的攻擊. 該攻擊將類似中間相遇攻擊(MITM) 的兩部分看成兩個(gè)函數(shù), 函數(shù)的自變量分別為f1f2和f3,因變量為對(duì)應(yīng)的(f1f2H(modq)) (modp)和(-f3H(modq)) (modp).利用Claw-Finding 算法求解出滿足兩個(gè)函數(shù)相等關(guān)系的(f1f2,f3), 即可通過推導(dǎo)得到私鑰多項(xiàng)式f.

4.1 Claw-Finding 量子算法

問題1 (Claw-Finding) 給定兩個(gè)函數(shù)f:x ∈X →Z和g:y ∈Y →Z,X,Y和Z表示一個(gè)有限集合. 找到一對(duì)Claw (x,y), 其中x ∈X,y ∈Y, 使得f(x)=g(y).

2009 年, Tani[20]基于Szedegy 量子漫步算法[25]提出了解決Claw-Finding 問題的確定性算法.該算法基于Johnson 圖實(shí)現(xiàn), 利用二分查找(binary search) 和四分查找(4-ary search) 解決搜索問題.Johnson 圖是一類特殊的圖, 用J(n,k) 來(lái)表示. 它是一個(gè)有(nk)個(gè)頂點(diǎn)的連通正則圖, 圖上的每一個(gè)頂點(diǎn)都是[n] 的大小為k的子集(這里[n] = 1,2,··· ,n). 當(dāng)且僅當(dāng)兩個(gè)子集中僅有一個(gè)元素不同時(shí), 這兩個(gè)子集在圖上的兩個(gè)點(diǎn)之間有邊, 在數(shù)學(xué)上常稱之為集合之間的對(duì)稱差為2. 待檢測(cè)點(diǎn)集合(a,b,c,d,e,f)六個(gè)點(diǎn)組成的Johnson 圖J(6,3) 如圖1 所示.

圖1 頂點(diǎn)數(shù)為()=20 的Johnson 圖J(6,3) [26]Figure 1 Johnson graph J(6,3) with number of vertices()=20 [26]

當(dāng)且僅當(dāng)頂點(diǎn)集合的對(duì)稱差為2 時(shí), 頂點(diǎn)之間才有邊. 若點(diǎn)a為目標(biāo)點(diǎn), 則在Johnson 圖中頂點(diǎn)abc,abd,abe,abf,acd,ace,acf,ade,adf,aef均為標(biāo)記點(diǎn). 容易發(fā)現(xiàn), 目標(biāo)點(diǎn)a在集合(a,b,c,d,e,f) 中的概率為, 而在Johnson 圖中由目標(biāo)點(diǎn)a組成的標(biāo)記點(diǎn)的概率為這使得找到目標(biāo)點(diǎn)的概率變大[27].

在Claw-Finding 算法中, 首先定義兩個(gè)Johnson 圖Jf(|X|,l),Jg(|Y|,m), 圖中的X和Y分別對(duì)應(yīng)函數(shù)f和g的自變量,l和m則對(duì)應(yīng)兩個(gè)自變量的子集. 根據(jù)這兩個(gè)圖, 定義圖類積G=Jf×Jg, 若Jf(|X|,l) 上的點(diǎn)表示為F,Jg(|Y|,m) 上的點(diǎn)為G, 那么圖類積上的點(diǎn)為(F,G). 當(dāng)且僅當(dāng)Jf(|X|,l) 上的兩個(gè)點(diǎn)F,F′之間有邊且Jg(|Y|,m) 上的兩個(gè)點(diǎn)G,G′之間有邊時(shí), 圖類積G=Jf×Jg的點(diǎn)(F,G),(F′,G′) 之間才有邊. 若頂點(diǎn)(F,G) 中存在一對(duì)(x,y)∈F×G, 使得f(x)=g(y) 成立, 那么頂點(diǎn)(F,G)即為目標(biāo)點(diǎn). 另外, 我們用LF,G來(lái)表示每一個(gè)頂點(diǎn)(F,G) 對(duì)應(yīng)的具體函數(shù)值. 為方便分析, 令|X|=K,|Y|=M. 通常情況下,K ≤M.

容易看出上述定義的Johnson 圖是一個(gè)無(wú)向圖, 文獻(xiàn)[25] 通過引入自循環(huán)將原始圖變?yōu)椴糠钟邢驁D,即目標(biāo)點(diǎn)僅會(huì)漫步到下一個(gè)目標(biāo)點(diǎn), 而不會(huì)漫步到其他非目標(biāo)點(diǎn). 這種漫步依然是通過轉(zhuǎn)移概率矩陣實(shí)現(xiàn),算法中漫步算子定義為W=RBRA. 散射算子RB,RA的定義與文獻(xiàn)[25]相同,只是將x,y變?yōu)?F,G)和(F′,G′). 具體如下:

這里|cF,G〉和|rF′,G′〉中的系數(shù)表示圖類積中某個(gè)點(diǎn)的轉(zhuǎn)移概率. 如圖2 所示, 左圖是原始圖, 其中標(biāo)號(hào)5是目標(biāo)點(diǎn), 右圖則是引入自循環(huán)后的修改的圖[28]. 原始圖中的量子漫步的轉(zhuǎn)移概率是均勻的, 但在修改的圖中并不是均勻的. 修改圖中的漫步算子W=RBRA與文獻(xiàn)[25] 中的量子漫步算法相同, 將根據(jù)修改圖的轉(zhuǎn)移概率矩陣來(lái)定義. 以RA為例, 當(dāng)|F,G〉為目標(biāo)點(diǎn)時(shí),|F,G〉|F′,G′〉將標(biāo)記為-|F,G〉|F′,G′〉,且不再散射到其他點(diǎn). 否則|F,G〉|F′,G′〉將依據(jù)定義的RA進(jìn)行散射.

并且, 為了在量子算法中讀取函數(shù)值, 文獻(xiàn)[20] 定義了量子OracleOf,g:|i,h,z〉 →|i,h,z ⊕Hi(h)(mod|Z|)〉,i ∈{0,1}, 這里H0(h):=f(h),H1(h):=g(h). 通過量子OracleOf,g將函數(shù)值讀出, 并存為L(zhǎng)F,G.

圖2 (a) 原始圖, (b) 修改圖Figure 2 (a) is original graph, (b) is modified graph

下面給出該算法的具體步驟:

步驟1: 定義初態(tài)為圖上點(diǎn)的均勻疊加態(tài)

步驟2: 查詢量子OracleOf,g, 此時(shí)系統(tǒng)狀態(tài)為

算法可以分為兩部分, 檢測(cè)算法(Claw-Detect algorithm) 和搜索算法(Claw-Search algorithm). 其中, 檢測(cè)算法作為搜索算法的子程序, 輔助得到最終的Claw(x,y). 所以下面我們給出檢測(cè)算法的具體算法步驟(見算法1), 而搜索算法僅給出算法思想.

?

下面介紹搜索算法的思想.

圖3 Claw-Search 算法思想Figure 3 Idea of Claw-Search algorithm

如圖所示, 圖3 中X和Y分別表示函數(shù)f(x) 和g(y) 的自變量空間. 若X={x1,x2,··· ,xn},Y={y1,y2,··· ,yn}, 則X1={x1,x2,··· ,xn/2},X2={xn/2+1,··· ,xn},Y1={y1,y2,··· ,yn/2},Y2={yn/2+1,··· ,yn}. Claw-Finding 問題中通常|X|≤|Y|, 因此算法優(yōu)先判斷搜索空間Y的大小. 如果Y=cX(其中c表示某個(gè)常數(shù)), 直接將X和Y以4-ary 搜索執(zhí)行Detect 算法. 若存在Claw 于集合(X1,Y1) 中, 則將(X1,Y1) 作為新的搜索空間(X,Y). 重復(fù)執(zhí)行直至搜索空間X和Y足夠小. 如果|Y|≥|X|2, 則將Y以2-ary 搜索執(zhí)行Detect 算法, 直至Y=cX, 然后重復(fù)執(zhí)行上述4-ary 搜索判斷Claw. 最后, 當(dāng)搜索空間X和Y降為O(1) 時(shí), 通過經(jīng)典查詢即可獲得目標(biāo)Claw.

4.2 應(yīng)用Claw-Finding 量子算法分析NTRU 密碼

現(xiàn)在, 我們根據(jù)Claw-Finding 算法給出對(duì)NTRU 密碼的量子攻擊. 首先, 構(gòu)造函數(shù)f:X →Z和g:Y →Z, 其中f(x)=(-xH(modq)) (modp),g(y)=(yH(modq)) (modp), 即x對(duì)應(yīng)f3,y對(duì)應(yīng)(f1f2),z ∈Z={0,1,··· ,p-1}. 應(yīng)用Claw-Finding 算法找到一對(duì)(x,y), 使得f(x)=g(y). 即找到了對(duì)應(yīng)的(f3,f1f2), 計(jì)算f=f1f2+f3可得NTRU 的私鑰多項(xiàng)式. 當(dāng)|X|=K,|Y|=M, Claw-Finding算法找到一對(duì)Claw(x,y) 的復(fù)雜度為

然而, 在原Claw-Finding 算法中兩個(gè)函數(shù)的輸出均為單比特. 而在NTRU 密碼中, 函數(shù)的輸出為比特串, 因?yàn)椴徽撌?f1f2H(modq)) (modp) 還是(-f3H(modq)) (modp), 計(jì)算所得的結(jié)果都是一個(gè)向量. 因此, 這里我們需要通過修改Claw-Finding 算法以達(dá)到攻擊NTRU 的目的. 具體地, 在得到量子態(tài)|(f1f2H(modq)) (modp)〉(用|φa〉表示) 和|(-f3H(modq)) (modp)〉(表示為|φb〉) 后, 計(jì)算兩個(gè)量子態(tài)的重疊程度(Overlap) 表示為z(φa,φb) =|〈φa|φb〉|2. 在量子環(huán)境下若兩個(gè)比特串完全相等, 則兩個(gè)比特串的內(nèi)積(即〈φa|φb〉) 為1; 否則為0. 因此我們可以用z(φa,φb) 來(lái)判斷兩個(gè)比特串(即兩個(gè)向量) 是否相等. Overlap 的計(jì)算參考文獻(xiàn)[29], 具體由定理2 給出.

定理2 給定兩個(gè)量子態(tài)Ua|0〉=|φa〉,Ub|0〉=|φb〉, 定義量子態(tài)

下面, 我們通過修改的Claw-Finding 算法給出對(duì)NTRU 公鑰密碼的攻擊. 首先, 通過訪問量子Oracle 得到初態(tài)(15), 觀察發(fā)現(xiàn)公式(15)可重寫為

(1) 制備量子態(tài)

這里

|0〉1表示單比特|0〉態(tài);

(2) 對(duì)|0〉1|ψ12〉和|0〉1|ψ22〉做量子交換測(cè)試(quantum swap test) 操作可得

(3) 應(yīng)用定理2 于|ψ2〉可得

(4) 對(duì)|0〉1|ψ12〉和|0〉1|ψ22〉做逆量子交換測(cè)試操作可得

至此,|ψ4〉中已得到每一組的|F,G〉和|F′,G′〉對(duì)應(yīng)(x,y) 的函數(shù)值(f(x),g(y)) 的內(nèi)積. 若對(duì)應(yīng)的(x,y) 為Claw, 則(f(x),g(y)) 的內(nèi)積為1; 否則(f(x),g(y)) 的內(nèi)積為0.|LF〉和|LG〉(|LF′〉和|LG′〉)對(duì)應(yīng)的每一個(gè)函數(shù)值均可通過上述操作, 得到對(duì)應(yīng)值的內(nèi)積, 我們用|TF,G〉(|TF′,G′〉) 表示. 算法的檢測(cè)部分為檢測(cè)F,G(F′,G′) 對(duì)應(yīng)的函數(shù)值|LF〉和|LG〉(|LF′〉和|LG′〉) 是否相等: 若|TF,G〉|TF′,G′〉為|00〉, 則F,G和F′,G′中均不存在Claw; 否則認(rèn)為F,G或F′,G′中存在Claw. 具體地, 檢測(cè)|F,G〉和|F′,G′〉中是否存在Claw, 也即檢測(cè)對(duì)應(yīng)的量子態(tài)|F,G〉和|F′,G′〉是否為目標(biāo)點(diǎn), 通過使用酉操作2|00〉〈00|-I作用到|TF,G〉|TF′,G′〉上即可實(shí)現(xiàn)目標(biāo)量子位翻轉(zhuǎn).

綜上所述, 在考慮引理1 和2 的情況下應(yīng)用修改的 Claw-Finding 量子算法可以在復(fù)雜度為O((|f1f2|/N)1/2) 下得到對(duì)應(yīng)的Claw(f3,f1f2). 表2 中給出文獻(xiàn)[19] 與本文所提攻擊的比較.

表2 文獻(xiàn)[19] 與本文所提攻擊與之間的比較Table 2 Comparison of quantum attack between Ref. [19] and proposed attack

雖然本文提出的量子攻擊復(fù)雜度與文獻(xiàn)[19] 相同, 但所提攻擊避免了應(yīng)用Grover 算法時(shí)強(qiáng)量子Oracle 的前提假設(shè), 并且文獻(xiàn)[19] 需要在每次Oracle 迭代中都需要調(diào)用指數(shù)大的列表, 而本文所提攻擊不需要這些額外的消耗.

5 總結(jié)

本文分析了Fluhrer 提出基于Grover 搜索算法對(duì)NTRU 公鑰密碼的攻擊. 該攻擊存在一個(gè)強(qiáng)量子Oracle 的前提假設(shè), 所需的量子Oracle 實(shí)現(xiàn)難度較大, 且需要維護(hù)O(|f3|/N) 的指數(shù)大列表. 針對(duì)這些缺陷, 本文基于修改的Claw-Finding 算法給出對(duì)NTRU 的新的量子攻擊. 其中, 修改的Claw-Finding量子算法中定義的函數(shù)輸出為多比特串. 通過引入量子幅度放大和相位估計(jì)計(jì)算兩個(gè)函數(shù)輸出比特串的內(nèi)積, 算法能有效識(shí)別目標(biāo)量子態(tài). 在與文獻(xiàn)[19] 所提量子攻擊具有相同攻擊復(fù)雜度的情況下, 本文提出的攻擊有效地避免了強(qiáng)量子Oracle 的假設(shè), 并且不需要維護(hù)指數(shù)大列表, 減少了資源消耗.