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

Post-quantum public key encryption based on LPN

作　　者：徐胜峰 李祥学[1,2] XU Shengfeng;LI Xiangxue(School of Computer Science and Technology,East China Normal University,Shanghai 200062,China;School of Software Engineering,East China Normal University,Shanghai 200062,China)

机构地区：[1]华东师范大学计算机科学与技术学院,上海200062 [2]华东师范大学软件工程学院,上海200062

出　　处：《西安邮电大学学报》2021年第6期48-56,共9页Journal of Xi’an University of Posts and Telecommunications

基　　金：国家自然科学基金项目(61971192);国家密码发展基金项目(MMJJ20180106)。

摘　　要：选择密文攻击下的不可区分(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安全的。Chosen-Ciphertext(IND-CCA)secure KEM schemes could be constructed from Chosen-Plaintext(IND-CPA)or One-Way(OW-CPA)secure PKE via the generic Fujisaki-Okamoto(FO)transformations.Such security relies on the Random Oracle Model(ROM).To the best of our knowledge,there are no IND-CCA secure KEM schemes based on Learning Parity with Noise(LPN)assumption secure against post quantum attacks in the standard model.The first direct construction of LPN-based KEM is proposed,which is secure in the standard model.Double-trapdoor technique is adopted to answer adversary's decryption queries correctly and a Target Collision Resistant(TCR)Hash function is used to check the validity of the ciphertext.The encapsulated key is determined by a special LPN problem(with no random oracle required).The scheme is IND-CCA secure against post-quantum attacks under the low-noise LPN assumptions by a series of games.

关 键 词：后量子密码学 LPN问题 密钥封装机制 选择明文攻击安全 选择密文攻击安全 低噪 

分 类 号：TN918.4[电子电信—通信与信息系统]