Paper 2016/1126

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

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


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Post-Quantum CryptographyPublic-Key EncryptionLearning with RoundingLearning with Errors
Contact author(s)
doodoo1204 @ snu ac kr
2017-07-06: last of 6 revisions
2016-12-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Duhyeong Kim and Joohee Lee and Yongsoo Song},
      title = {Lizard: Cut off the Tail! Practical Post-Quantum Public-Key Encryption from LWE and LWR},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1126},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.