[Resource Topic] 2016/1055: A Practical Post-Quantum Public-Key Cryptosystem Based on spLWE

Welcome to the resource topic for 2016/1055

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

Authors: Jung Hee Cheon, Kyoo Hyung Han, Jinsu Kim, Changmin Lee, 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.

ePrint: https://eprint.iacr.org/2016/1055

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .