Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / KEM, lattice techniques, implementation

Date: received 27 Jun 2017

Contact author: authors at pq-crystals org

Available format(s): PDF | BibTeX Citation

Version: 20170627:201157 (All versions of this report)

Short URL: ia.cr/2017/634

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]