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

Jung Hee Cheon, Kyoohyung Han, Jinsu Kim, Changmin Lee, Yongha SonIACR ePrint 2016

TL;DR

This paper introduces a practical public-key cryptosystem (PKE) designed to be secure against quantum computers, built upon a variant of the Learning with Errors (LWE) problem called sparse LWE (spLWE). The proposed system offers efficient encryption and decryption, achieving 128-quantum bit security with performance in the hundreds of microseconds.

What Problem Does This Paper Address?

The advent of quantum computing poses a significant threat to current public-key cryptography, which relies on problems like integer factorization and discrete logarithms that quantum algorithms can solve efficiently. This has spurred research into "post-quantum" cryptography, aiming to develop systems resistant to both classical and quantum attacks. Lattice-based cryptography, particularly schemes based on the Learning with Errors (LWE) problem, is a leading candidate due to its strong security guarantees and potential for efficiency. However, many existing LWE-based schemes suffer from large key sizes or slow performance, hindering practical adoption. This paper addresses the need for a practical, efficient, and quantum-resistant public-key cryptosystem by proposing a new scheme based on a variant of LWE that uses a sparse secret key (spLWE).

Methods

The authors propose a public-key cryptosystem (PKE) based on a new hardness assumption: sparse Learning with Errors (spLWE). They construct an IND-CPA secure PKE and then convert it into an IND-CCA secure scheme using a modified Fujisaki-Okamoto transformation in the quantum random oracle model.

Key methodological contributions include:

  • spLWE (Sparse Learning with Errors): A variant of the LWE problem where the secret vector has a limited number of non-zero entries. This sparsity is exploited to improve efficiency.
  • IND-CPA PKE Construction: A public-key encryption scheme designed to be secure against chosen-plaintext attacks.
  • IND-CCA Conversion: A transformation to upgrade the IND-CPA scheme to an IND-CCA (chosen-ciphertext attacks) secure scheme, which is a stronger security notion. This conversion uses a modified Fujisaki-Okamoto transform, which is known to be efficient.
  • Reduction from LWE to spLWE: The authors provide a theoretical proof that the hardness of spLWE can be based on the hardness of the standard LWE problem. This is crucial for establishing the security of their scheme.
  • Modified Attacks: They adapt existing attacks on LWE to exploit the sparsity of the secret key in spLWE, allowing them to derive more suitable parameters for their scheme.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Sparsity as an Efficiency Lever: The core insight is that by using a secret key with a sparse structure (few non-zero elements), the computational cost of cryptographic operations can be significantly reduced without compromising security, provided the sparsity is managed correctly.
  • Bridging Theory and Practice: The paper demonstrates a practical instantiation of a post-quantum cryptosystem, moving beyond theoretical constructions to provide concrete performance figures and parameter choices.
  • Security via Reduction: The theoretical reduction from LWE to spLWE is a critical insight, as it allows the security of the proposed system to be inherited from the well-studied LWE problem.
  • Balancing Security and Efficiency: The authors highlight the trade-offs involved, particularly that spLWE might require larger dimensions than LWE for equivalent security, but this is offset by the efficiency gains from sparsity.

Key Results

  • Practical IND-CPA and IND-CCA Schemes: The paper presents two PKE schemes: one achieving IND-CPA security and another achieving IND-CCA security.
  • Efficient Performance: For 256-bit messages and 128-quantum bit security, the IND-CCA scheme achieves encryption times of approximately 313 microseconds and decryption times of 302 microseconds on a standard PC. The IND-CPA scheme is similarly efficient.
  • Smaller Ciphertext Size: The proposed IND-CPA encryption scheme has a ciphertext size of (n log q + 2l)-bit for an l-bit message, which is noted as being smaller than some existing LWE-based PKEs.
  • Theoretical Security Foundation: The hardness of spLWE is proven to be reducible to the hardness of the standard LWE problem, providing a strong theoretical basis for the scheme's security.
  • Parameter Derivation: The authors analyze existing attacks and adapt them to spLWE, enabling them to derive concrete parameters that balance security and performance.

Limitations and Future Work

  • Dimension vs. Sparsity Trade-off: While sparsity improves efficiency, it may necessitate larger dimensions for the underlying lattice problems to maintain security compared to non-sparse LWE. The paper notes that the dimension of spLWE remains below 520 for their chosen parameters.
  • Reduction Tightness: The reduction from LWE to spLWE is not tight enough to directly derive optimal parameters for practical use. The authors acknowledge that their reduction serves to guarantee hardness but is not sufficient for precise parameter setting.
  • Random Oracle Model: The IND-CCA security proof for PKE2 relies on the random oracle model, which is a standard assumption but not a fully concrete security guarantee.
  • Future Work: The paper suggests further investigation into the parameter space and potential optimizations. The authors also mention that the efficiency of their scheme is more pronounced compared to RLWE-based schemes, hinting at further exploration in this direction.

Summary updated

BibTeX
@article{cheon2016practical,
  author = {Jung Hee Cheon and Kyoohyung Han and Jinsu Kim and Changmin Lee and Yongha Son},
  title = {{A Practical Post-Quantum Public-Key Cryptosystem Based on spLWE}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2016},
}
Figure