一種在基于格的加密方案中搜索解密失敗密文的方法*

陳昱帆, 陳輝焱, 張 珍, 張亞峰

北京電子科技學(xué)院, 北京 100070

1 引言

1.1 背景介紹

現(xiàn)代公鑰密碼的安全性大多數(shù)基于因子分解與離散對(duì)數(shù)問(wèn)題. 然而, 由于量子計(jì)算機(jī)的發(fā)展, 世界對(duì)后量子密碼的需求與日俱增. 格上的數(shù)學(xué)困難問(wèn)題被認(rèn)為在量子環(huán)境下仍然難解. 因此, 基于格的密碼作為一種后量子密碼而備受關(guān)注. 基于格的密碼具有廣泛的應(yīng)用, 包括數(shù)字簽名[1,2]、零知識(shí)證明[3,4]、公鑰加密[5,6]與密鑰封裝等. 與其他后量子公鑰加密方案相比, 基于格的公鑰加密方案有著嚴(yán)格的可證明安全、靈活的安全等級(jí)、較小的計(jì)算量. 總之, 基于格的公鑰加密方案是最好的后量子公鑰加密方案之一. 美國(guó)國(guó)家安全局(NIST) 正在公開(kāi)征集后量子公鑰加密方案, 此時(shí)已經(jīng)進(jìn)行到了第三輪, 其中很多基于格的公鑰加密方案入選了決賽, 例如saber[7]與kyber[8].

基于格的公鑰加密方案與密鑰封裝方案都缺乏完美的正確性, 即使在加密過(guò)程中使用了正確的公鑰與正確的加密方法, 仍然有可能發(fā)生加解密不一致. 本文中將加解密不一致的情況稱為解密失敗, 將導(dǎo)致解密失敗的密文稱為解密失敗密文. 解密失敗是由私鑰與密文的共同作用所導(dǎo)致的結(jié)果, 解密失敗密文會(huì)泄露私鑰的信息, 進(jìn)而影響方案的安全性. 由解密失敗密文而推測(cè)私鑰的攻擊方法在本文中被稱為解密失敗攻擊.

為了抵抗解密失敗攻擊, 大多數(shù)基于格的公鑰加密方案會(huì)盡可能減少解密失敗發(fā)生的概率. 然而降低解密失敗概率必須調(diào)整方案參數(shù), 導(dǎo)致方案的性能降低. 在NIST 公開(kāi)征集的候選方案中, 解密失敗概率普遍低于2-120. 部分方案會(huì)為了增加方案性能而選取較高的解密失敗概率, 然后通過(guò)增加糾錯(cuò)碼來(lái)降低解密失敗概率[9]. 糾錯(cuò)碼可以顯著降低解密失敗概率, 但是解密失敗概率仍然不為0, 攻擊者還是可以從解密失敗密文中獲得私鑰信息.

因此, 研究如何在基于格的加密方案中搜索解密失敗密文, 對(duì)基于格的加密方案的安全性有重要意義.

1.2 相關(guān)工作

在LWE 問(wèn)題提出之前, 針對(duì)基于格的公鑰加密方案的解密失敗攻擊就已經(jīng)被提出. James 和Joux在文獻(xiàn)[10] 中提出了針對(duì)NTRU 的解密失敗攻擊, 然后又對(duì)其加以拓展[11,12]. 之后, Fluhrer 提出了針對(duì)基于Ring-LWE 問(wèn)題的方案的解密失敗攻擊[13], 然后Betu 在文獻(xiàn)[14] 中對(duì)其進(jìn)行了拓展.

然而, 上述所有的解密失敗攻擊都有一個(gè)使用前提: 攻擊者必須使用特定的密文. 而文獻(xiàn)[15] 與[16]中提出的FO 轉(zhuǎn)換可以將選擇明文安全的公鑰加密方案轉(zhuǎn)換為選擇密文安全的密鑰封裝方案, 并且不允許攻擊者隨意創(chuàng)造密文. 因此, 上述的解密失敗攻擊都無(wú)法應(yīng)用于FO 轉(zhuǎn)換.

2018 年, D’Anvers 等人在文獻(xiàn)[17] 中提出了一種在基于格的加密方案中搜索解密失敗密文的方法,并將其命名為“failure boosting”. 此攻擊方法可以應(yīng)用于所有的基于LWE/LWR 問(wèn)題的公鑰加密與密鑰封裝方案. 之后在2019 年, D’Anvers 等人在文獻(xiàn)[18] 中對(duì)“failure boosting” 進(jìn)行了進(jìn)一步的分析與拓展. 同年, D’Anvers 等人改進(jìn)了“failure boosting”, 提出了一種新的搜索解密失敗密文的方法, 并將其命名為“directional failure boosting”[19].與此同時(shí), Guo 等人提出了兩種分別針對(duì)LAC[20]和SS-NTRUPKE[21]的解密失敗攻擊. 2020 年, Bindel 和Schank 證明了沒(méi)有產(chǎn)生解密失敗的密文也可以用于解密失敗攻擊[22].

盡管解密失敗攻擊已得到了有效的優(yōu)化, 但是仍然需要很高的計(jì)算量, 因此上述方法的有效性難以直接通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證.

1.3 本文貢獻(xiàn)

D’Anvers 等人提出的“directional failure boosting” 有著一個(gè)不合理的假設(shè): 在“directional failure boosting” 中, D’Anvers 等人將私鑰設(shè)定為一個(gè)多項(xiàng)式向量,并且將私鑰的l2-模設(shè)定為私鑰中的多項(xiàng)式的系數(shù)所組成的向量的l2-模. D’Anvers 等人假設(shè)私鑰中所有的系數(shù)在方案給定的分布中隨機(jī)選取, 并且在選取時(shí)相互獨(dú)立, 進(jìn)而得出私鑰的l2-模的分布函數(shù).

在單密鑰攻擊的前提下, 私鑰的l2-模是一個(gè)固定的數(shù)值. 僅僅利用私鑰中系數(shù)的分布很難準(zhǔn)確推測(cè)出私鑰的l2-模. 本文中提出了一種新的搜索解密失敗密文的方法, 該方法從解密失敗密文的數(shù)量與解密查詢的次數(shù)中提取出私鑰的信息, 然后得出一個(gè)新的私鑰的l2-模的分布函數(shù), 進(jìn)而改進(jìn)了“directional failure boosting”. 第4 節(jié)中的實(shí)驗(yàn)表明, 本文提出的方法比“directional failure boosting” 更加有效.

