基于LPN困難問題的后量子安全公鑰加密

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

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

LPN(Learning Parity with Noise)問題在后量子密碼領(lǐng)域是一個(gè)常用的假設(shè)[1]，主要用來構(gòu)造一些加密算法和協(xié)議，如公鑰加密算法和傳輸協(xié)議等。這些基于LPN構(gòu)造出來的加密算法和協(xié)議性能高并能抵抗量子算法的攻擊。

Alekhnovich[19]最早構(gòu)造出基于低噪LPN的選擇明文攻擊下的不可區(qū)分(Indistinguishability against Chosen Plaintext Attack，IND-CPA)安全的公鑰加密方案。隨后，D?ttling等人[11]利用相關(guān)認(rèn)證技術(shù)[20]首次構(gòu)造出基于低噪LPN的選擇密文攻擊下的不可區(qū)分(Indistinguishability against Chosen Ciphertext Attack,IND-CCA)安全的公鑰加密方案，但是方案的公鑰、私鑰和密文長度過大，效率有待提高。Kiltz等人[21]利用雙陷門技術(shù)構(gòu)造出IND-sTag-CCA安全的帶標(biāo)簽公鑰加密方案，并將該方案通過常見的技術(shù)手段轉(zhuǎn)變成IND-CCA安全的公鑰加密方案。雙陷門技術(shù)在方案的安全性證明中用來回答敵手的解密詢問。這兩個(gè)IND-CCA安全的公鑰加密方案的解碼錯(cuò)誤率(Decoding Failure Rate，DFR)均是2-Θ(k)，k為安全參數(shù)。Yu等人[14]構(gòu)造出基于常噪LPN問題的CCA安全公鑰加密方案的解碼錯(cuò)誤率為2-Θ(k2)。

到目前為止，并沒有基于變體xLPN(Variant of the Exact LPN，VxLPN)的CPA/CCA安全的公鑰加密方案。因此，該研究擬證明VxLPN問題和標(biāo)準(zhǔn)LPN問題一樣困難，并通過雙陷門技術(shù)，構(gòu)造基于VxLPN的IND-CPA/CCA安全的公鑰加密方案，以期降低解碼錯(cuò)誤率，提高效率。

1 預(yù)備知識

1.1 符號描述

為了表述方便，對文中符號進(jìn)行描述。黑體小寫字母表示列向量，如s，黑體小寫字母的轉(zhuǎn)置表示行向量，如sT。列向量s的漢明重量表示為|s|。黑體的大寫字母表示矩陣，如A，黑體大寫字母的轉(zhuǎn)置表示矩陣的轉(zhuǎn)置，如AT。μ表示噪聲率為μ的伯努利分布，也就是Pr[μ=1]=μ，Pr[μ=0]=1-μ，表示q個(gè)獨(dú)立的副本，也就是μ并列起來。表示列向量從分布{z∈{0,1}q∶|z|=qμ}上均勻地選取出，其中，qμ表示向量漢明重量為qμ。表示矩陣中的每一列都是從分中均勻選取的，x表示x中均勻隨機(jī)選取。Uq(Uq×q)表示在{0,1}q({0,1}q×q)上的均勻分布。negl(·)為其輸入的可忽略函數(shù)。

1.2 LPN及相關(guān)變體的定義

該部分主要介紹LPN問題、變體LPN問題(Variant of the LPN，VLPN)、緊湊LPN問題(Exact LPN，xLPN)以及背包LPN問題(Knapsack LPN，KLPN)相關(guān)定義。

(1)

(2)

困難性令T:=T(n)，如果運(yùn)行時(shí)間限制為T，對于任意攻擊者的優(yōu)勢在式(1)和式(2)中的上界為1/T，判定性/計(jì)算性(n,μ,q)-LPN問題是T-困難的。對于(n,μ)-LPN問題，內(nèi)在的限制就是q≤T。

