基于LPN困难问题的后量子安全密钥封装

徐胜峰，李祥学,2

(1.华东师范大学 计算机科学与技术学院，上海 200062；2.华东师范大学 软件工程学院，上海 200062)

LPN(Learning Parity with Noise)问题是后量子密码领域一个极佳候选假设，基于LPN问题的密钥封装机制不仅适用于某些弱功率设备，还能抵抗量子算法攻击。在Lepton方案中，Yu等人[1]首先介绍Exact LPN和Ring LPN两个LPN的变体，并证明出这两个变体和标准的LPN问题一样困难，然后使用FO(Fujisaki-Okamoto)变换[2-5]构造出一个选择密文攻击下的不可区分(Indistinguishability against Chosen Ciphertext Attack，IND-CCA)安全的密钥封装机制。Cheng等人[6]构造出一个基于低噪LPN的多接收者的密钥封装机制。可以简单地认为，密钥封装机制是公钥加密方案加密一个随机数。

现有基于LPN问题构造出的CCA安全的密钥封装机制是很难直接构造出来的，大部分方案都是利用FO变换得到。尽管使用FO变换能够简单地构造出CCA安全的方案，但是FO变换往往会导致方案的安全规约不紧凑。因此，构造出一个紧凑的密钥封装机制尤为重要。该研究拟给出紧凑的基于低噪LPN的CCA安全的密钥封装机制直接构造，以期抵抗量子算法攻击。在构造过程中，以双陷门技术回答敌手的解密询问，以抗第二原像哈希函数(Target Collision Resistant Hash Function，TCR)验证密文的有效性。

1 预备知识

1.1 密钥封装

密钥封装机制[13-14](Key-EncapsulationMechanism,KEM)是概率多项式时间的算法元祖(Gen,Encaps,Decaps)，其定义如下。

1)密钥生成算法Gen是一个概率算法，该算法需要输入安全参数1k，输出公钥kp和私钥ks。

2)密钥封装算法Encaps是一个概率算法，该算法需要输入公钥kp,输出密文C和密钥k，记作(C,k)←Encaps(kp)。

3)解封装算法Decaps是一个确定的算法，该算法需要将私钥ks和密文C作为输入，输出密钥k或者失败符号⊥，记作k←Decaps(ks,C)，并满足

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

等式不成立的概率是可忽略的，这是由(kp,ks)和密钥封装算法使用的任何随机数所决定的。

1.2 密钥封装安全性定义

初始化挑战者输入安全参数1k并生成挑战密钥对(kp,ks)←Gen(1k)，攻击者从挑战者手中得到公钥kp，挑战者随机地选择b∈{0,1}。

挑战挑战者首先均匀随机选取，然后生成挑战密文和秘钥将生成的挑战密文和秘钥发送给攻击者。

初始化挑战者输入安全参数1k并生成挑战密钥对(kp,ks)←Gen(1k)。攻击者从挑战者手中得到公钥kp，挑战者随机选择b*∈{0,1}。

挑战挑战者先均匀随机选取，然后生成挑战密文和秘钥最后将生成的挑战密文和秘钥发送给攻击者。攻击者可以询问解封装预言机并进行相关运算。

2 基于LPN的CCA安全的密钥封装

下面介绍Lepton方案[1]和CLQY方案[6]两个常见的基于LPN的CCA安全的密钥封装机制，以及该研究构造的基于低噪LPN的IND-CCA安全的密钥封装机制。

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)，计算c2-Trunc(c1s,l)，利用解码算法ECC-1恢复m∶=ECC-1[c2-Trunc(c1s,l)]。令(k′,C′)=Encaps(kp,m)，如果C′=C，则令k∶=k′，否则k∶=⊥。最后，输出密钥k。