2 基礎(chǔ)知識(shí)

2.1 格密碼基礎(chǔ)知識(shí)

2.1.1 數(shù)學(xué)知識(shí)

2.1.2 LWE 問(wèn)題

同時(shí)還存在著Mod/Ring-LWE 問(wèn)題. 將上述LWE 問(wèn)題中的Zq更改為Rq來(lái)獲得Rq上的矩陣和向量. 如果上述維度l不等于1, 那么就形成了Mod-LWE 問(wèn)題; 如果l等于1, 就形成了Ring-LWE 問(wèn)題.

2.1.3 基于LWE 問(wèn)題的公鑰加密方案

D’Anvers 等在文獻(xiàn)[17,19] 中總結(jié)出基于LWE 問(wèn)題的公鑰加密方案的通用構(gòu)架, 本文將簡(jiǎn)要描述.

公鑰加密方案包括密鑰生成算法、加密算法和解密算法. 下面, Gen 代表密鑰生成算法, Enc 代表加密算法, Dec 代表解密算法. 定義M ?Rq代表明文空間. 明文中的多項(xiàng)式的系數(shù)從{0,1}中選取. 下述Enc 中的r是一段比特串.x ←χ(Rq;r) 代表將r看做隨機(jī)選取而得的比特串, 并利用r在分布χ(Rq)中選取x.

在文獻(xiàn)[19] 中, D’Anvers 等人定義χs、χe、χs′、χe′為四個(gè)相同的期望值為0 的高斯分布, 并且分布的方差很小. 本文中假定上述四個(gè)分布都是以零為中心的對(duì)稱離散分布, 并且取值空間很小.

很多基于格的公鑰加密方案都有著較高的帶寬. 所有在實(shí)際應(yīng)用過(guò)程中, 很多加密方案都會(huì)對(duì)密文進(jìn)行壓縮. 而壓縮會(huì)產(chǎn)生一個(gè)額外的誤差, 這個(gè)誤差會(huì)影響解密失敗. 在文獻(xiàn)[19] 中, D’Anvers 等人僅僅考慮上述模型下的加密方案, 沒(méi)有考慮密文的壓縮. 本文中的方案作為文獻(xiàn)[19] 中“diectional failure boosting” 的改進(jìn), 也不考慮上述密文壓縮的問(wèn)題.

為了將選擇明文安全的公鑰加密方案轉(zhuǎn)換為選擇密文安全的密鑰封裝方案, 很多方案設(shè)計(jì)者會(huì)選擇FO 轉(zhuǎn)換[15,16]. 一個(gè)密鑰封裝方案包括封裝算法和拆封算法. 本文中將封裝算法記為Encaps, 將拆封算法記為Decaps. 下述H() 與G() 代表在密鑰封裝方案中所使用的兩個(gè)哈希方程, 其輸入可以是任意數(shù)值,輸出是一段可以近似看作隨機(jī)的比特串.

為了更方便的表達(dá)解密失敗, 需要定義出下述多項(xiàng)式和向量.

定義1

然后, 解密出的明文m′可以表示如下:

在上述加密方案中, 本文設(shè)定qt=/4」. 可以發(fā)現(xiàn),‖STC+G‖∞＞qt與m′/=m可以近似看作等價(jià),所以, 可以認(rèn)為‖STC+G‖∞＞qt時(shí)解密失敗才會(huì)發(fā)生.

根據(jù)公式(1), 可以發(fā)現(xiàn):

因?yàn)镾和C都是由2l個(gè)n-1 級(jí)多項(xiàng)式組成的向量, 所以每個(gè)STC中的系數(shù)都是由2l*n個(gè)數(shù)值相加得到.G中的系數(shù)是從χe′中選取而來(lái). 在本文的設(shè)定中,χs、χe、χs′、χe′都是以0 為中心的離散分布, 并且取值空間很小. 因此,G中的系數(shù)的絕對(duì)值與STC中的系數(shù)的絕對(duì)值比起來(lái), 非常小,P(‖STC+G‖∞＞qt)≈P(‖STC‖∞＞qt). 在文獻(xiàn)[19] 中, D’Anvers 等人也直接忽視了G的影響.P(‖STC‖∞＞qt) 可以寫作:

本文中, 將‖STC‖∞＞qt描述為STC產(chǎn)生了解密失敗. 如果STC中的某個(gè)系數(shù)的絕對(duì)值大于qt,本文中描述為這個(gè)系數(shù)產(chǎn)生了解密失敗.

2.1.4 選擇密文安全

定義κ代表密鑰K的選擇空間. 一個(gè)攻擊者A攻擊密鑰封裝方案的優(yōu)勢(shì)由下述公式定義. 如果該優(yōu)勢(shì)可以忽略, 那么密鑰封裝方案可以被認(rèn)為選擇密文安全.

2.2 D’Anvers 的方法

本小節(jié)將簡(jiǎn)述D’Anvers 的“failure boosting” 和“directional failure boosting” 兩種方法. 對(duì)于詳細(xì)細(xì)節(jié)與原理, 請(qǐng)參閱文獻(xiàn)[17,19].

在文獻(xiàn)[17] 中, D’Anvers 等人提出了一種獲得解密失敗密文的方法, 并將其命名為“failure boosting”. 然后在文獻(xiàn)[19] 中, D’Anvers 等人又提出了一種“failure boosting” 的改進(jìn), 并將其命名為“directional failure boosting”. 兩種方法的大致思路如下:

第一步: 獲得一個(gè)密文(C,G), 然后計(jì)算出該密文產(chǎn)生解密失敗的概率, 如果該概率大于一定數(shù)值, 就將該密文選為“弱密文”.

第二步: 獲得了一定量的弱密文之后, 將所有的弱密文輸入解密查詢, 意圖獲得解密失敗.

兩種方法的差別在于: 對(duì)于給定密文, 如何計(jì)算該密文的解密失敗概率. 下面將簡(jiǎn)要介紹兩種方法的差別.

2.2.1 failure boosting

“failure boosting” 可以應(yīng)用于所有基于LWE/LWR 問(wèn)題的加密方案.

對(duì)于給定的C和G, 假定S中的系數(shù)從分布χs和χe中隨機(jī)選取且相互獨(dú)立. 因此,STC中的每個(gè)系數(shù)都可以看作由2l*n個(gè)相互獨(dú)立的數(shù)值相加而來(lái), 進(jìn)而都可以看作從同一個(gè)高斯分布中選取. 且STC中的系數(shù)之間可以近似看做相互獨(dú)立.

D’Anvers 等人通過(guò)下述公式計(jì)算出高斯分布的方差. 設(shè)Cij代表C中第i+1 個(gè)多項(xiàng)式的Xj的系數(shù).STCi代表STC中Xi的系數(shù). var(STCi) 代表STCi的分布的方差. 因?yàn)棣謘和χe都以0 為中心,所以STCi的分布的期望值為0.

將解密失敗記作事件F. 然后用下述公式計(jì)算給定密文(C,G) 的解密失敗概率.

2.2.2 directional failure boosting

盡管“directional failure boosting” 是“failure boosting” 的一個(gè)改進(jìn), 但“directional failure boosting” 有兩個(gè)局限性:

在單目標(biāo)攻擊的情況下,‖S‖2是一個(gè)固定的數(shù)值. D’Anvers 等人缺少了對(duì)‖S‖2的合理預(yù)測(cè), 而是直接假設(shè)其在相應(yīng)的分布中隨機(jī)選取. 這樣很顯然會(huì)影響弱密文篩選的準(zhǔn)確性.

2.2.3 恢復(fù)私鑰

僅僅獲得解密失敗密文不會(huì)影響方案的準(zhǔn)確性, 但是解密失敗密文可以應(yīng)用于某些私鑰恢復(fù)攻擊, 如文獻(xiàn)[17,21] 中的方法.

2.3 改進(jìn)“directional failure boosting”

根據(jù)第2.2.2 節(jié)所述, “directional failure boosting” 缺少了對(duì)‖S‖2的預(yù)測(cè). 并且在“directional failure boosting” 使用之前, 需要先使用“failure boosting” 來(lái)獲得至少一個(gè)解密失敗密文.

本文中假定攻擊者首先使用“failure boosting” 進(jìn)行了多次解密查詢, 并且獲得了至少一個(gè)解密失敗密文. 然后本文將詳細(xì)闡述如何應(yīng)用“failure boosting” 中的解密查詢次數(shù)與解密失敗密文個(gè)數(shù)來(lái)預(yù)測(cè)‖S‖2.

2.4 方法簡(jiǎn)介

由于本文中的方法是針對(duì)“directional failure boosting” 的一個(gè)提升, 所以本文中的方法也僅僅可以應(yīng)用于單目標(biāo)攻擊. 在單目標(biāo)攻擊的情況下, 本文將攻擊者要攻擊的私鑰稱為目標(biāo)私鑰.

根據(jù)公式(6), 可以發(fā)現(xiàn): 對(duì)于一個(gè)特定的私鑰, 解密失敗不僅僅取決于輸入查詢的密文, 還取決于該私鑰. 假設(shè)輸入解密查詢的密文從某個(gè)特定的分布中隨機(jī)選擇, 那么就可以從解密失敗概率中獲得私鑰的信息.

然而, 上述思路存在如下兩個(gè)需要解決的問(wèn)題:

P1: 只有弱密文才能輸入解密查詢. 想要實(shí)現(xiàn)上述思路, 就必須計(jì)算出弱密文的分布.

P2: 對(duì)于某個(gè)特定的目標(biāo)私鑰, 攻擊者并不知道該私鑰的解密失敗概率.

為了解決上述兩個(gè)問(wèn)題,本文將注意力集中于“failure boosting”.下面將介紹如何利用“failure boosting” 來(lái)解決上述兩個(gè)問(wèn)題.

D’Anvers 等人在“failure boosting” 將弱密文定義如下: 假設(shè)私鑰中的系數(shù)都是從χs或χe中隨機(jī)選取且相互獨(dú)立, 對(duì)于給定密文通過(guò)公式(6) 計(jì)算出解密失敗概率, 如果解密失敗概率大于一定數(shù)值, 就將其選擇為弱密文. 本文中將弱密文中的系數(shù)所服從的分布稱為“弱密文分布”.

利用“failure boosting” 中弱密文的概念, 通過(guò)貝葉斯公式可以計(jì)算出“failure boosting” 中的弱密文分布. 然后假設(shè)輸入解密查詢的弱密文的系數(shù)都是從弱密文分布中隨機(jī)選取, 就解決了問(wèn)題P1. 在2.5 節(jié)中, 將會(huì)對(duì)這一步驟的原理進(jìn)行詳細(xì)的闡述.

在獲得“failure boosting” 的弱密文分布之后, 本文中假設(shè)攻擊者使用“failure boosting” 針對(duì)目標(biāo)私鑰進(jìn)行了數(shù)次解密查詢并且獲得了至少一個(gè)解密失敗密文. 利用解密查詢次數(shù)以及所獲得的解密失敗密文的個(gè)數(shù), 可以推測(cè)出目標(biāo)私鑰的解密失敗概率, 進(jìn)而解決問(wèn)題P2.

綜上, 在利用了“failure boosting” 獲得了至少一個(gè)解密失敗密文之后, 可以利用解密失敗密文的個(gè)數(shù)與解密查詢的次數(shù)來(lái)推測(cè)出私鑰的信息.

在解決了問(wèn)題P1 與P2 之后, 將注意力集中到“directional failure boosting”. 如2.2.2 節(jié)中所述, 在“directional failure boosting” 使用之前, 必須首先使用“failure boosting” 來(lái)獲得至少一個(gè)解密失敗密文; 并且“directional failure boosting” 中缺少對(duì)‖S‖2的合理推測(cè). 因此, 在使用“failure boosting” 獲得了至少一個(gè)解密失敗密文之后, 攻擊者可以利用解密查詢次數(shù)與解密失敗密文的個(gè)數(shù)來(lái)推測(cè)出私鑰的信息, 并將其轉(zhuǎn)換為‖S‖2的信息. 然后攻擊者就可以通過(guò)得出的‖S‖2的信息來(lái)改進(jìn)“directional failure boosting”.

本文中將上述方法的具體實(shí)現(xiàn)分為四個(gè)步驟:

