Paper 2016/1055

A Practical Post-Quantum Public-Key Cryptosystem Based on spLWE

Jung Hee Cheon, Kyoo Hyung Han, Jinsu Kim, Changmin Lee, and Yongha Son

Abstract

The Learning with Errors (LWE) problem has been widely used as a hardness assumption to construct public-key primitives. In this paper, we propose an efficient instantiation of a PKE scheme based on LWE with a sparse secret, named as spLWE. We first construct an IND-CPA PKE and convert it to an IND-CCA scheme in the quantum random oracle model by applying a modified Fujisaki-Okamoto conversion of Unruh. In order to guarantee the security of our base problem suggested in this paper, we provide a polynomial time reduction from LWE with a uniformly chosen secret to spLWE. We modify the previous attacks for LWE to exploit the sparsity of a secret key and derive more suitable parameters. We can finally estimate performance of our scheme supporting 256-bit messages: our implementation shows that our IND-CCA scheme takes 313 micro seconds and 302 micro seconds respectively for encryption and decryption with the parameters that have 128-quantum bit security.

Note: For more easy understanding, we add a new section 'Results and techniques' at page 2. The previous ‘Contribution’ section is incorporated to the 'Introduction' section. We find some software implementation results for LWE-based PKE [LP11] and RLWE-based PKE [LPR10]. They also implemented at a PC environment which is similar to us. Therefore, we have added tables which compare ours result with them at page 14, section 5.2.