CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM

By Joppe W. Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Damien Stehlé. European Symposium on Security and Privacy, 2017

1,190 citations recorded by the source corpus.

Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digitalsignature, 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 postquantum security.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

View Paper: https://www.semanticscholar.org/paper/a57342d25e255b75a469a8ebc990cb136c6bf2e1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Information Systems

Citations in the corpus

A Modular Analysis of the Fujisaki-Okamoto Transformation (2017, background): “Dealing with imperfectly correct schemes is of great importance since many (but not all) practical lattice-based encryption schemes have a small correctness error, see, e.g., DXL [21], Peikert [34], BCNS [14], New Hope [3], Frodo [13], Lizard [17], and Kyber [12].”
Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM (2018, methodology): “Multi target protection: As described in [16], hashing the public key into K̂ has two beneficial effects: it makes sure that K depends on the input of both parties, and it offers multi-target protection.”
Communication-Computation Trade-offs in PIR (2019, methodology): “• Finally, we propose to use a technique used in most postquantum lattice-based encryption schemes proposed for standardization to NIST, such as NewHope [4] and CRYSTALKyber [9], that we call bit-dropping.”