第一步: 計(jì)算出“failure boosting” 中的弱密文分布. 這一步的目的是解決問(wèn)題P1. 在計(jì)算出之后, 可以假設(shè)“failure boosting” 中的弱密文的系數(shù)都是從其弱密文分布中隨機(jī)選取.

第二步: 計(jì)算出目標(biāo)私鑰的解密失敗概率的概率密度函數(shù). 這一步的目的是解決問(wèn)題P2. 如前文所述, 利用“failure boosting” 的解密查詢次數(shù)與解密失敗密文個(gè)數(shù), 可以推測(cè)出目標(biāo)私鑰的解密失敗概率的概率密度函數(shù).

第三步: 解決了問(wèn)題P1 與P2 之后, 可以獲得目標(biāo)私鑰的部分信息. 然后這一步的目的就是將私鑰的信息轉(zhuǎn)化為‖S‖2的分布函數(shù).

第四步: 在獲得了‖S‖2的分布函數(shù)之后, 使用其來(lái)改進(jìn)“directional failure boosting”.

2.5 第一步: 計(jì)算弱密文分布

本小節(jié)的目的是獲得“failure boosting” 中的弱密文分布. 在獲得了弱密文分布之后, 就可以假設(shè)“failure boosting” 中輸入解密查詢的弱密文的系數(shù)都是弱密文分布中隨機(jī)選取, 進(jìn)而解決問(wèn)題P1.

在本小節(jié)的最后額外說(shuō)明, 在S固定, 并且C中的系數(shù)在弱密文分布中隨機(jī)選取的情況下, 由于C中的各個(gè)系數(shù)之間的協(xié)方差為0, 所以STC中的系數(shù)可以近似看作高斯分布.

首先將“failure boosting” 中的弱密文的選擇標(biāo)準(zhǔn)進(jìn)行等價(jià)轉(zhuǎn)換.

在本小節(jié)中假設(shè)“failure boosting” 中的弱密文的選擇標(biāo)準(zhǔn)是解密失敗概率大于Pt. 已知對(duì)于給定的C和G, 在“failure boosting” 中將解密失敗概率表示為P(‖STC+G‖∞＞qt). 在本文的設(shè)定中,G的影響非常有限, 可以假設(shè)P(‖STC+G‖∞＞qt)≈P(‖STC‖∞＞qt), 文獻(xiàn)[19] 中也做出了同樣的假設(shè).

在本文的設(shè)定中,S和C都是2l維的多項(xiàng)式向量, 所以STC只包含一個(gè)多項(xiàng)式. 在“failure boosting” 中假設(shè)STC中的n個(gè)系數(shù)都是從相同的高斯分布中隨機(jī)選取并且相互獨(dú)立. D’Anvers 在文獻(xiàn)[18] 中說(shuō)明上述假設(shè)在沒(méi)有糾錯(cuò)碼的情況下是合理的. 由此, 可以得到: 1-P(‖STC‖∞＞qt)≈(1-P(|STCi|＞qt))n. 設(shè)定數(shù)值P′t, 令其滿足1-Pt=(1-P′t)n.

在上述公式中共有2l*n項(xiàng)元素, 并且所有元素之間相互獨(dú)立. 將前2l*n-1 項(xiàng)元素相加所得到的和近似看作一個(gè)高斯分布, 記為分布N′. 由于var(χs) 和var(χe) 都是已知的數(shù)值, 并且χe′和χs′已知,所以分布N′的期望值和方差可以通過(guò)計(jì)算輕松得到.

需要注意, 當(dāng)χe′與χs′都是高斯分布且相同, 并且var(χs)=var(χe) 的時(shí)候, 也可以將N′看作是一個(gè)卡方分布.

將密文被選為弱密文記為事件Fw.s′0在弱密文中的分布可以被下述公式計(jì)算出:

將弱密文中的s′i和e′i的分布分別記作χs′-new、χe′-new.

顯然, 所有的s′i都服從和s′0相同的分布. 若延續(xù)文獻(xiàn)[19] 中的參數(shù)設(shè)定, 可以得到相同的χs′-new和χe′-new. 而當(dāng)χs和χe不同的時(shí)候, 可以用相同的方法計(jì)算出χe′-new.

至此, 獲得了弱密文分布, 解決了問(wèn)題P1.

需要注意的是, 在C被選為弱密文的前提下, 其中的系數(shù)顯然已經(jīng)不滿足相互獨(dú)立.

然而, 根據(jù)2.1.3 節(jié)中所述,χs′和χe′都是以0 為中心的對(duì)稱分布. 通過(guò)公式(9) 可以得到χs′-new和χe′-new也都是以0 為中心的對(duì)稱分布. 根據(jù)協(xié)方差公式cov(a,b) =E(ab)-E(a)E(b), 可以得到弱密文C中的所有系數(shù)之間的協(xié)方差為0.

因此, 當(dāng)S是一個(gè)固定的私鑰,C中的系數(shù)從弱密文分布中選取的情況下,STC中的每個(gè)系數(shù)都可以近似地看作由2l*n個(gè)相互獨(dú)立的數(shù)值相加而來(lái), 然后近似地看作一個(gè)高斯分布. 顯然該高斯分布的期望值仍然為0, 參考公式(5), 該高斯分布的方差為‖EA‖22var(χs′-new)+‖SA‖22var(χe′-new).

2.6 第二步: 計(jì)算解密失敗概率的概率密度函數(shù)

首先獲得“failure boosting” 中的γ與解密失敗概率之間的一一映射.

在S為目標(biāo)私鑰、C中的系數(shù)在弱密文分布中選取的前提下,STC中每個(gè)系數(shù)的解密失敗概率可以表示為:

根據(jù)上述公式, 可以得知: 存在一個(gè)STC中每個(gè)系數(shù)的解密失敗概率與γ之間的一一映射. 進(jìn)而知道存在一個(gè)γ與STC的解密失敗概率的一一映射. 對(duì)于固定的γ, 假設(shè)STC中的系數(shù)之間相互獨(dú)立, 設(shè)相應(yīng)的STC的解密失敗概率為Pγ. 映射方程可以表示為:

然后本小節(jié)的剩余目的就是通過(guò)解密查詢次數(shù)與解密失敗密文個(gè)數(shù)來(lái)獲得一個(gè)γ的概率密度函數(shù).

