eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

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


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.

Available format(s)
Publication info
Published elsewhere. Minor revision. ICISC 2016
practicalpost-quantumIND-CCAPKEsparse secretLWEquantum random oracle model
Contact author(s)
nemokjs1 @ snu ac kr
2016-11-21: revised
2016-11-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Kyoo Hyung Han and Jinsu Kim and Changmin Lee and Yongha Son},
      title = {A Practical Post-Quantum Public-Key Cryptosystem Based on spLWE},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1055},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1055}},
      url = {https://eprint.iacr.org/2016/1055}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.