Lizard: Cut off the tail! A practical post-quantum public-key encryption from LWE and LWR

Abstract

© 2018, Springer Nature Switzerland AG.The LWE problem has been widely used in many constructions for post-quantum cryptography due to its reduction from the worst-case of lattice hard problems and the lightweight operations for generating its instances. The PKE schemes based on the LWE problem have a simple and fast decryption, but the encryption phase requires large parameter size for the leftover hash lemma or 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. To the best of our knowledge, Lizard is the first IND-CPA secure PKE under the hardness assumptions of the LWE and LWR problems, and its variant, namely CCALizard, achieves IND-CCA security in the (quantum) random oracle model. Our approach accelerates the encryption speed to a large extent and also reduces the size of ciphertexts. We present an optimized C implementation of our schemes, which shows outstanding performances with concrete security: On an Intel single core processor, an encryption and decryption for CCALizard with 256-bit plaintext space under 128-bit quantum security take only 32,272 and 47,125 cycles, respectively. To achieve these results, we further take some advantages of sparse small secrets. Lizard is submitted to NISTs post-quantum cryptography standardization process.