假設(shè)私鑰S中的系數(shù)都是從分布χs和χe中選取而來(lái). 由于γ共由2l*n個(gè)相互獨(dú)立的數(shù)值相加得到, 所以可以將γ近似的看作服從高斯分布, 記為Nγ.

另外, 當(dāng)var(χs′-new) = var(χe′-new) 并且χs與χe相同且都是高斯分布的時(shí)候,Nγ也可以看作服從卡方分布.

至此, 獲得了γ的概率密度函數(shù). 最后, 利用貝葉斯公式, 帶入解密查詢次數(shù)與解密失敗密文的個(gè)數(shù),可以獲得γ的新的概率密度函數(shù), 記為fγnew. 假設(shè)“failure boosting” 中進(jìn)行了k次解密查詢并且獲得了k1個(gè)解密失敗密文, 可以得到:

由于上式的分母難以有效求出原函數(shù), 所以將其當(dāng)作離散的函數(shù), 并假設(shè)其取值為整數(shù)且間隔為1. 由于在實(shí)際的加密方案中S中系數(shù)的分布是離散的, 所以γ的分布本就是離散的, 上述假設(shè)相當(dāng)于將間隔相近的離散數(shù)值當(dāng)作同一個(gè)數(shù)值考慮.

需要注意的是在實(shí)際應(yīng)用中, 最有效的攻擊方法是利用“failure boosting” 獲得了一個(gè)解密失敗密文之后立刻轉(zhuǎn)而使用“directional failure boosting”, 所以在大部分情況下k1=1.

2.7 第三步: 獲得私鑰信息

現(xiàn)在, 問(wèn)題P1 和P2 都已經(jīng)解決, 可以開(kāi)始提取目標(biāo)私鑰的信息.

本小節(jié)中, 將會(huì)詳細(xì)解釋如何從現(xiàn)有信息中提取出目標(biāo)私鑰的信息, 然后將私鑰的信息轉(zhuǎn)化為‖S‖22的分布函數(shù).

2.7.1 提取私鑰信息

第一個(gè)目的是利用fγnew來(lái)獲得目標(biāo)私鑰中的系數(shù)的信息.

對(duì)于一個(gè)固定的目標(biāo)私鑰S, 假設(shè)密文C在弱密文分布中隨機(jī)選取. 如2.5 節(jié)所述,STC中的參數(shù)的分布的方差是γ, 可以寫作:

在沒(méi)有fγnew的情況下, 已知si和ei在選取時(shí)相互獨(dú)立. 所以上述公式的前2l*n-1 項(xiàng)可以看作一個(gè)高斯分布, 將其記為Nr.Nr的方差和期望值可以像Nγ一樣被計(jì)算出來(lái).

需要注意, 當(dāng)設(shè)定Nγ為卡方分布的時(shí)候,Nr也必須設(shè)為卡方分布.

在2.6 節(jié), 關(guān)于γ的新的概率密度函數(shù)已經(jīng)得到.s20的分布可以通過(guò)χs得到. 然后應(yīng)用貝葉斯公式將fγnew代入, 就可以得到一個(gè)新的s20的分布, 將其記為χs2-new:

2.7.2 獲得‖S‖2的分布函數(shù)

與公式(13) 相似, 為了獲得協(xié)方差, 將s20+s21記作t. 下一步的目的就是通過(guò)γ的新分布獲得t的新分布.

首先寫出在沒(méi)有fγnew的情況下,γ的表達(dá)式:知, 所以分布N′r的期望值和方差可以通過(guò)和Nr類似的方法得到.

在沒(méi)有任何私鑰信息的情況下,t的分布可以通過(guò)χs得到. 然后通過(guò)貝葉斯公式和γ的新分布, 可以獲得t的新的分布:

2.8 第四步: 提升“directional failure boosting”

在2.7 節(jié)的最后, 獲得了‖S‖2的分布. 將‖S‖2的分布函數(shù)代入公式(7), 就可以獲得一個(gè)更加有效的“directional failure boosting”.

3 討論

3.1 本文中的改進(jìn)方法的開(kāi)銷

對(duì)于大多數(shù)加密方案來(lái)說(shuō),私鑰S和密文C中的系數(shù)的選取范圍非常有限.在文獻(xiàn)[19]中,D’Anvers等人以saber[7]和kybe[8]作為參考來(lái)選擇參數(shù). 在saber[7]和kybe[8]中,S和C的系數(shù)的選取范圍都不超過(guò)10 個(gè)整數(shù).

但是有些加密方案中的S和C的系數(shù)選取范圍很大. 例如SS-NTRU-PKE 中,S和C的系數(shù)是從期望值為0、標(biāo)準(zhǔn)差為724 的離散高斯分布中選取而來(lái). 而過(guò)大的選取范圍會(huì)顯著影響本文中的方法的計(jì)算開(kāi)銷. 為了應(yīng)對(duì)上述情況, 可以將S中的系數(shù)的選取范圍分割為數(shù)個(gè)區(qū)間, 然后以區(qū)間為單位來(lái)進(jìn)行操作. 另外, 當(dāng)S和C中的系數(shù)的選取范圍增大時(shí), 為了保證解密失敗概率很低,q也必須相應(yīng)增大. 如SS-NTRU-PKE 中,q=230+213+1. 顯然,qt會(huì)隨著q的增大而增大, 進(jìn)而‖STC‖∞＞qt中的所有系數(shù)都會(huì)很大. 所以當(dāng)本文中的改進(jìn)方法在實(shí)際應(yīng)用過(guò)程中計(jì)算開(kāi)銷過(guò)大時(shí), 只需將‖STC‖∞＞qt中的所有系數(shù)都等比例縮小然后取整數(shù), 就可以顯著降低計(jì)算開(kāi)銷.

由于本文中的改進(jìn)方法是文獻(xiàn)[19] 中的“directional failure boosting” 的改進(jìn), 所以在本節(jié)中, 假設(shè)S和C中的系數(shù)的選取范圍都是非常有限的整數(shù)集合.

本文中的改進(jìn)方法的第一步僅僅需要對(duì)C的系數(shù)的選取空間進(jìn)行遍歷, 其計(jì)算開(kāi)銷可以直接忽略.

