CCA Secure Public Key Encryption And Key Encapsulation Mechanism Based On Low-Noise LPN

With the rapid development of quantum theory,Shor and Grover algorithms can quickly solve some classical hard problems such as RSA large number decomposition under the quantum model,and many common encryption algorithms and protocols nowadays mainly rely on these classical hard problems.Therefore,Shor's algorithm and Grover's algorithm will impose higher requirements on the information security protected by traditional cryptosystems and current network communication security.the LPN problem is an excellent candidate hypothesis in the field of post-quantum cryptography,which is not only applicable to some weak power devices,but also resistant to the attacks of quantum algorithms.In this paper,we focus on the public key encryption scheme and key encapsulation mechanism based on the variant LPN problem.By using the one-time signatures,Dottling et al.(ASIACRYPT 2012)initiated the first secure public key encryption(PKE)under the low-noise LPN assumption.Kiltz et al.(PKC 2014)proposed a simpler and more efficient scheme using double-trapdoor technique from the same assumption.Both schemes abide the decoding failure rate(DFR)2-?(k)(k is the security parameter).In this work,we first introduce a variant(VxLPN)of the low-noise Exact LPN(xLPN,proposed by Jain et al.at ASIACRYPT 2012 and used as building block in commitments and zero-knowledge proofs).A series of reductions show that VxLPN is at least as hard as the standard LPN for the same noise rate ?.We then construct from the VxLPN CPA/CCA2 secure PKE schemes with squared-exponential DFR 2-?(k2)which share the common structure extrinsically with Kiltz et al.and Yu et al.schemes.Consider the performance on 128-bit security level,our CCA2-secure scheme only holds 117.79MB public keys,67.31MB secret keys and 10.15KB ciphertexts,and thus is more efficient than the schemes of Dottling et al.and Kiltz et al((14.53GB,14.48GB,14.06KB)and(161.78MB,92.45MB,13.60KB)respectively).Many Chosen-Ciphertext(CCA)secure KEM schemes are constructed from ChosenPlaintext(IND-CPA)or One-Way(OW-CPA)secure PKE via the generic FujisakiOkamoto(FO)transformations(CRYPTO 2018).However,the security relies on the Random Oracle Model(ROM).To the best of our knowledge,there are no CCA secure KEM schemes based on Learning Parity with Noise(LPN)assumption that can against post quantum attacks in the standard model.In this work,we propose the first direct construction of LPN-based KEM,which is secure in the standard model.In particular,we use double-trapdoor technique to answer adversary's decapsulation queries correctly and a Target Collision Resistant(TCR)hash function 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 CCA secure against post-quantum attacks under the low-noise LPN assumptions by a series of games and the security reduction is tight.