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 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.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Keywords
- Post-Quantum CryptographyPublic-Key EncryptionLearning with RoundingLearning with Errors
- Contact author(s)
- doodoo1204 @ snu ac kr
- History
- 2017-07-06: last of 6 revisions
- 2016-12-02: received
- See all versions
- Short URL
- https://ia.cr/2016/1126
- License
-
CC BY