基于Ring-LPN的高效公钥加密方案

LPN(Learning Parity With Noise)问题是构造后量子密码方案的基础问题之一。基于LPN构造的密码方案具有计算速度快和抗量子计算攻击的优点,但基于普通LPN构造的密码方案存在密钥空间大这一影响其可用性的缺点。基于结构化的LPN（比如Ring-LPN、 Toepliz-LPN等）构造公钥密码可以降低存储要求,进一步提高方案的效率。因此,利用Ring-LPN的特有优势并结合标签加密构造技术,提出并证明了环上的背包问题,设计了一个基于Ring-LPN且CCA（Chosen-Ciphertext-Attacks）安全的公钥加密方案。与基于普通LPN的同类型密码方案相比较,所提出的方案以环多项式向量为公私钥,在计算上采取快速傅里叶变换,可以大幅提高加解密速率,因此方案具有更小的计算开销和存储开销;与达到相同安全级别的LPN方案相比,所需的样本数更少,密文扩展率更小。同时,方案的CCA安全性在标准模型下归约到了Ring-LPN假设。