基于LPN困難問(wèn)題的后量子安全密鑰封裝

徐勝峰，李祥學(xué),2

(1.華東師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 200062；2.華東師范大學(xué) 軟件工程學(xué)院，上海 200062)

LPN(Learning Parity with Noise)問(wèn)題是后量子密碼領(lǐng)域一個(gè)極佳候選假設(shè)，基于LPN問(wèn)題的密鑰封裝機(jī)制不僅適用于某些弱功率設(shè)備，還能抵抗量子算法攻擊。在Lepton方案中，Yu等人[1]首先介紹Exact LPN和Ring LPN兩個(gè)LPN的變體，并證明出這兩個(gè)變體和標(biāo)準(zhǔn)的LPN問(wèn)題一樣困難，然后使用FO(Fujisaki-Okamoto)變換[2-5]構(gòu)造出一個(gè)選擇密文攻擊下的不可區(qū)分(Indistinguishability against Chosen Ciphertext Attack，IND-CCA)安全的密鑰封裝機(jī)制。Cheng等人[6]構(gòu)造出一個(gè)基于低噪LPN的多接收者的密鑰封裝機(jī)制?？梢院?jiǎn)單地認(rèn)為，密鑰封裝機(jī)制是公鑰加密方案加密一個(gè)隨機(jī)數(shù)。

現(xiàn)有基于LPN問(wèn)題構(gòu)造出的CCA安全的密鑰封裝機(jī)制是很難直接構(gòu)造出來(lái)的，大部分方案都是利用FO變換得到。盡管使用FO變換能夠簡(jiǎn)單地構(gòu)造出CCA安全的方案，但是FO變換往往會(huì)導(dǎo)致方案的安全規(guī)約不緊湊。因此，構(gòu)造出一個(gè)緊湊的密鑰封裝機(jī)制尤為重要。該研究擬給出緊湊的基于低噪LPN的CCA安全的密鑰封裝機(jī)制直接構(gòu)造，以期抵抗量子算法攻擊。在構(gòu)造過(guò)程中，以雙陷門(mén)技術(shù)回答敵手的解密詢問(wèn)，以抗第二原像哈希函數(shù)(Target Collision Resistant Hash Function，TCR)驗(yàn)證密文的有效性。

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

1.1 密鑰封裝

密鑰封裝機(jī)制[13-14](Key-EncapsulationMechanism,KEM)是概率多項(xiàng)式時(shí)間的算法元祖(Gen,Encaps,Decaps)，其定義如下。

1)密鑰生成算法Gen是一個(gè)概率算法，該算法需要輸入安全參數(shù)1k，輸出公鑰kp和私鑰ks。

2)密鑰封裝算法Encaps是一個(gè)概率算法，該算法需要輸入公鑰kp,輸出密文C和密鑰k，記作(C,k)←Encaps(kp)。

3)解封裝算法Decaps是一個(gè)確定的算法，該算法需要將私鑰ks和密文C作為輸入，輸出密鑰k或者失敗符號(hào)⊥，記作k←Decaps(ks,C)，并滿足

Pr[Decaps(ks,(Encaps(kp)))≠k∶(kp,ks)←KeyGen(1k)]=negl(k)

等式不成立的概率是可忽略的，這是由(kp,ks)和密鑰封裝算法使用的任何隨機(jī)數(shù)所決定的。

1.2 密鑰封裝安全性定義

初始化挑戰(zhàn)者輸入安全參數(shù)1k并生成挑戰(zhàn)密鑰對(duì)(kp,ks)←Gen(1k)，攻擊者從挑戰(zhàn)者手中得到公鑰kp，挑戰(zhàn)者隨機(jī)地選擇b∈{0,1}。

挑戰(zhàn)挑戰(zhàn)者首先均勻隨機(jī)選取，然后生成挑戰(zhàn)密文和秘鑰將生成的挑戰(zhàn)密文和秘鑰發(fā)送給攻擊者。

初始化挑戰(zhàn)者輸入安全參數(shù)1k并生成挑戰(zhàn)密鑰對(duì)(kp,ks)←Gen(1k)。攻擊者從挑戰(zhàn)者手中得到公鑰kp，挑戰(zhàn)者隨機(jī)選擇b*∈{0,1}。

