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

摘要

选择密文攻击下的不可区分(Indistinguishability against Chosen Ciphertext Attack,IND-CCA)安全的密钥封装机制可以由选择明文攻击下的不可区分(Indistinguishability against Chosen Plaintext Attack,IND-CPA)或者选择明文攻击下的单向(One-Wayness against Chosen Plaintext Attack,OW-CPA)安全的公钥加密方案使用FO(Fujisaki-Okamoto)变换得到,并在随机预言机模型(Random Oracle Model,ROM)下是安全的。截止目前,并没有一个基于LPN(Learning Parity with Noise)问题的密钥封装机制能在标准模型下达到选择密文攻击(Chosen Ciphertext Attack,CCA)安全。以双陷门技术回答敌手的解封装询问,以抗第二原像哈希函数检测方案中密文的有效性,由此可得出首个基于LPN在标准模型下达到CCA安全的密钥封装机制的直接构造,其密钥通过特殊LPN问题构造,并不依赖随机预言机。通过一系列的游戏和相邻游戏间的安全规约,可证明该密钥封装机制在量子算法的攻击下是CCA安全的。