Introduction
Kyber is an IND-CCA2-secure key encapsulation mechanism (KEM), whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices. Kyber is one of the finalists in the NIST post-quantum cryptography project. The submission lists three different parameter sets aiming at different security levels. Specifically, Kyber-512 aims at security roughly equivalent to AES-128, Kyber-768 aims at security roughly equivalent to AES-192, and Kyber-1024 aims at security roughly equivalent to AES-256.
For users who are interested in using Kyber, we recommend the following:
- Use Kyber in a so-called hybrid mode in combination with established "pre-quantum" security; for example in combination with elliptic-curve Diffie-Hellman.
- We recommend using the Kyber-768 parameter set, which—according to a very conservative analysis—achieves more than 128 bits of security against all known classical and quantum attacks.
Scientific Background
The design of Kyber has its roots in the seminal LWE-based encryption scheme of Regev. Since Regev's original work, the practical efficiency of LWE encryption schemes has been improved by observing that the secret in LWE can come from the same distribution as the noise and also noticing that "LWE-like" schemes can be built by using a square (rather than a rectangular) matrix as the public key. Another improvement was applying an idea originally used in the NTRU cryptosystem to define the Ring-LWE and Module-LWE problems that used polynomial rings rather than integers. The CCA-secure KEM Kyber is built on top of a CPA-secure cryptosystem that is based on the hardness of Module-LWE.
Users of Kyber
Kyber is already being integrated into libraries and systems by industry. For example,
- Cloudflare integrated Kyber alongside other PQ algorithms into CIRCL, the Cloudflare Interoperable, Reusable Cryptographic Library;
- Amazon now supports hybrid modes involving Kyber in their AWS Key Management Service; and
- already in 2019 IBM advertised the "World’s First Quantum Computing Safe Tape Drive" using Kyber and Dilithium.
Performance Overview
The tables below gives an indication of the performance of Kyber. All benchmarks were obtained on one core of an Intel Core-i7 4770K (Haswell) CPU. We report benchmarks of two different implementations: a C reference implementation and an optimized implementation using AVX2 vector instructions. For benchmarks on an ARM Cortex-M4 microcontroller, see the benchmarks reported by the pqm4 project.
| Kyber-512 | |||||
|---|---|---|---|---|---|
| Sizes (in bytes) | Haswell cycles (ref) | Haswell cycles (avx2) | |||
| sk: | 1632 | gen: | 122684 | gen: | 33856 |
| pk: | 800 | enc: | 154524 | enc: | 45200 |
| ct: | 768 | dec: | 187960 | dec: | 34572 |
| Kyber-768 | |||||
| Sizes (in bytes) | Haswell cycles (ref) | Haswell cycles (avx2) | |||
| sk: | 2400 | gen: | 199408 | gen: | 52732 |
| pk: | 1184 | enc: | 235260 | enc: | 67624 |
| ct: | 1088 | dec: | 274900 | dec: | 53156 |
| Kyber-1024 | |||||
| Sizes (in bytes) | Haswell cycles (ref) | Haswell cycles (avx2) | |||
| sk: | 3168 | gen: | 307148 | gen: | 73544 |
| pk: | 1568 | enc: | 346648 | enc: | 97324 |
| ct: | 1568 | dec: | 396584 | dec: | 79128 |
As an update for round 2 of the NIST project we also proposed a variant of Kyber that is meant to showcase the performance of Kyber when hardware support for the symmetric primitives is available. This variant, called Kyber-90s, uses AES-256 in counter mode and SHA2 instead of SHAKE.
| Kyber-512-90s | |||||
|---|---|---|---|---|---|
| Haswell cycles (ref) | Haswell cycles (avx2) | ||||
| gen: | 213156 | gen: | 21880 | ||
| enc: | 213156 | enc: | 28592 | ||
| dec: | 277612 | dec: | 20980 | ||
| Kyber-768-90s | |||||
| Haswell cycles (ref) | Haswell cycles (avx2) | ||||
| gen: | 389760 | gen: | 30460 | ||
| enc: | 432764 | enc: | 40140 | ||
| dec: | 473984 | dec: | 30108 | ||
| Kyber-1024-90s | |||||
| Haswell cycles (ref) | Haswell cycles (avx2) | ||||
| gen: | 636380 | gen: | 43212 | ||
| enc: | 672644 | enc: | 56556 | ||
| dec: | 724144 | dec: | 44328 | ||