挑戰(zhàn)挑戰(zhàn)者先均勻隨機(jī)選取，然后生成挑戰(zhàn)密文和秘鑰最后將生成的挑戰(zhàn)密文和秘鑰發(fā)送給攻擊者。攻擊者可以詢問(wèn)解封裝預(yù)言機(jī)并進(jìn)行相關(guān)運(yùn)算。

2 基于LPN的CCA安全的密鑰封裝

下面介紹Lepton方案[1]和CLQY方案[6]兩個(gè)常見(jiàn)的基于LPN的CCA安全的密鑰封裝機(jī)制，以及該研究構(gòu)造的基于低噪LPN的IND-CCA安全的密鑰封裝機(jī)制。

2.1 Lepton方案

a∶=Samp(σ)∈{0,1}n

(k′,r,d)∶=G(m‖kp,3) ∈({0,1}k)3

c1∶=ax+e1∈{0,1}n

c2∶=Trunc(bx+e2,l)+ECC(m) ∈{0,1}l

k∶=G(k′‖(c1,c2,d)) ∈{0,1}k

3)Decaps(ks,C)解封裝算法。輸入私鑰ks=s和密文(c1,c2,d)，計(jì)算c2-Trunc(c1s,l)，利用解碼算法ECC-1恢復(fù)m∶=ECC-1[c2-Trunc(c1s,l)]。令(k′,C′)=Encaps(kp,m)，如果C′=C，則令k∶=k′，否則k∶=⊥。最后，輸出密鑰k。

Lepton方案的正確性和安全性證明參考文獻(xiàn)[1]。

2.2 CLQY方案

c0∶=As+e∈{0,1}l

ci∶=Bis+S′ie+ECC(m) ∈{0,1}l

k∶=H2(m) ∈{0,1}l

3)mKEM.DeCap(i,,ki,s,C):解封裝算法。將i、、ki,s和C作為輸入，如果≠m，該算法直接中止，否則計(jì)算ci-Sic0=ECC(m)+(S′i-Si)e。利用解碼算法ECC-1恢復(fù)m′，計(jì)算(s′,e′)=H1(m′)。如果滿足

該算法令k∶=H2(m′)，否則令k∶=⊥。最后，輸出密鑰k。

CLQY方案的正確性和安全性證明參考文獻(xiàn)[6]。

2.3 基于低噪LPN的IND-CCA安全的密鑰封裝

(kp,ks)=[(A,B,D,F),(S0,S1)]

c0∶=As+e∈{0,1}m

c1∶=Bs+(S′0)Te-(E′0)Ts+ECC(s) ∈{0,1}m

c2∶=Ds+(S′1)Te-(E′1)Ts+ECC(s) ∈{0,1}m

k∶=Fs+t∈{0,1}(l+1)

(1)

定理1只要選擇適當(dāng)?shù)膮?shù)，構(gòu)造方案的KEM就是正確的，私鑰中的S0和S1在解封裝階段是等價(jià)的。

(2)

(3)

如果C是正確生成的密文，那么通過(guò)式(2)、式(3)和文獻(xiàn)[25]中的引理3可得到

下面的引理將證明私鑰S0和S1以壓倒性的概率具有相同解碼能力。

引理1定義解碼算法Decaps(ks,C)S1，且該算法是利用私鑰S1解碼恢復(fù)出s。令

Decaps(ks,C)S0:=Decaps(ks,C)，

Decaps(ks,C)S1和Decaps(ks,C)S0以壓倒性的概率返回相同k。即

證明如果k∶=Decaps(ks,C)S0，則可恢復(fù)出s。由式(1)可得到

解碼算法Decaps(ks,C)S1使用ECC-1能恢復(fù)出相同的s，其中錯(cuò)誤項(xiàng)滿足

因?yàn)?/p>

通過(guò)使用文獻(xiàn)[25] 中引理3，得到

綜上所述，私鑰中的S0和S1在解封裝階段是等價(jià)的。換句話說(shuō)，利用私鑰中的S0和S1能夠以壓倒性的概率解碼出相同的密鑰k。

游戲0該游戲是KEM的IND-CCA安全實(shí)驗(yàn)。挑戰(zhàn)者誠(chéng)實(shí)地調(diào)用敵手，并模擬關(guān)于敵手的游戲如下。

