徐胜峰，李祥学,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和密文……