本文中的改進(jìn)方法的第二步的計(jì)算開(kāi)銷主要集中于γ的取值空間的遍歷. 將γ的所有可能的離散值的個(gè)數(shù)記為|γ|. 根據(jù)文獻(xiàn)[19] 中的參數(shù)選取,|γ|≈217. 在文獻(xiàn)[19] 中, D’Anvers 等人對(duì)使用“failure boosting” 獲得第一個(gè)解密失敗密文所需要的解密查詢次數(shù)進(jìn)行了預(yù)估, 認(rèn)為需要2102.21次解密查詢. 本文中假設(shè)對(duì)于給定數(shù)值x, 計(jì)算x2102.21需要27次運(yùn)算. 由于第二步對(duì)γ的每個(gè)取值的遍歷中, 指數(shù)運(yùn)算的開(kāi)銷占據(jù)了絕大部分, 所以本文中的改進(jìn)方法的第二步的計(jì)算開(kāi)銷大約為224. 由于γ的新的分布函數(shù)在之后數(shù)次用到, 所以可以消耗|γ| 大小的存儲(chǔ), 用來(lái)儲(chǔ)存γ的新的分布.

在本文的改進(jìn)方法的第三步中, 總計(jì)算開(kāi)銷大約為|γ|*|χs|2*22. 根據(jù)文獻(xiàn)[19] 中的參數(shù)選取, 大約為224. 另外, 如果在具體應(yīng)用時(shí),χs/=χe或χs′/=χe′, 那么第三步的計(jì)算開(kāi)銷就擴(kuò)大為4 倍.

如2.6 節(jié)所述, 本文中假設(shè)γ的取值范圍是離散且間隔為1 的. 如果在具體應(yīng)用的時(shí)候計(jì)算開(kāi)銷不可接受, 也可以通過(guò)改變假設(shè)中γ的離散間隔來(lái)減少計(jì)算開(kāi)銷.

在文獻(xiàn)[19] 中, D’Anvers 等人預(yù)測(cè): 在解密查詢次數(shù)沒(méi)有限制的情況下, 以1-e-1的概率獲得第二個(gè)解密失敗密文大約需要2110的計(jì)算開(kāi)銷. 根據(jù)文獻(xiàn)[19] 中的參數(shù)選取, 本文中的方法所造成的額外的計(jì)算開(kāi)銷僅僅需要230, 相較之下可以直接忽略.

3.2 與文獻(xiàn)[19] 中“directional failure boosting” 的對(duì)比

本文中所提出的方法是對(duì)“directional failure boosting” 的一個(gè)改進(jìn), 所以本小節(jié)中將本文的方法與“directional failure boosting” 進(jìn)行對(duì)比.

本文中的方法與“directional failure boosting” 的差異在于本文中的方法增加了額外的步驟. 如果“directional failure boosting” 的假設(shè)足夠理想, 那么本文中的方法不會(huì)帶來(lái)任何提升. 但是如前文所述,“directional failure boosting” 缺少對(duì)‖S‖2的預(yù)測(cè), 進(jìn)而導(dǎo)致弱密文的選擇不夠合理. 本文的方法通過(guò)增加對(duì)‖S‖2的預(yù)測(cè)來(lái)使弱密文的選擇更加合理, 進(jìn)而可以使“directional failure boosting” 更加有效.

另外, 本文中的方法有著比“directional failure boosting” 更加寬松的要求. 例如, 本文中的方法不要求χs、χe、χs′和χe′相同, 但是“directional failure boosting” 要求. 所以, 在某些情況下, 即使“directional failure boosting” 不可用, 攻擊者仍然可以用本文中的方法來(lái)獲得私鑰的信息.

4 實(shí)驗(yàn)驗(yàn)證本文中的方法所帶來(lái)的提升

盡管我們認(rèn)為本文中的方法可以為“directional failure boosting” 帶來(lái)提升, 但是難以從理論上量化具體的提升數(shù)值. 所以本節(jié)中, 將會(huì)用實(shí)驗(yàn)來(lái)量化本文中的方法所帶來(lái)的提升.

本文中的方法與“directional failure boosting” 的差別在于本文中的方法對(duì)‖S‖2做了額外的預(yù)測(cè).而“directional failure boosting” 則假設(shè)χs、χe、χs′和χe′都是相同的高斯分布, 然后認(rèn)為‖S‖22在相應(yīng)的卡方分布中隨機(jī)選取. 所以本節(jié)中, 將本文中的方法所獲得的‖S‖22的分布函數(shù)與“directional failure boosting” 中所使用的卡方分布進(jìn)行對(duì)比, 進(jìn)而驗(yàn)證本文中的方法所帶來(lái)的提升.

4.1 參數(shù)選取與假設(shè)

為了更加方便與“directional failure boosting” 進(jìn)對(duì)比, 本文的實(shí)驗(yàn)的參數(shù)選取會(huì)盡可能的滿足“directional failure boosting” 的要求. 在文獻(xiàn)[19] 中, D’Anvers 等人假設(shè)χs和χe是相同的離散高斯分布. 實(shí)驗(yàn)中我們參考了kyber768[8]的方法, 用中心二項(xiàng)分布來(lái)代替高斯分布, 生成私鑰. 具體的參數(shù)選取如下: 設(shè)定l=3、n=256, 對(duì)于每一個(gè)si, 采用下述方法生成. 而ei的生成方法與si相同.

在“directional failure boosting” 中, D’Anvers 等人假設(shè)χe和χs都是高斯分布, 然后利用卡方分布得到‖S‖的分布, 進(jìn)而得到‖S‖2的分布函數(shù). 需要注意的是, 由于理想的高斯分布難以實(shí)現(xiàn), 用中心二項(xiàng)分布來(lái)代替高斯分布是一種非常常見(jiàn)的方法, 在很多的加密方案中都被使用.

本文中的方法的使用前提是攻擊者已經(jīng)使用“failure boosting” 獲得至少一個(gè)解密失敗密文. 但是在實(shí)際應(yīng)用過(guò)程中, 使用“failure boosting” 獲得一個(gè)解密失敗密文需要很大的計(jì)算開(kāi)銷, 難以實(shí)現(xiàn). 所以本文根據(jù)一些假設(shè)來(lái)調(diào)整實(shí)驗(yàn).