那么將會(huì)有如下兩個(gè)不同的情況。

滿足

情況2t≠t*。在這種情況下，挑戰(zhàn)者計(jì)算k∶=Fs+t并發(fā)送k給敵手。否則，令k:=⊥。挑戰(zhàn)者發(fā)送k給敵手。

證明挑戰(zhàn)者誠(chéng)實(shí)地調(diào)用敵手并輸出1，當(dāng)且僅當(dāng)b′=b*。

游戲1該游戲和游戲0基本一致，除了挑戰(zhàn)者改變密鑰生成階段。該階段挑戰(zhàn)者選取和計(jì)算和并發(fā)送公鑰kp=(A,B,D′,F)給敵手。最后，挑戰(zhàn)者單獨(dú)保留私鑰ks=(S0,S1)。

證明游戲1和游戲0不同的是挑戰(zhàn)者用游戲1中的公鑰代替游戲0中的公鑰。如果矩陣版本的判定性(n,μ)-VLPN假設(shè)是困難的，那么游戲0中的公鑰和游戲1中的公鑰是計(jì)算不可區(qū)分的。因此，得到Pr[R1]-Pr[R0]≤negl(n)。

游戲2該游戲和游戲1基本一致，除了挑戰(zhàn)者改變挑戰(zhàn)階段。該階段挑戰(zhàn)者均勻地選取矩陣和，隨機(jī)選取挑戰(zhàn)比特b*∈{0,1}并發(fā)送給敵手，其中

引理4Pr[R2]=Pr[R1]

游戲3該游戲和游戲2基本一致，除了挑戰(zhàn)者改變密鑰生成階段。該階段挑戰(zhàn)者選取矩陣和計(jì)算和并發(fā)送公鑰kp=(A,B,D,F)給敵手。最后，挑戰(zhàn)者保留私鑰ks=(S0,S1)。

證明游戲3和游戲2不同的是挑戰(zhàn)者用游戲3中公鑰代替游戲2中公鑰根據(jù)矩陣版本的判定性(n,μ)-VLPN假設(shè)，游戲2中公鑰kp=(A,B,D′)和游戲3中公鑰kp=(A,B,D)是計(jì)算不可區(qū)分的。因此，得到Pr[R3]-Pr[R2]≤negl(n)。注意密文中的等于

游戲4該游戲和游戲3基本一致，除了挑戰(zhàn)者用S1代替S0響應(yīng)所有的解密問(wèn)詢。

證明引理5證明了S1和S0解密能力是等價(jià)的。

游戲5該游戲和游戲4基本一致，除了挑戰(zhàn)者改變挑戰(zhàn)階段。該階段挑戰(zhàn)者均勻地選取矩陣和，隨機(jī)選取挑戰(zhàn)比特b*∈{0,1}并發(fā)送給敵手，其中

游戲6該游戲和游戲5基本一致，除了挑戰(zhàn)者改變挑戰(zhàn)階段。該階段挑戰(zhàn)者均勻地選取矩陣和，隨機(jī)選取挑戰(zhàn)比特b*∈{0,1}并發(fā)送給敵手，其中

證明游戲6和游戲5不同的是挑戰(zhàn)者用游戲6中c*=v代替游戲5中c*=As+e，其中根據(jù)判定性(n,μ)-VLPN假設(shè)，這兩個(gè)游戲中的挑戰(zhàn)密文是計(jì)算不可區(qū)分的。因此，得到Pr[R6]-Pr[R5]≤negl(n)。

游戲7該游戲和游戲6基本一致，除了挑戰(zhàn)者改變挑戰(zhàn)階段。該階段挑戰(zhàn)者選取向量和，隨機(jī)挑選挑戰(zhàn)比特b*∈{0,1}并發(fā)送給敵手，其中

證明游戲7和游戲6不同的是挑戰(zhàn)者用游戲7中的和代替游戲6中的和其中和根據(jù)判定性(n,μ)-KLPN假設(shè)，這兩個(gè)游戲中的挑戰(zhàn)密文是計(jì)算不可區(qū)分的，從而Pr[R7]-Pr[R6]≤negl(n)。

