CRYSTALS-Kyber#
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”.
In the following guide:
\(R\) denotes the ring \(\mathbb{Z}[X]/(X^n + 1)\).
\(R_q\) denotes the ring \(\mathbb{Z}_q[X]/(X^n + 1)\).
\(n = 2^{n'-1}\) such that \(X^n + 1\) is the \(2^{n'}\)-th cyclotomic polynomial.
\(\mathcal{B}^K\) (resp. \(\mathcal{B}^*\)) is the set of bytes arrays of length \(k\) (resp. of arbitrary length).
Parameters#
Parameters |
Description |
|---|---|
\(n\) |
\(n = 2^{n' - 1}\) such that \(X^n + 1\) is the \(2^{n'}\)-th cyclotomic polynomial. |
\(k\) |
The lattice dimension is set to a multiple of \(n\), with \(k\) being the multiplier. Kyber uses this parametrize the security/efficiency of the algorithm. |
\(q\) |
A small prime satisfying \(n | (q-1)\) while retaining CCA security. Using a small prime allows the use of fast multiplication based on NTT. |
\(\eta_1\), \(\eta_2\) |
Kyber uses a centered binomial distribution noted \(B_{\eta}\), with \(\eta = 2\) or \(\eta = 3\), for sampling noise. \(\eta_1\) defines the noise used in Kyber.CPAPKE.KeyGen and some of the noise in Kyber.CPAPKE.Enc, while \(\eta_2\) defines the noise of Kyber.CPAPKE.Enc only. |
\(d_u\), \(d_v\) |
Control the ciphertext compression. |
Parameter set |
\(n\) |
\(k\) |
\(q\) |
\(\eta_1\) |
\(\eta_2\) |
\(d_u\) |
\(d_v\) |
NIST security level |
Equivalent AES security |
|---|---|---|---|---|---|---|---|---|---|
Kyber512 |
256 |
2 |
3329 |
3 |
2 |
10 |
4 |
1 |
AES-128 |
Kyber768 |
256 |
3 |
3329 |
2 |
2 |
10 |
4 |
3 |
AES-192 |
Kyber512 |
256 |
4 |
3329 |
2 |
2 |
11 |
5 |
5 |
AES-256 |
Parameter set |
Private key |
Public Key |
Ciphertext |
|---|---|---|---|
Kyber512 |
1632 |
800 |
768 |
Kyber768 |
2400 |
1184 |
1088 |
Kyber1024 |
3168 |
1568 |
1568 |
There is a variant of Kyber that uses the existing hardware support for symmetric primitives. Called Kyber-90s, it uses AES-256-CTR and SHA2.
The authors offer two recommendations:
Using Kyber in a hybrid-mode, combined with an established primitive such as elliptic curve Diffie-Hellman.
Using the Kyber768 parameter set, which is estimated to achieve more than 128 bits of security.
Implementations#
The reference implementation can be found on GitHub: pq-crystals/kyber. It includes an optimized version with AVX2.
The repository and the NIST submission packages include an AVX2 optimized implementation.
Kyber is integrated in Open Quantum Safe’s liboqs and PQClean. The latter includes an aarch64 version.
Other third-party implementations are referenced in the Software page, such as:
An integration in Amazon’s AWS Key Management Service [Wei20].
An integration in the Botan C++ library.
An integration in Bouncy Castle.
And implementations in a variety of programming languages such as Rust, Python, Java, and Go.
Benchmarks#
Benchmarks performed on an Intel i7-8565u using the provided programs.
There are also benchmarks provided by the authors in Kyber’s homepage as well as benchmarks from the SUPERCOP benchmarking framework.
Parameter set |
Key generation |
Encapsulation |
Decapsulation |
|---|---|---|---|
Kyber512 |
78335 |
90264 |
106145 |
Kyber768 |
124656 |
142119 |
208495 |
Kyber1024 |
185777 |
212082 |
265636 |
Kyber512 AVX2 |
12755 |
22709 |
22268 |
Kyber768 AVX2 |
27143 |
37498 |
28226 |
Kyber1024 AVX2 |
43098 |
48344 |
40643 |
Parameter set |
Key generation |
Encapsulation |
Decapsulation |
|---|---|---|---|
Kyber512-90s |
108869 |
134826 |
143744 |
Kyber768-90s |
196670 |
221077 |
242194 |
Kyber1024-90s |
305843 |
392176 |
491882 |
Kyber512 AVX2 |
13736 |
20315 |
12789 |
Kyber768 AVX2 |
16085 |
22532 |
14556 |
Kyber1024 AVX2 |
20939 |
26990 |
20392 |
Attacks#
The paper has a section called “Analysis with respect to known attacks.
More recently, there have been a number of side-channels attacks:
A Side-Channel Attack on a Hardware Implementation of CRYSTALS-Kyber, [JWN+23].
A Side-Channel Secret Key Recovery Attack on CRYSTALS-Kyber Using k Chosen Ciphertexts, [WD23], [YWY+23].
Secret Key Recovery Attacks on Masked and Shuffled Implementations of CRYSTALS-Kyber and Saber, [BNGD22].
Chosen-Ciphertext Clustering Attack on CRYSTALS-Kyber Using the Side-Channel Leakage of Barrett Reduction, [SPH22].
Bibliography#
Linus Backlund, Kalle Ngo, Joel Gärtner, and Elena Dubrova. Secret key recovery attacks on masked and shuffled implementations of crystals-kyber and saber. Cryptology ePrint Archive, Paper 2022/1692, 2022. https://eprint.iacr.org/2022/1692. URL: https://eprint.iacr.org/2022/1692.
Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem. In Gerhard Goos, Juris Hartmanis, Jan van Leeuwen, and Joe P. Buhler, editors, Algorithmic Number Theory, volume 1423, pages 267–288. Springer Berlin Heidelberg, Berlin, Heidelberg, 1998. URL: http://link.springer.com/10.1007/BFb0054868 (visited on 2023-07-12), doi:10.1007/BFb0054868.
Yanning Ji, Ruize Wang, Kalle Ngo, Elena Dubrova, and Linus Backlund. A Side-Channel Attack on a Hardware Implementation of CRYSTALS-Kyber. In 2023 IEEE European Test Symposium (ETS), 1–5. Venezia, Italy, May 2023. IEEE. URL: https://ieeexplore.ieee.org/document/10174000/ (visited on 2023-07-19), doi:10.1109/ETS56758.2023.10174000.
Bo-Yeon Sim, Aesun Park, and Dong-Guk Han. Chosen-Ciphertext Clustering Attack on CRYSTALS-KYBER Using the Side-Channel Leakage of Barrett Reduction. IEEE Internet of Things Journal, 9(21):21382–21397, November 2022. URL: https://ieeexplore.ieee.org/document/9786796/ (visited on 2023-07-19), doi:10.1109/JIOT.2022.3179683.
Nick Sullivan. Securing the post-quantum world. December 2020. URL: http://blog.cloudflare.com/securing-the-post-quantum-world/ (visited on 2023-07-17).
Ruize Wang and Elena Dubrova. A Side-Channel Secret Key Recovery Attack on CRYSTALS-Kyber Using k Chosen Ciphertexts. In Said El Hajji, Sihem Mesnager, and El Mamoun Souidi, editors, Codes, Cryptology and Information Security, volume 13874, pages 109–128. Springer Nature Switzerland, Cham, 2023. URL: https://link.springer.com/10.1007/978-3-031-33017-9_7 (visited on 2023-07-19), doi:10.1007/978-3-031-33017-9_7.
Alex Weibel. Round 2 post-quantum TLS is now supported in AWS KMS \textbar AWS Security Blog. November 2020. Section: Advanced (300). URL: https://aws.amazon.com/blogs/security/round-2-post-quantum-tls-is-now-supported-in-aws-kms/ (visited on 2023-07-17).
Yipei Yang, Zongyue Wang, Jing Ye, Junfeng Fan, Shuai Chen, Huawei Li, Xiaowei Li, and Yuan Cao. Chosen ciphertext correlation power analysis on Kyber. Integration, 91:10–22, July 2023. URL: https://linkinghub.elsevier.com/retrieve/pii/S0167926023000378 (visited on 2023-07-19), doi:10.1016/j.vlsi.2023.02.012.