Cryptology ePrint Archive: Report 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 LWE problem has been widely used in many constructions for post-quantum cryptography due to its strong security reduction from the worst-case of lattice hard problems and its lightweight operations. The PKE schemes based on the LWE problem have a simple and fast decryption, but the encryption phase is rather slow due to large parameter size for the leftover hash lemma or expensive Gaussian samplings. In this paper, we propose a novel PKE scheme, called Lizard, without relying on either of them. The encryption procedure of Lizard first combines several LWE samples as in the previous LWE-based PKEs, but the following step to re-randomize this combination before adding a plaintext is different: it removes several least significant bits of each component of the computed vector rather than adding an auxiliary error vector. Lizard is IND-CPA secure under the hardness assumptions of the LWE and LWR problems, and its variant achieves IND-CCA security in the quantum random oracle model. Our approach accelerates encryption speed to a large extent and also reduces the size of ciphertexts, and Lizard is very competitive for applications requiring fast encryption and decryption phases. In our single-core implementation on a laptop, the encryption and decryption of IND-CCA Lizard with 256-bit plaintext space under 128-bit quantum security take 0.014 and 0.027 milliseconds, which are comparable to those of NTRU. To achieve these results, we further take some advantages of sparse small secrets.

Category / Keywords: Post-Quantum Cryptography, Public-Key Encryption, Learning with Rounding, Learning with Errors

Date: received 1 Dec 2016, last revised 6 Jul 2017

Contact author: doodoo1204 at snu ac kr

Available format(s): PDF | BibTeX Citation

Version: 20170706:070616 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]