判定性(n,μ)-VLPN問題可以規(guī)約到判定性(n,μ)-LPN問題上，詳細(xì)證明過程參考文獻(xiàn)[11]。

判定性(n,μ)-KLPN問題可以規(guī)約到判定性(n,μ)-LPN問題，詳細(xì)證明過程參考文獻(xiàn)[22]。

判定性(n,μ)-xLPN問題可以規(guī)約到判定性(n,μ)-LPN問題，詳細(xì)證明過程參考文獻(xiàn)[8]。

類似于定義1與定義2的關(guān)系，可以給出VxLPN問題的定義。

Abhishek等人[23]證明出判定性(n,μ)-xLPN問題和計(jì)算性(n,μ)-LPN問題是多項(xiàng)式等價(jià)的。證明VxLPN問題的困難性的具體規(guī)約過程如下。

下面將在引理A中證明判定性(n,μ)-VxLPN問題和計(jì)算性(n,μ)-VxLPN問題一樣困難。在引理B中證明計(jì)算性VxLPN和計(jì)算性VLPN一樣困難。

要證明判定性(n,μ)-VxLPN問題和計(jì)算性(n,μ)-VxLPN問題是等價(jià)的，常用的關(guān)于判定性(n,μ)-LPN問題的規(guī)約方法[2]不適用于判定性(n,μ)-VxLPN問題，因此，利用Goldreich-Levin理論[24]完成規(guī)約證明。

引理B 判定性(n,μ)-VxLPN問題和計(jì)算性(n,μ)-VxLPN問題是多項(xiàng)式等價(jià)的。

證明根據(jù)樣例保存規(guī)約證明該引理。利用標(biāo)準(zhǔn)的技術(shù)[4]，證明判定性矩陣版本(n,μ)-VxLPN問題也是困難的。證明方案的安全性就是利用判定性(n,μ)-VxLPN問題和判定性矩陣版本(n,μ)-VxLPN問題。下面，將具體證明該引理。

情況1矩陣A′是一個(gè)q×n隨機(jī)矩陣。

情況2y=Ax+e=A′x+srTx+e=A′x+s〈r,x〉+e。

這樣能得到一個(gè)關(guān)于Goldreich-Levin理論的矛盾，假設(shè)是不存在的。綜上所述，完成了該引理的證明。

1.3 哈希函數(shù)和隨機(jī)預(yù)言機(jī)模型

1.4 公鑰加密方案

公鑰加密[25-27](Public Key Encryption，PKE)方案是一個(gè)概率多項(xiàng)式時(shí)間算法元組(Gen,Enc,Dec)，其定義如下。

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

2)加密算法Enc是一個(gè)概率算法，該算法需要輸入公鑰kp和明文p，輸出密文C，記為C←Enc(kp,p)。

3)解密算法Dec是一個(gè)確定的算法，該算法需要輸入私鑰ks和密文C，輸出明文p或者失敗符號⊥，記作p←Dec(ks,C)，并滿足

Pr[Dec(ks,(Enc(kp,p)))≠p∶(kp,ks)←Gen(1k)]=
negl(k)

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

帶標(biāo)簽的公鑰加密[28-30](Tag Based public key Encryption，TBE)方案是一個(gè)概率多項(xiàng)式時(shí)間算法元組(KeyGen,Enc,Dec)，其定義如下。

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

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

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

1.5 公鑰加密方案安全性定義

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

挑戰(zhàn)挑戰(zhàn)者收到了攻擊者發(fā)送過來的等長消息對(p0,p1)，生成挑戰(zhàn)密文C*←Enc(kp,pb)，并將生成的挑戰(zhàn)密文發(fā)送給攻擊者。

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

1.6 帶標(biāo)簽的公鑰加密方案安全性定義

初始化挑戰(zhàn)者輸入安全參數(shù)k，并從攻擊者手中獲得一個(gè)標(biāo)簽t*。