已知在“failure boosting” 中, 只有弱密文會(huì)被輸入解密查詢. 在2.5 節(jié)中, 攻擊者可以獲得弱密文分布. 并且在本文的方法的第二步和第三步中, 僅僅用到了弱密文分布的方差, 沒(méi)有用到具體的弱密文.

所以, 實(shí)驗(yàn)中做出如下假設(shè):

假設(shè) 1 實(shí)驗(yàn)中不再設(shè)定 “failure boosting” 中弱密文的選擇標(biāo)準(zhǔn), 直接設(shè)定 var(χs′-new) =var(χe′-new)=3.

由于弱密文的選取標(biāo)準(zhǔn)可以由攻擊者隨意指定, 且弱密文分布的方差由弱密文的選取標(biāo)準(zhǔn)而確定, 所以, 在實(shí)驗(yàn)中, 弱密文分布的方差var(χs′-new) 和var(χe′-new) 也可以由攻擊者任意指定. 上述假設(shè)1 可以認(rèn)為合理.

通過(guò)公式(10) 和(11), 可以計(jì)算出給定私鑰在“failure boosting” 中的解密失敗概率. 然后, 在區(qū)間(0,1) 之間的均勻分布中任意選取一個(gè)小數(shù). 通過(guò)這個(gè)小數(shù), 可以模擬一次解密查詢:

如果這個(gè)小數(shù)的數(shù)值小于等于給定私鑰的解密失敗概率, 那么就認(rèn)為進(jìn)行了一次解密查詢并且發(fā)生了一次解密失敗. 否則, 認(rèn)為進(jìn)行了一次解密查詢但沒(méi)有發(fā)生解密失敗.

通過(guò)上述方法, 對(duì)于給定私鑰, 可以在“failure boosting” 中獲得一個(gè)相對(duì)合理的解密查詢次數(shù)和解密失敗密文個(gè)數(shù). 所以實(shí)驗(yàn)中做出如下假設(shè):

假設(shè)2 實(shí)驗(yàn)中認(rèn)為公式(10) 和(11) 是正確的. 然后通過(guò)在區(qū)間(0,1) 之間的均勻分布中任意選取一個(gè)小數(shù)來(lái)模擬一次解密查詢. 如果這個(gè)小數(shù)的數(shù)值小于等于給定私鑰的解密失敗概率, 那么就認(rèn)為進(jìn)行了一次解密查詢并且發(fā)生了一次解密失敗. 否則, 認(rèn)為進(jìn)行了一次解密查詢但沒(méi)有發(fā)生解密失敗.

公式(10)和(11)的正確性依賴于以下兩點(diǎn): 在S固定、C中的系數(shù)從弱密文分布中隨機(jī)選取的前提下,

(1) 將STC中的系數(shù)看做從高斯分布中隨機(jī)選取.

(2) 假設(shè)STC中的系數(shù)相互獨(dú)立.

第(1) 點(diǎn)在2.5 節(jié)末尾進(jìn)行了說(shuō)明, 第(2) 點(diǎn)在文獻(xiàn)[18] 中得到了證明.

在公式(10) 和(11) 正確的前提下, 通過(guò)公式計(jì)算出的給定私鑰的解密失敗概率是合理的, 所以利用假設(shè)2 獲得的解密查詢次數(shù)與解密失敗密文個(gè)數(shù)也是合理的. 所以假設(shè)2 可以被認(rèn)為合理.

通過(guò)上述兩個(gè)假設(shè), 可以在試驗(yàn)中直接獲得解密查詢次數(shù)和解密失敗密文個(gè)數(shù), 而不需要真正的解密查詢. 然后, 為了進(jìn)一步減少實(shí)驗(yàn)的計(jì)算開(kāi)銷, 設(shè)定qt=300.

最后, 由于最有效的攻擊方法是在使用“failure boosting” 獲得一個(gè)解密失敗密文之后立刻轉(zhuǎn)而使用“directional failure boosting”, 所以在公式(12) 中, 設(shè)k1=1.

4.2 本文中獲得的分布的準(zhǔn)確度

在實(shí)驗(yàn)中, 我們首先扮演挑戰(zhàn)者, 生成私鑰, 然后使用4.1 節(jié)中的方法模擬解密查詢, 直到獲得一次解密失敗. 最后將解密查詢次數(shù)與解密失敗密文個(gè)數(shù)發(fā)送給攻擊者.

然后扮演攻擊者, 使用本文中的方法獲得一個(gè)‖S‖22的分布.

最后, 為了量化本文中的方法獲得的‖S‖22分布的準(zhǔn)確度, 我們將目標(biāo)私鑰的‖S‖22分別帶入到本文中的方法獲得的概率密度函數(shù)、“directional failure boosting” 所使用的卡方分布的概率密度函數(shù)之中, 然后進(jìn)行對(duì)比.

基于以上假設(shè), 我們?cè)趍atlab2020b 中進(jìn)行了實(shí)驗(yàn).

4.3 本文中的方法所帶來(lái)的提升

在獲得了‖S‖2的分布之后, 實(shí)驗(yàn)的目的就是量化本文中的‖S‖2的分布能為“directional failure boosting” 帶來(lái)多大的提升. 然而, 由于客觀條件的限制, 結(jié)果難以直接通過(guò)實(shí)驗(yàn)驗(yàn)證.

圖1 實(shí)驗(yàn)中adv1 的數(shù)值Figure 1 adv1 in experiment

圖2 實(shí)驗(yàn)中adv2 的數(shù)值Figure 2 adv2 in experiment

圖3 實(shí)驗(yàn)中adv3 的數(shù)值Figure 3 adv3 in experiment

4.3.1 “directional failure boosting” 的效率

從上述公式可以看出, cos(θSE)cos(θC(r)E)+sin(θSE)sin(θC(r)E)cos(t) 可以看作是cos(θSC(r)) 的一個(gè)預(yù)測(cè). 所以實(shí)驗(yàn)中做出下列假設(shè):

假設(shè)3 對(duì)于一個(gè)給定的密文C,假設(shè)對(duì)于所有的r ∈{0,1,··· ,2n-1},攻擊者可以獲得cos(θSC(r)).

