徐胜峰，李祥学,2

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

LPN(Learning Parity with Noise)问题在后量子密码领域是一个常用的假设[1]，主要用来构造一些加密算法和协议，如公钥加密算法和传输协议等。这些基于LPN构造出来的加密算法和协议性能高并能抵抗量子算法的攻击。

Alekhnovich[19]最早构造出基于低噪LPN的选择明文攻击下的不可区分(Indistinguishability against Chosen Plaintext Attack，IND-CPA)安全的公钥加密方案。随后，Döttling等人[11]利用相关认证技术[20]首次构造出基于低噪LPN的选择密文攻击下的不可区分(Indistinguishability against Chosen Ciphertext Attack,IND-CCA)安全的公钥加密方案，但是方案的公钥、私钥和密文长度过大，效率有待提高。Kiltz等人[21]利用双陷门技术构造出IND-sTag-CCA安全的带标签公钥加密方案，并将该方案通过常见的技术手段转变成IND-CCA安全的公钥加密方案。双陷门技术在方案的安全性证明中用来回答敌手的解密询问。这两个IND-CCA安全的公钥加密方案的解码错误率(Decoding Failure Rate，DFR)均是2-Θ(k)，k为安全参数。Yu等人[14]构造出基于常噪LPN问题的CCA安全公钥加密方案的解码错误率为2-Θ(k2)。

到目前为止，并没有基于变体xLPN(Variant of the Exact LPN，VxLPN)的CPA/CCA安全的公钥加密方案。因此，该研究拟证明VxLPN问题和标准LPN问题一样困难，并通过双陷门技术，构造基于VxLPN的IND-CPA/CCA安全的公钥加密方案，以期降低解码错误率，提高效率。

1 预备知识

1.1 符号描述

为了表述方便，对文中符号进行描述。黑体小写字母表示列向量，如s，黑体小写字母的转置表示行向量，如sT。列向量s的汉明重量表示为|s|。黑体的大写字母表示矩阵，如A，黑体大写字母的转置表示矩阵的转置，如AT。……