Paper 2017/634

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

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

Abstract

Recent advances in quantum computing and the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digital-signature, encryption, and key-establishment protocols increased interest in post-quantum cryptographic schemes. This paper introduces Kyber (part of the CRYSTALS -- Cryptographic Suite for Algebraic Lattices -- package that will be submitted to the NIST call for post-quantum standards), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM), based on hardness assumptions over module lattices. 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. We implemented and benchmarked the CCA-secure KEM and key exchange protocols against the ones that are based on LWE and Ring-LWE: we conclude that our schemes are not only as efficient but also feature more flexibility and security advantages over the latter schemes.