CRYSTALS-Kyber: LWE-based key encapsulation

[latexpage]

Introduction

In the context of the NIST standardization process for identifying and analyzing Post-Quantum Cryptography (PQC) solutions, the first crucial outcome is given by the selection of the key encapsulation mechanism CRYSTALS-Kyber. Kyber is a public key cryptographic scheme enabling two parties to derive a common secret for protecting their information exchange. The main features that allowed Kyber to be selected as the primary KEM solution, among the initial 45 proposals, are its efficiency and its security in the face of the best known classical and quantum attacks. In modern cryptographic protocols, Kyber is set to replace cryptographic key exchange techniques based on mathematical problems vulnerable to quantum computer, such as the widely used Elliptic Curve Diffie-Hellman (ECDH) key exchange.

CRYSTALS-Kyber

To understand the rationale underlying Kyber’s design, it is worth proceeding by steps. The starting point is the encryption scheme based on LWE, the second step is the extension to Module-LWE, while the last one is the transformation from encryption scheme to key encapsulation mechanism. In the following, some useful notation is introduced.

• $q$ is a prime number
• $\mathbb{Z}_q$ denotes the set $\{0,\dots,q-1\}$
• $R_q=\mathbb{Z}_q[X]/(X^n+1)$ denotes the set of polynomials in $X$ with coefficients in $\mathbb{Z}_q$ modulo the relation $X^n=-1$
• Given a set $S$, $s\leftarrow S$ denotes that $s$ is uniformly sampled from $S$
• $s\in \mathbb{Z}_q\gets B_{\eta}$ denotes that $s$ is sampled from a centered binomial distribution [1] with parameter $\eta$
• $f\in R_q\gets B_\eta$ denotes that each coefficient of $f$ is sampled from $B_\eta$
• $\textsf{H}$, $\textsf{G}$ are hash functions
• $\textsf{KDF}$ is a key derivation function

LWE Public Key Encryption (PKE)

As with other public key encryption schemes, LWE PKE consists of three algorithms: key generation, encryption and decryption. Notice that LWE PKE can be considered a “toy” scheme, since it enables encrypting just a single bit $x\in\{0,1\}$.

1. Key generation : the vector $\mathbf{s}$ and the matrix $\mathbf{A}$ are uniformly sampled from $\mathbb{Z}_q^k$ and $\mathbb{Z}_q^{m\times k}$. The error $\mathbf{e}=(e_1,\dots,e_m)^{T}\in\mathbb{Z}_q^{m}$ is sampled from $B_\eta^m$. $\mathbf{s}$ is the private key while the pair $(\mathbf{A},\mathbf{b}=\mathbf{As}+\mathbf{e})$ is the public key. Due to security reasons, note that $m > k$.
2. Encryption of $x\in\{0,1\}$: the ciphertext consists of a vector $\mathbf{u}\in\mathbb{Z}_q^k$ given by the sum of the rows of $\mathbf{A}$ corresponding to a certain index subset $P$ and an element $v\in\mathbb{Z}_q$ obtained from the sum of the entries of $\mathbf{b}$ corresponding to $P$ and the value $\lfloor \frac{q}{2} \cdot x\rfloor$ [2]. Observe that an attacker knowing $P$ can derive $x$, therefore the uniform sampling of $P$ is crucial.
3. Decryption of $(\mathbf{u},v)$: thanks to the knowledge of the private key, $x$ is obtained by checking if $v-\langle \mathbf{u}, \mathbf{s}\rangle$ is closer to $0$ or $\lfloor \frac{q}{2}\rfloor$.

Kyber Public Key Encryption (PKE)

The Kyber PKE scheme mimics the case discussed above, with a variation in the mathematical structure the elements live in. Indeed, one moves from $\mathbb{Z}_q$ to $R_q$. It is worth noting that, although Kyber PKE is not a toy construction, it still cannot be used as a “standalone” encryption solution, since it does not guarantee all the security requirements needed in a practical context. Indeed, this construction achieves just IND-CPA security [3] (indistinguishability under chosen plaintext attack), a standard security notion in cryptography but an insufficient one for most use cases. The fundamental role of Kyber PKE is instead to serve as a building block for the key encapsulation mechanism exposed by Kyber.

 At a high level, the steps are the same as LWE PKE.

1. Key Generation : the secret $\mathbf{s}\in R_q^k$ and the error $\mathbf{e}\in R_q^k$ are sampled from $B_{\eta_1}^k$ and $B_{\eta_2}^k$ respectively. The public matrix $\mathbf{A}$ is uniformly sampled from $R_q^{k\times k}$.
2. Encryption of $m\in R_q$: the vector $\mathbf{r}\in R_q^k$, sampled from $B_{\eta_1}^k$, has the same role as $P$ in the LWE PKE case. The sampling of additional errors $\mathbf{e}_1\in R_q^k$ and $e_2\in R_q$ is needed for security reasons since, unlike LWE PKE, one works with a square matrix $\mathbf{A}$ [4]. The symbol $\lceil\cdot\rfloor$ denotes that for each coefficient of the considered element, one takes the approximation to the closest integer.
3. Decryption of $(\mathbf{u},v)$: the rationale follows the LWE PKE one.