需要注意,在“directional failure boosting”中,攻擊者僅僅可以獲得一個(gè)cos(θSC(r))的分布,而不是cos(θSC(r)). 只有當(dāng)該分布足夠合理的時(shí)候, 上述假設(shè)才可以被認(rèn)為合理. 在文獻(xiàn)[19] 中, D’Anvers 等人認(rèn)為“directional failure boosting” 中cos(θSC(r)) 的分布是合理的, 然后利用該分布來(lái)預(yù)測(cè)“directional failure boosting”的攻擊效率.并且D’Anvers 等人認(rèn)為隨著解密失敗密文個(gè)數(shù)的增加,“directional failure boosting” 可以獲得近乎準(zhǔn)確的cos(θSC(r)) 的值. 另外, 當(dāng)攻擊者可以獲得cos(θSC(r)) 時(shí), 弱密文的篩選的準(zhǔn)確程度將僅僅取決于‖S‖2的分布的準(zhǔn)確程度,所以假設(shè)3 可以使實(shí)驗(yàn)很好的反映本文中獲得的‖S‖2的分布在實(shí)際中所帶來(lái)的提升. 所以, 假設(shè)3 在本實(shí)驗(yàn)中可以被認(rèn)為是合理的.

接下來(lái)將會(huì)解釋“directional failure boosting” 如何在假設(shè)3 成立的條件下運(yùn)行. 對(duì)于一個(gè)給定的密文C, 在cos(θSC(r)) 的情況下, 公式(7) 可以寫作:

下面將解釋, 對(duì)于一個(gè)Pt, 如何獲得ωPt和QPt.

如文獻(xiàn)[18] 中所述, 在‖S‖2和‖C‖2確定的前提下,STC中的系數(shù)然可以被看作相互獨(dú)立. 所以對(duì)于r ∈{0,1,··· ,n-1},θSC(r)之間可以看作相互獨(dú)立. 對(duì)于r ∈{n,1,··· ,2n-1}, 有cos(θSC(r)) =-cos(θSC(r-n)).

文獻(xiàn)[19] 中所述,‖C‖2和cos(θSC(r)) 可以看作相互獨(dú)立.

通過(guò)上述假設(shè), 當(dāng)C中的系數(shù)與S中的系數(shù)選取方式相同時(shí), 可以得知‖C‖2和cos(θSC(r)) 的分布.在給定‖S‖2的分布和Pt的情況下, 可以計(jì)算出αPt和βPt, 進(jìn)而計(jì)算出ωPt和QPt.

在文獻(xiàn)[19] 中, D’Anvers 等人在選取Pt的數(shù)值的時(shí)候, 會(huì)選取使得ωPt的值取到最小值的Pt. 在本文的實(shí)驗(yàn)中, 會(huì)延續(xù)這一設(shè)定.

4.3.2 本文中的方法所帶來(lái)的提升

在單目標(biāo)攻擊的時(shí)候,‖S‖2是一個(gè)固定的數(shù)值, 所以實(shí)際中的βPt的數(shù)值會(huì)和預(yù)期的有所不同, 進(jìn)而導(dǎo)致實(shí)際中的ωPt和QPt與預(yù)期有所不同. 對(duì)于一個(gè)給定的‖S‖2, 將公式(19) 的‖S‖2的分布替換為固定的數(shù)值, 可以獲得實(shí)際中的βPt、ωPt和QPt.

在本節(jié)中, 我們將4.2 節(jié)中所獲得的‖S‖2的分布與D’Anvers 等人所用的卡方分布進(jìn)行對(duì)比, 進(jìn)而驗(yàn)證本文中的方法的提升. 在選擇Pt的時(shí)候, 將會(huì)選取使得預(yù)期ωPt的值取到最小值的Pt.

對(duì)于D’Anvers 等人所使用的卡方分布, 我們將4.2 節(jié)中所獲得的所有的‖S‖2帶入, 進(jìn)而獲得實(shí)際中的計(jì)算開(kāi)銷與解密查詢次數(shù), 將其期望值記為ω1和Q1. 然后, 對(duì)于4.2 節(jié)中所獲得的‖S‖2的分布, 將相應(yīng)的‖S‖2的數(shù)值帶入, 進(jìn)而獲得實(shí)際中的計(jì)算開(kāi)銷與解密查詢次數(shù), 將其期望值記為ω2和Q2.

經(jīng)過(guò)實(shí)驗(yàn), 得到ω2/ω1≈98.4%,Q2/Q1≈97.0%. 即, 在我們的假設(shè)與實(shí)驗(yàn)設(shè)定下, 實(shí)驗(yàn)表明本文中提出的方法可以使“directional failure boosting” 的計(jì)算開(kāi)銷與解密查詢次數(shù)分別降低至98.4% 和97%.

另外, 實(shí)驗(yàn)中還將本文中所獲得的‖S‖2的分布與相應(yīng)的正態(tài)分布、而不是卡方分布進(jìn)行對(duì)比. 所得到的結(jié)果與和卡方分布對(duì)比基本一致.

5 總結(jié)

本文中提出了一種新的在基于LWE 問(wèn)題的加密方案中獲得解密失敗密文的方法. 本文中的方法是“directional failure boosting” 的一個(gè)提升, 與“directional failure boosting” 相比, 本文中的方法在效率上有優(yōu)勢(shì), 可以使獲得一個(gè)解密失敗密文所需要的計(jì)算開(kāi)銷與解密查詢次數(shù)分別降低至98.4% 和97%.本文方法還存在兩個(gè)不足之處, 將在今后的研究工作中繼續(xù)研究改進(jìn).

(1) 在文獻(xiàn)[19] 中, D’Anvers 等人提到大多數(shù)基于LWE 問(wèn)題的加密方案都會(huì)對(duì)密文進(jìn)行壓縮, 進(jìn)而減少帶寬. 但是不論是“directional failure boosting” 還是本文中的方法, 都沒(méi)有考慮壓縮密文所帶來(lái)的影響.

(2) “directional failure boosting” 的使用前提是至少已經(jīng)獲得一個(gè)解密失敗密文. 本文假設(shè)在使用“directional failure boosting” 之前, 需要用“failure boosting” 來(lái)獲得至少一個(gè)解密失敗密文.但是在實(shí)際應(yīng)用中, 即使第一個(gè)解密失敗密文并不是通過(guò)“failure boosting” 獲得, “directional failure boosting” 也可以使用. 但是本文中的方法并不適應(yīng)這種情況.