密鑰生成挑戰(zhàn)者計(jì)算出密鑰(kp,ks)←Gen(1k)，將密鑰ks單獨(dú)保留，并將公鑰kp發(fā)送給攻擊者，隨機(jī)選取

初始化挑戰(zhàn)者輸入安全參數(shù)k，并從攻擊者手中獲得一個(gè)標(biāo)簽t*。

密鑰生成挑戰(zhàn)者計(jì)算出密鑰(kp,ks)←KeyGen(1k)，將密鑰ks私自保留，并將公鑰kp發(fā)送給攻擊者，隨機(jī)選取挑戰(zhàn)比特

那么TBE方案是IND-sTag-CCA2安全的。

1.7 主要引理

引理2(布爾不等式)[33-35]對于事件A1,A2,…,Aq，有

證明假設(shè)e的漢明重量不超過2 μm，分析sTe結(jié)果的情況。sTe=1必要條件是至少存在一個(gè)i且當(dāng)s[i]=1時(shí)，e[i]=1。將該必要條件應(yīng)用在下面證明第二步中，布爾不等式[33-36]應(yīng)用在第四步中，最終得到

令δ:=α/(4μ′)-1，注意到μ′≤c<α/4，(1+δ)μ′=α/4，使用切諾夫不等式可以得到

不難發(fā)現(xiàn)δ=α/(4μ′)-1≥α/(4c)-1>0和δμ′=α/4-μ′>c-μ′≥0均為大于零的常量，可以得到

將矩陣E表示為(e1,e2,…,em)，則ETs=[sT(e1,e2,…,em)]T。用類似的方法證明

其中，|ETs|=|(sTe1，sTe2，…，sTem)T|，具體證明細(xì)節(jié)省略。

根據(jù)判定性(n,μ)-LPN假設(shè)，(A,yTA)和(A,r)是計(jì)算不可區(qū)分的，證明過程參考文獻(xiàn)[37]。

2 基于LPN的CPA安全的公鑰加密

下面介紹3個(gè)常見的基于LPN的CPA安全的公鑰加密方案，包括Alekhnovich的方案[19](簡稱AM方案)、D?ttling等人[11]的方案(簡稱DMN方案)和Yu等人的方案[14](簡稱YZ方案)，以及該研究構(gòu)造的基于VxLPN的IND-CPA安全的公鑰加密方案。

2.1 AM方案

C=Ty+e

其中，C∈{0,1}m。

3)Dec(ks,C):解密算法。輸入私鑰ks=(S,E)和密文C，并通過解碼算法從密文C中恢復(fù)出v。利用求解線性系統(tǒng)v=MTTy計(jì)算出y。如果|e|滿足|e|≤αm，那么解密算法輸出p，否則，解密算法輸出⊥。

AM方案是首個(gè)基于LPN的CPA安全公鑰加密方案，其正確性和安全性證明參考文獻(xiàn)[19]。

2.2 DMN方案

3)Dec(ks,C):解密算法。輸入私鑰ks=T和密文C=(c1,c2,c3)，計(jì)算c0:=c2-Tc1。

解密算法利用生成矩陣G的糾錯(cuò)性質(zhì)恢復(fù)出s。如果解碼失敗，輸出⊥，否則解密算法利用生成矩陣G1的糾錯(cuò)性質(zhì)恢復(fù)出p。如果兩次解碼都正確，則輸出p，否則輸出⊥。

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

2.3 YZ方案

Yu等人[14]首次構(gòu)造出基于常噪LPN的CPA安全的公鑰加密方案，在此基礎(chǔ)上利用相關(guān)技術(shù)又構(gòu)造出基于常噪LPN的CCA安全帶標(biāo)簽的公鑰加密方案。令k是方案的安全參數(shù)，選取正整數(shù)m和n分別滿足n=Θ(k2)和m=Θ(k2)，噪聲率0<μ<1/2，生成矩陣G∈{0,1}m×n能夠糾αm個(gè)錯(cuò)誤。YZ方案的具體算法如下。