The correctness [5] of the scheme is guaranteed by the following equality. \[ v-\langle \mathbf{u},\mathbf{s} \rangle= \mathbf{s}^{T}\mathbf{A}^{T}\mathbf{r}+\mathbf{e}^{T}\mathbf{r}+e_2+\Big\lceil\frac{q}{2}\cdot m\Big\rfloor-\mathbf{s}^{T}\mathbf{A}^{T}\mathbf{r}-\mathbf{s}^{T}\mathbf{e_1}= \Big\lceil\frac{q}{2}\cdot m\Big\rfloor + \underbrace{\mathbf{e}^{T}\mathbf{r} -\mathbf{s}^{T}\mathbf{e_1}+e_2}_{\text{error terms}}. \]

Fujisaki-Okamoto Transform

The last step towards Kyber’s key encapsulation construction is the application of a variant of the Fujisaki-Okamoto (FO) transform. This operation is known in literature to turn an IND-CPA secure PKE scheme into an IND-CCA2 secure KEM scheme. The IND-CCA2 level[3] ( indistinguishability under adaptive chosen ciphertext attack ) is a standard security notion in cryptography that, unlike the weaker IND-CPA, is suitable for real-world application scenarios. The most relevant effect of the FO transform can be observed during ciphertext reception. Once a ciphertext is decrypted, the corresponding plaintext is re-encrypted and compared with the one received. The purpose is to add a layer of validation to the information. If the comparison succeeds, a cryptographic key is derived, otherwise, the ciphertext is deemed invalid and rejected.

Kyber Key Encapsulation Mechanism (KEM)

 Kyber’s key generation, encapsulation and decapsulation algorithms are based on Kyber PKE’s key generation, encryption and decryption.

1. Key generation: the algorithm is essentially the same as Kyber PKE’s. The main difference is the sampling of an additional secret $z$, needed in case of decapsulation failure.
2. Encapsulation: a plaintext $m$ is uniformly sampled. The shared key $K$ is derived from $m$ and the corresponding ciphertext $c$.
3. Decapsulation: the FO transform steps are highlighted in red. Note that, in case of decapsulation failure, no error response is returned; instead, a random key derived from the additional secret $z$ is delivered. In this case, the two parties end up holding two different keys, and the decapsulation failure is only detected later, during subsequent communication. This strategy is called implicit rejection. The rationale behind this choice is to achieve stronger resistance to misuse. For instance, without a decapsulation failure check, a request could still be answered with a low-entropy default key, which this mechanism is designed to prevent.

Software Performance

Analyzing the software performance of Kyber KEM, the computational effort is distributed according to the following pie plot [6].  The most demanding part, Keccak , includes all the symmetric primitives [7]:

Instead, the NTT[9] denotes a particular transform of elements in $R_q$. \[ f = f_0 + f_1\cdot X + \cdots + f_{n-1}\cdot X^{n-1}\xmapsto[]{\textsf{NTT}} \hat{f} = \hat{f}_0 + \hat{f}_1\cdot X + \cdots +\hat{f}_{n-1}\cdot X^{n-1}. \] Thanks to NTT, the product of two elements $f$ and $g$ is given by \[ fg = \textsf{NTT}^{-1}(\hat{f}\circ\hat{g}), \] where $\hat{f}\circ\hat{g}$ is computed component-wise: \[ (\hat{f}\circ\hat{g})_i=\hat{f}_i\cdot \hat{g}_i, \] turning out to be very computationally efficient. In the context of NIST post-quantum standardization, computational efficiency played a fundamental role. In this direction, one of Kyber’s key strengths lies precisely in the efficiency gain of multiplications between elements in $R_q$, guaranteed by the application of the NTT.

[1] Sampling from $B_{\eta}$: \begin{align*} &\{(a_i,b_i)\}^{\eta}_{i=1} \longleftarrow (\{0,1\}^2)^\eta\\\text{output } & \sum_{i=1}^{\eta}(a_i-b_i)\in\{-\eta\dots,-1,0,1\dots,\eta\}.\end{align*} [2] $\lfloor\cdot\rfloor$ denotes the integer part. [3] Wikipedia page. [4] Were $\mathbf{e_1}$, $e_2$ to be zero and $\mathbf{A}$ full rank, $\mathbf{r}$ could be recovered from $\mathbf{u}$, and the message $m$ could subsequently be deduced from $v$. [5] The scheme is correct if $\text{Kyber}.\textsf{CPAPKE}.\textsf{Dec}(sk,\text{Kyber}.\textsf{CPAPKE}.\textsf{Enc}(pk,m))=m$. [6] Performance of Kyber’s reference implementation on an Intel Core i7-8665U processor. [7] Chosen according to FIPS-202 standard. [8] $\textsf{XOF}$ and $\textsf{PRF}$ are not discussed in this article and are involved in sampling steps. [9] Observe that the actual NTT implemented in Kyber is a slight variation of the one presented here for illustrative purposes.

This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The authors

Veronica Cristiano, a bachelor’s degree in Mathematics from the University of Pisa and a master’s degree in Mathematics with a specialization in Cryptography at the University of Trento, joined the Telsy Cryptography research group in mid-2021.

Francesco Stocco, a master’s degree in Mathematics at the University of Padua and the Université de Bordeaux attending the course of study “Algebra Geometry And Number Theory” (ALGANT), joined the Telsy research group in Cryptography at end of 2020 focusing in particular on issues related to quantum technologies.