游戲8該游戲和游戲7基本一致，除了挑戰(zhàn)者改變挑戰(zhàn)階段。該階段挑戰(zhàn)者均勻地選取矩陣和，隨機(jī)選取挑戰(zhàn)比特b*∈{0,1}并發(fā)送給敵手，其中

證明游戲8和游戲7不同的是挑戰(zhàn)者用游戲8中的代替游戲7中的其中通過(guò)使用文獻(xiàn)[30]中的引理2.10，不難發(fā)現(xiàn)這兩個(gè)游戲中的挑戰(zhàn)密文在敵手看來(lái)是不可區(qū)分的，從而Pr[R8]-Pr[R7]≤negl(n)。

綜上所述，使用引理3至引理11可以證明出該方案的KEM是IND-CCA安全的。換句話來(lái)說(shuō)，即

3 不同方案的性能和效益分析

CRYSTALS-Kyber[1]、Classic McEliece[1]、SABER[1]、NTRU-HRSS-KEM[1]、MP[7]和NewHope[31]是基于LWE構(gòu)造出來(lái)的方案，Lepton[1]、CLQY[6]、DMN[32]、KMP[16]和YZ[33]是基于LPN構(gòu)造出來(lái)的方案，PW[34]是基于DDH或者錯(cuò)誤學(xué)習(xí)問(wèn)題(Learning With Errors,LWE)構(gòu)造出來(lái)的方案，而該研究的構(gòu)造方案是基于低噪LPN的密鑰封裝機(jī)制。上述方案的困難問(wèn)題假設(shè)對(duì)比如表1所示。

表1 不同方案的困難問(wèn)題假設(shè)

假設(shè)判定性(n,μ)-VLPN問(wèn)題能被敵手以時(shí)間復(fù)雜度為24μn解決，那么該研究的構(gòu)造方案的KEM被敵手攻克的時(shí)間復(fù)雜度為24μn+1(2n+m+1)。令n=11 449,c=1/16,μ=0.002 34，可計(jì)算出構(gòu)造方案的KEM能達(dá)到128比特安全。在128比特安全下，不同方案的參數(shù)對(duì)比如表2所示，可以看出，構(gòu)造方案的KEM公鑰長(zhǎng)度、私鑰長(zhǎng)度和密文長(zhǎng)度分別為101.56 MB、125.00 MB和9.08 KB，均低于DMN[32]和KMP[16]，構(gòu)造更為有效。

表2 128比特安全下不同方案的參數(shù)對(duì)比

注意到基于LWE的方案，如CRYSTALS-Kyber[1]和NTRU-HRSS-KEM[1]是基于有限域GF(q)上的運(yùn)算，而構(gòu)造方案則是基于有限域GF(2)上的運(yùn)算，因此，構(gòu)造方案在硬件上運(yùn)行速度更快。

4 結(jié)語(yǔ)

研究了首個(gè)在標(biāo)準(zhǔn)模型下基于低噪的LPN的IND-CCA安全的密鑰封裝機(jī)制。利用雙陷門(mén)技術(shù)正確回答敵手的解密問(wèn)詢，通過(guò)抗第二原像哈希函數(shù)確保密文通過(guò)有效認(rèn)證。與一般的密鑰封裝機(jī)制不同的是，該研究構(gòu)造的CCA安全的密鑰封裝機(jī)制是直接構(gòu)造的，不依賴于傳統(tǒng)的FO變換，且封裝密鑰不是由哈希函數(shù)生成而是由特殊的LPN問(wèn)題生成。利用FO變換生成的CCA安全的密鑰封裝機(jī)制的安全性規(guī)約是不緊湊的，這是因?yàn)槔肍O變換生成的密鑰封裝機(jī)制都是在隨機(jī)預(yù)言機(jī)模型或者量子隨機(jī)預(yù)言機(jī)模型下達(dá)到CCA安全。相反，該研究的CCA安全的密鑰封裝機(jī)制在標(biāo)準(zhǔn)模型下的安全性規(guī)約是緊湊的。除此之外，構(gòu)造的密鑰封裝機(jī)制是基于低噪的LPN問(wèn)題而不是LWE問(wèn)題，因此是在有限域GF(2)上進(jìn)行運(yùn)算，硬件運(yùn)行速度比其他基于LWE問(wèn)題構(gòu)造的密鑰封裝機(jī)制更快。