3)Dec(ks,C):解密算法。輸入私鑰ks=s和密文C=(C1,c2)，并計(jì)算

解密算法利用生成矩陣G的糾錯(cuò)性質(zhì)恢復(fù)出明文p。如果有|STe-ETs|≤αm，則輸出p，否則輸出⊥。

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

2.4 基于VxLPN的IND-CPA安全公鑰加密方案

3)Dec(ks,C): 解密算法。輸入私鑰ks=s和密文C=(C1,c2)，并計(jì)算

定理1只要方案選擇適當(dāng)?shù)膮?shù)，PKE方案就能夠滿足正確性。

下面將分析密文C。由引理3可以得到概率為1-2-Θ(m)的等式

定理2如果判定性(n,μ)-VxLPN假設(shè)是困難的，那么PKE方案是IND-CPA 安全的。

游戲0該游戲是關(guān)于PKE方案的IND-CPA安全實(shí)驗(yàn)。挑戰(zhàn)者模擬IND-CPA安全游戲如下。

和游戲2中的

在計(jì)算上是不可區(qū)分的。因此，可以得到|Pr[R2]-Pr[R1]|≤negl(n)。

因此，PKE方案滿足IND-CPA安全。

3 基于LPN的CCA安全的公鑰加密

下面介紹4個(gè)常見的基于LPN的CCA安全的公鑰加密方案，包括DMN方案[11]、Kiltz等人[21]的方案(簡稱KMP方案)、YZ方案[14]和Cheng等人[12]的方案(簡稱CLQY方案)，以及該研究構(gòu)造的基于VxLPN的IND-CCA安全的公鑰加密方案。

3.1 DMN方案

解密算法利用生成矩陣G的糾錯(cuò)性質(zhì)恢復(fù)出s。如果解碼失敗，輸出⊥，否則計(jì)算e1=c1-As、e2=c2-Bτ′s和e3=c3-Ds-G1p。解密算法利用生成矩陣G1的糾錯(cuò)性質(zhì)恢復(fù)出p，如果兩次解碼都正確，則輸出p，否則輸出⊥。

在128比特安全下，DMN方案的公鑰和私鑰長度往往會比其他基于LPN的 CCA安全的公鑰加密方案的公鑰和私鑰長度大得多。該方案的正確性和安全性證明參考文獻(xiàn)[11]。

3.2 KMP方案

3)Dec(ks,C,t):解密算法。輸入私鑰ks=(0,T0)、標(biāo)簽t和密文C=(c,c0,c1,c2)，解密算法計(jì)算

則使用生成矩陣G1的糾錯(cuò)性質(zhì)恢復(fù)出明文p(從c2-Ds=G1p+e1中恢復(fù))，否則令p=⊥。最后，輸出明文p。

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

3.3 YZ方案

Yu等人[14]構(gòu)造出首個(gè)基于常噪LPN的CCA安全帶標(biāo)簽的公鑰加密方案，使用雙陷門技術(shù)又成功構(gòu)造出CCA安全的加密方案，并利用相關(guān)技術(shù)將該CCA安全的帶標(biāo)簽的公鑰加密方案轉(zhuǎn)換成CCA安全的公鑰加密方案。令k為方案的安全參數(shù)，選取一些常數(shù)n=Θ(k2),m≥2n,l≥m,q=Θ(n)，除此之外，令α為常數(shù)且滿足α>0，噪聲率0<μ≤0.1，μ1=Θ(logn/n)，λ=Θ(log2n)，2λ≤H∞(生成矩陣G∈{0,1}m×n和G1∈{0,1}l×n分別能糾正βm和2μl個(gè)比特錯(cuò)誤[14]。定義標(biāo)簽空間=F2n，Ht∈{0,1}n×n，t,t1,t2∈F2n，滿足H0=0,Ht1+Ht2=Ht1+t2，給定任何t≠0可計(jì)算出Ht。YZ方案的具體算法如下。

c:=As+e
c0:=(GHt+B0)s+(S′0)Te-(E′0)Ts
c1:=(GHt+B1)s+(S′1)Te-(E′1)Ts
c2:=Ds+e1+G1p

其中,c∈{0,1}n,c0∈{0,1}m,c1∈{0,1}m,c2∈{0,1}t。

則使用生成矩陣G1的糾錯(cuò)性質(zhì)恢復(fù)出明文p(從c2-Ds=G1p+e1中恢復(fù))，否則令p=⊥。最后，輸出p。

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

3.4 CLQY方案

c0-Tc=GHts+(T′-T)e

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

3.5 基于VxLPN的IND-CCA安全公鑰加密方案

該研究將構(gòu)造基于VxLPN的IND-CCA安全的公鑰加密方案，為此首先構(gòu)造基于VxLPN的IND-sTag-CCA2安全的公鑰加密方案，在此基礎(chǔ)上再利用標(biāo)準(zhǔn)的變換[14,21,40]將帶標(biāo)簽的公鑰加密方案轉(zhuǎn)變成標(biāo)準(zhǔn)的公鑰加密方案。

(kp,ks) =[(A,B0,B1,D),(S0,S1)]

c:=As+e
c0:=(GHt+B0)s+(S′0)Te-(E′0)Ts
c1:=(GHt+B1)s+(S′1)Te-(E′1)Ts
c2:=Ds+e1+G1p

其中,c∈{0,1}n,c0∈{0,1}m,c1∈{0,1}m,c2∈{0,1}l。

(3)

則使用生成矩陣G1的糾錯(cuò)性質(zhì)恢復(fù)出明文p(從c2-Ds=G1p+e1中恢復(fù))，否則令p=⊥。最后，輸出p。

定理3只要方案選擇適當(dāng)?shù)膮?shù)，TBE方案是正確的。

證明要想得到正確的TBE方案，需要滿足以下條件

|(S′0-S0)Te+(E0-E′0)Ts|≤αm

|e1|=μl

Pr[|e|=μn]=1
Pr[|e1|=μl]=1

則C是正確生成的密文。由引理3以壓倒性的概率得到

中解碼出正確的Hts，且錯(cuò)誤項(xiàng)滿足

|(S′i-Si)Te+(Ei-E′i)Ts|≤αm，

定理4如果判定性(n,μ)-VxLPN假設(shè)是困難的，那么TBE方案是IND-sTag-CCA2安全的。

使用生成矩陣G的糾錯(cuò)性質(zhì)恢復(fù)出Hts。如果有

游戲1該游戲和游戲0基本一致，除了挑戰(zhàn)者改變密鑰生成階段。

引理6|Pr[R1]-Pr[R0]|≤negl(n)

證明游戲1和游戲0唯一的不同就是挑戰(zhàn)者用游戲1公鑰中代替游戲0公鑰中根據(jù)矩陣版本判定性(n,μ)-VxLPN假設(shè)，游戲1中和游戲0中kp=(A,B0,B1,D)是計(jì)算不可區(qū)分的。因此，|Pr[R1]-Pr[R0]|≤negl(n)。

游戲2該游戲和游戲1基本一致，除了挑戰(zhàn)者改變密鑰生成階段和挑戰(zhàn)階段。

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

證明游戲2和游戲1不同的是，挑戰(zhàn)者在游戲2公鑰中用代替了游戲1公鑰中此外，S1和E1在密鑰生成階段中與S′1和E′1在挑戰(zhàn)階段具有相同的分布。不難發(fā)現(xiàn)，并不包含在公鑰中，所以攻擊者不能得到任何關(guān)于S1和E1有用的信息。游戲2中的挑戰(zhàn)密文和游戲1中的挑戰(zhàn)密文具有相同的分布。綜上所述，在攻擊者看來，游戲2和游戲1相同，所以有Pr[R2]=Pr[R1]。

