Paper 2016/1126

Lizard: Cut off the Tail! Practical Post-Quantum Public-Key Encryption from LWE and LWR

Jung Hee Cheon and Duhyeong Kim and Joohee Lee and Yongsoo Song

Abstract

The Learning with Errors (LWE) is one of the most promising primitive for post-quantum cryptography due to its strong security reduction from the worst-case of NP-hard problems and its lightweight operations. The Public Key Encryption (PKE) scheme based on LWE has a simple and fast decryption, but its encryption is rather slow due to large parameter sizes for Leftover Hash Lemma or expensive Gaussian samplings. In this paper, we propose a novel PKE without relying on either of them. For encryption, we first combine several LWE instances as in the previous LWE-based PKEs. However, the following step to re-randomize this combination before adding a message is different: remove several least significant bits of ciphertexts rather than inserting errors. We prove that our scheme is IND-CPA secure under the hardness of LWE and can be converted into an IND-CCA scheme in the quantum random oracle model. Our approach accelerates encryption speed to a large extent and also reduces the size of cipher- texts. The proposed scheme is very competitive for all applications requiring both of fast encryption and decryption. In our single-core implementation in Macbook Pro, encryption and decryption of a 128-bit message for quantum 128-bit security take 7 and 6 microseconds that are 3.4 and 4.2 times faster than those of NTRU PKE, respectively. To achieve these results, we further take some advantage of sparse small secrets, under which the security of our scheme is also proved.