Paper 2017/634

CRYSTALS -- Kyber: a CCA-secure module-lattice-based KEM

Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé

Abstract

Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digital-signature, encryption, and key-establishment protocols, have created significant interest in post-quantum cryptographic schemes. This paper introduces Kyber (part of CRYSTALS -- Cryptographic Suite for Algebraic Lattices -- a package submitted to NIST post-quantum standardization effort in November 2017), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM),based on hardness assumptions over module lattices. Our KEM is most naturally seen as a successor to the NewHope KEM (Usenix 2016). In particular, the key and ciphertext sizes of our new construction are about half the size, the KEM offers CCA instead of only passive security, the security is based on a more general (and flexible) lattice problem, and our optimized implementation results in essentially the same running time as the aforementioned scheme. We first introduce a CPA-secure public-key encryption scheme, apply a variant of the Fujisaki--Okamoto transform to create a CCA-secure KEM, and eventually construct, in a black-box manner, CCA-secure encryption, key exchange, and authenticated-key-exchange schemes. The security of our primitives is based on the hardness of Module-LWE in the classical and quantum random oracle models, and our concrete parameters conservatively target more than $128$ bits of post-quantum security.

Note: Updated to the full version (including Appendix A describing the Kyber.Hybrid construction)

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. 2018 IEEE European Symposium on Security and Privacy (EuroS&P)
DOI
10.1109/EuroSP.2018.00032
Keywords
KEMlattice techniquesimplementation
Contact author(s)
authors @ pq-crystals org
History
2020-10-14: last of 2 revisions
2017-06-27: received
See all versions
Short URL
https://ia.cr/2017/634
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/634,
      author = {Joppe Bos and Léo Ducas and Eike Kiltz and Tancrède Lepoint and Vadim Lyubashevsky and John M.  Schanck and Peter Schwabe and Gregor Seiler and Damien Stehlé},
      title = {CRYSTALS -- Kyber: a CCA-secure module-lattice-based KEM},
      howpublished = {Cryptology ePrint Archive, Paper 2017/634},
      year = {2017},
      doi = {10.1109/EuroSP.2018.00032},
      note = {\url{https://eprint.iacr.org/2017/634}},
      url = {https://eprint.iacr.org/2017/634}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.