Lepton方案的正确性和安全性证明参考文献[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，该算法直接中止，否则计算ci-Sic0=ECC(m)+(S′i-Si)e。利用解码算法ECC-1恢复m′，计算(s′,e′)=H1(m′)。如果满足

该算法令k∶=H2(m′)，否则令k∶=⊥。最后，输出密钥k。

CLQY方案的正确性和安全性证明参考文献[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只要选择适当的参数，构造方案的KEM就是正确的，私钥中的S0和S1在解封装阶段是等价的。

(2)

(3)

如果C是正确生成的密文，那么通过式(2)、式(3)和文献[25]中的引理3可得到

下面的引理将证明私钥S0和S1以压倒性的概率具有相同解码能力。

引理1定义解码算法Decaps(ks,C)S1，且该算法是利用私钥S1解码恢复出s。令

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

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

证明如果k∶=Decaps(ks,C)S0，则可恢复出s。由式(1)可得到

解码算法Decaps(ks,C)S1使用ECC-1能恢复出相同的s，其中错误项满足

因为

通过使用文献[25] 中引理3，得到

综上所述，私钥中的S0和S1在解封装阶段是等价的。换句话说，利用私钥中的S0和S1能够以压倒性的概率解码出相同的密钥k。

游戏0该游戏是KEM的IND-CCA安全实验。挑战者诚实地调用敌手，并模拟关于敌手的游戏如下。

那么将会有如下两个不同的情况。

满足

情况2t≠t*。在这种情况下，挑战者计算k∶=Fs+t并发送k给敌手。否则，令k:=⊥。挑战者发送k给敌手。

证明挑战者诚实地调用敌手并输出1，当且仅当b′=b*。

游戏1该游戏和游戏0基本一致，除了挑战者改变密钥生成阶段。该阶段挑战者选取和计算和并发送公钥kp=(A,B,D′,F)给敌手。最后，挑战者单独保留私钥ks=(S0,S1)。

证明游戏1和游戏0不同的是挑战者用游戏1中的公钥代替游戏0中的公钥。如果矩阵版本的判定性(n,μ)-VLPN假设是困难的，那么游戏0中的公钥和游戏1中的公钥是计算不可区分的。因此，得到Pr[R1]-Pr[R0]≤negl(n)。

游戏2该游戏和游戏1基本一致，除了挑战者改变挑战阶段。该阶段挑战者均匀地选取矩阵和，随机选取挑战比特b*∈{0,1}并发送给敌手，其中

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

游戏3该游戏和游戏2基本一致，除了挑战者改变密钥生成阶段。该阶段挑战者选取矩阵和计算和并发送公钥kp=(A,B,D,F)给敌手。最后，挑战者保留私钥ks=(S0,S1)。

证明游戏3和游戏2不同的是挑战者用游戏3中公钥代替游戏2中公钥根据矩阵版本的判定性(n,μ)-VLPN假设，游戏2中公钥kp=(A,B,D′)和游戏3中公钥kp=(A,B,D)是计算不可区分的。因此，得到Pr[R3]-Pr[R2]≤negl(n)。注意密文中的等于

游戏4该游戏和游戏3基本一致，除了挑战者用S1代替S0响应所有的解密问询。

证明引理5证明了S1和S0解密能力是等价的。

游戏5该游戏和游戏4基本一致，除了挑战者改变挑战阶段。该阶段挑战者均匀地选取矩阵和，随机选取挑战比特b*∈{0,1}并发送给敌手，其中

游戏6该游戏和游戏5基本一致，除了挑战者改变挑战阶段。该阶段挑战者均匀地选取矩阵和，随机选取挑战比特b*∈{0,1}并发送给敌手，其中

证明游戏6和游戏5不同的是挑战者用游戏6中c*=v代替游戏5中c*=As+e，其中根据判定性(n,μ)-VLPN假设，这两个游戏中的挑战密文是计算不可区分的。因此，得到Pr[R6]-Pr[R5]≤negl(n)。

游戏7该游戏和游戏6基本一致，除了挑战者改变挑战阶段。该阶段挑战者选取向量和，随机挑选挑战比特b*∈{0,1}并发送给敌手，其中

证明游戏7和游戏6不同的是挑战者用游戏7中的和代替游戏6中的和其中和根据判定性(n,μ)-KLPN假设，这两个游戏中的挑战密文是计算不可区分的，从而Pr[R7]-Pr[R6]≤negl(n)。

游戏8该游戏和游戏7基本一致，除了挑战者改变挑战阶段。该阶段挑战者均匀地选取矩阵和，随机选取挑战比特b*∈{0,1}并发送给敌手，其中

证明游戏8和游戏7不同的是挑战者用游戏8中的代替游戏7中的其中通过使用文献[30]中的引理2.10，不难发现这两个游戏中的挑战密文在敌手看来是不可区分的，从而Pr[R8]-Pr[R7]≤negl(n)。

综上所述，使用引理3至引理11可以证明出该方案的KEM是IND-CCA安全的。换句话来说，即

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

CRYSTALS-Kyber[1]、Classic McEliece[1]、SABER[1]、NTRU-HRSS-KEM[1]、MP[7]和NewHope[31]是基于LWE构造出来的方案，Lepton[1]、CLQY[6]、DMN[32]、KMP[16]和YZ[33]是基于LPN构造出来的方案，PW[34]是基于DDH或者错误学习问题(Learning With Errors,LWE)构造出来的方案，而该研究的构造方案是基于低噪LPN的密钥封装机制。上述方案的困难问题假设对比如表1所示。

表1 不同方案的困难问题假设

假设判定性(n,μ)-VLPN问题能被敌手以时间复杂度为24μn解决，那么该研究的构造方案的KEM被敌手攻克的时间复杂度为24μn+1(2n+m+1)。令n=11 449,c=1/16,μ=0.002 34，可计算出构造方案的KEM能达到128比特安全。在128比特安全下，不同方案的参数对比如表2所示，可以看出，构造方案的KEM公钥长度、私钥长度和密文长度分别为101.56 MB、125.00 MB和9.08 KB，均低于DMN[32]和KMP[16]，构造更为有效。

表2 128比特安全下不同方案的参数对比

注意到基于LWE的方案，如CRYSTALS-Kyber[1]和NTRU-HRSS-KEM[1]是基于有限域GF(q)上的运算，而构造方案则是基于有限域GF(2)上的运算，因此，构造方案在硬件上运行速度更快。

4 结语

研究了首个在标准模型下基于低噪的LPN的IND-CCA安全的密钥封装机制。利用双陷门技术正确回答敌手的解密问询，通过抗第二原像哈希函数确保密文通过有效认证。与一般的密钥封装机制不同的是，该研究构造的CCA安全的密钥封装机制是直接构造的，不依赖于传统的FO变换，且封装密钥不是由哈希函数生成而是由特殊的LPN问题生成。利用FO变换生成的CCA安全的密钥封装机制的安全性规约是不紧凑的，这是因为利用FO变换生成的密钥封装机制都是在随机预言机模型或者量子随机预言机模型下达到CCA安全。相反，该研究的CCA安全的密钥封装机制在标准模型下的安全性规约是紧凑的。除此之外，构造的密钥封装机制是基于低噪的LPN问题而不是LWE问题，因此是在有限域GF(2)上进行运算，硬件运行速度比其他基于LWE问题构造的密钥封装机制更快。