游戲3該游戲和游戲2基本一致，除了挑戰(zhàn)者改變密鑰生成階段。

引理8|Pr[R3]-Pr[R2]|≤negl(n)

證明游戲3和游戲2唯一的區(qū)別就是挑戰(zhàn)者在游戲3公鑰中用代替游戲2公鑰中其中根據(jù)矩陣版本判定性(n,μ)-VxLPN假設(shè)，在攻擊者看來，游戲2中公鑰和游戲3中公鑰是計(jì)算不可區(qū)分的。因此，不難得到|Pr[R3]-Pr[R2]|≤negl(n)。值得注意的是，挑戰(zhàn)密文中

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

引理9|Pr[R4]-Pr[R3]|≤negl(n)

證明不難知道，S1和S0有等價(jià)的解密能力且恢復(fù)出相同明文的概率差不超過關(guān)于n的可忽略函數(shù)。

游戲5該游戲和游戲4基本一致，除了挑戰(zhàn)者改變密鑰生成階段和挑戰(zhàn)階段。

引理10|Pr[R5]-Pr[R4]|≤negl(n)

證明由引理6-9相似的方法可證明該引理。

游戲6該游戲和游戲5基本一致，除了挑戰(zhàn)者改變挑戰(zhàn)階段。

引理11|Pr[R6]-Pr[R5]|≤negl(n)

證明游戲6和游戲5唯一的區(qū)別就是挑戰(zhàn)者在游戲6中用c*:=v和代替游戲5中的c*:=As+e和其中：根據(jù)判定性(n,μ)-VxLPN假設(shè)是困難的，游戲6挑戰(zhàn)密文與游戲5中挑戰(zhàn)密文是計(jì)算不可區(qū)分的。因此，可得到|Pr[R6]-Pr[R5]|≤negl(n)。

3.6 IND-CCA安全的公鑰加密方案的性能分析

由于IND-CPA安全的公鑰加密方案構(gòu)造相對比較簡單，因此主要分析IND-CCA安全的加密方案的性能。DMN方案[11]、KMP方案[21]、YZ方案[14]、CLQY方案[12]和構(gòu)造方案的困難問題假設(shè)如表1所示。DMN方案[11]、KMP方案[21]和構(gòu)造方案的解密錯(cuò)誤率如表2所示。在DMN方案[11]、KMP方案[21]和構(gòu)造方案中，令n=k2,m=2n，在DMN方案[11]中，令l1=l2=l3=n。

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

表2 不同方案的解碼錯(cuò)誤率

表3 不同方案的參數(shù)對比

4 結(jié)語

研究了基于變體xLPN的CPA/CCA安全的加密方案。在幾個(gè)比較常見的基于LPN問題的CPA/CCA安全的公鑰加密方案的基礎(chǔ)上，利用雙陷門技術(shù)構(gòu)造出了基于VxLPN問題的CPA/CCA安全的加密方案。利于一次簽名可以直接構(gòu)造出CCA安全的公鑰加密方案，而雙陷門技術(shù)可以構(gòu)造出CCA安全帶標(biāo)簽的公鑰加密方案，通過轉(zhuǎn)換可以得到CCA安全的公鑰加密方案。性能分析表明，在128比特安全水平下，D?ttling等人[11]和Kiltz等人[21]方案的公鑰長度、私鑰長度、密文長度分別為(14.53 GB、14.48 GB、14.06 KB)和(161.78 MB、92.45 MB、13.60 KB)，構(gòu)造方案的公鑰長度、私鑰長度、密文長度分別為(117.79 MB、67.31 MB、10.15 KB)，比其他IND-CCA安全方案更高效。除此之外，在相同安全參數(shù)情況下，構(gòu)造方案的解碼錯(cuò)誤率是2-Θ(k2)，比其他IND-CCA安全方案的解碼錯(cuò)誤率更低。