Cryptography 11: From Lindner–Peikert to Kyber — Building the Module-LWE Key Encapsulation Mechanism

Posted on: July 12, 2026 | Reading time: 14 minutes | Word count: 2960 words | Author: Dang Duong Minh Nhat

Hi everyone, it take a long time from the last post to this one. Today, we will learn about the path from the Lindner–Peikert cryptosystem to Kyber, which is a post-quantum secure key encapsulation mechanism standardized by NIST in FIPS 203 under the official name ML-KEM (Module-Lattice-based KEM). To understand this post, you should have read the previous posts in this series, especially the one on Cryptography 10. Okay, let’s get started.

The Lindner–Peikert cryptosystem

Definition

For $x \in [0, q-1]$, define the symmetric modular reduction operator:

$$ x \ \text{mods } q = \begin{cases} x & \text{if } x \le (q-1)/2, \\ x - q & \text{if } x > (q-1)/2. \end{cases} $$

This naturally extends to any integer: if $z \in \mathbb{Z}$ then $z \ \text{mods } q = (z \bmod q) \ \text{mods } q$. Using this representation, we define the rounding function:

$$ \text{Round}_q(x) = \begin{cases} 0 & \text{if } -q/4 < x \ \text{mods } q < q/4, \\ 1 & \text{otherwise}. \end{cases} $$

We assume the parameters $q, n, B$ satisfy $B \le \sqrt{\dfrac{q}{4(2n+1)}}$.

Key generation

Alice picks $A \in_R \mathbb{Z}_q^{n \times n}$, $s \in_R [-B,B]^n$, $e \in_R [-B,B]^n$, and computes $b = As + e \pmod{q}$. The public key is $(A,b)$, the secret key is $s$.

Encryption

To encrypt a message $m \in \left\lbrace 0,1\right\rbrace $, Bob picks $r, z \in_R [-B,B]^n$ and $z_0 \in_R [-B,B]$. He computes $c_1 = A^T r + z$, $c_2 = b^T r + z_0 + m \left\lceil \dfrac{q}{2} \right\rfloor$, and sends the ciphertext $c = (c_1, c_2)$.

Decryption

Alice computes $m = \text{Round}_q(c_2 - s^T c_1)$.

Correctness

We have:

$$ \begin{aligned} c_2 - s^T c_1 & = (b^T r + z_0 + m\left\lceil \frac{q}{2} \right\rfloor) - s^T (A^T r + z) \\ & = (s^T A^T + e^T)r + z_0 + m\left\lceil \frac{q}{2} \right\rfloor - s^T (A^T r + z) \\ & = e^T r - s^T z + z_0 + m\left\lceil \frac{q}{2} \right\rfloor. \end{aligned} $$

We also have:

$$ \begin{aligned} \left| e^T r - s^T z + z_0 \right| & \le nB^2 + nB^2 + B \\ & \le \frac{2nq}{4(2n+1)} + \sqrt{\frac{q}{4(2n+1)}} \\ & = \frac{nq}{2(2n+1)} + \sqrt{\frac{q}{4(2n+1)}} \\ & < \frac{q}{4}. \end{aligned} $$

Case $m = 0$: since $m = \text{Round}_q(c_2 - s^T c_1) = \text{Round}_q(e^T r - s^T z + z_0)$ and $\left| e^T r - s^T z + z_0 \ \text{mods } q \right| < \dfrac{q}{4}$, decryption correctly recovers $m = 0$.
Case $m = 1$: then $m = \text{Round}_q(c_2 - s^T c_1) = \text{Round}_q \left(e^T r - s^T z + z_0 + \dfrac{q+1}{2}\right)$. Since $\left| e^T r - s^T z + z_0 \right| < \dfrac{q}{4}$, we get $\dfrac{q}{4} + \dfrac{1}{2} < e^T r - s^T z + z_0 + \dfrac{q+1}{2} < \dfrac{3q}{4} + \dfrac{1}{2}$.
- If $\dfrac{q}{4} + \dfrac{1}{2} < e^T r - s^T z + z_0 + \dfrac{q+1}{2} \le \dfrac{q-1}{2}$, the condition holds directly.
- If $\dfrac{q-1}{2} < x = e^T r - s^T z + z_0 + \dfrac{q+1}{2} < \dfrac{3q}{4} + \dfrac{1}{2}$, then $x \ \text{mods } q < -\dfrac{q}{4} + \dfrac{1}{2}$, which also holds since $x$ is an integer.

So decryption succeeds — i.e. $m = \text{Round}_q(c_2 - s^T c_1)$ recovers the right bit — exactly when $\left| e^T r - s^T z + z_0 \ \text{mods } q \right| < \dfrac{q}{4}$.

Security

This public-key encryption scheme is indistinguishable under chosen-plaintext attack, assuming the $\text{ss-DLWE}(n,n,q,B)$ problem is hard. To see this, note that encryption can be written as:

$$ \begin{bmatrix} c_1 \\ c_2 \end{bmatrix} = \begin{bmatrix} A^T \\ b^T \end{bmatrix} r + \begin{bmatrix} z \\ z_0 \end{bmatrix} + \begin{bmatrix} 0 \\ \left\lceil \frac{q}{2} \right\rfloor m \end{bmatrix}. $$

Under the hardness of ss-DLWE, the matrix

$$ \begin{bmatrix} A^T \\ b^T \end{bmatrix} $$

is computationally indistinguishable from a uniformly random matrix. Consequently,

$$ \begin{bmatrix} A^T \\ b^T \end{bmatrix} r + \begin{bmatrix} z \\ z_0 \end{bmatrix} = \begin{bmatrix} A^T r + z \\ b^T r + z_0 \end{bmatrix} $$

is also indistinguishable from a random vector. So, from an attacker’s point of view, the ciphertext component $c_2$ looks like the sum of a uniformly random element $b^T r + z_0 \in \mathbb{Z}_q$ and the plaintext $m\left\lceil \dfrac{q}{2} \right\rfloor$. Hence the attacker learns nothing about $m$.

The polynomial ring $R_q = \mathbb{Z}_q[x]/(x^n+1)$

Let $q$ be prime and $n$ a positive integer. The polynomial ring $R_q = \mathbb{Z}_q[x]/(x^n+1)$ consists of polynomials in $\mathbb{Z}_q[x]$ of degree less than $n$, where multiplication is carried out by reducing modulo $x^n+1$. To multiply two polynomials $f(x), g(x) \in R_q$: first multiply them as ordinary polynomials in $\mathbb{Z}_q[x]$, obtaining $h(x) \in \mathbb{Z}_q[x]$ of degree at most $2n-2$; then divide $h(x)$ by $x^n+1$ and take the remainder $r(x) \in \mathbb{Z}_q[x]$, of degree at most $n-1$. The product of $f(x)$ and $g(x)$ in $R_q$ is $r(x)$.

Definition

Vector representation of a polynomial. A polynomial $f(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1} \in R_q$ can be represented as a length-$n$ vector of its coefficients, $f=(a_0,a_1,\cdots,a_{n-1})$.

Polynomial multiplication as a matrix product. Polynomial multiplication can be represented as a matrix-vector product. Let $a(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1} \in R_q$, $b(x) = b_0 + b_1 x + b_2 x^2 + \cdots + b_{n-1} x^{n-1} \in R_q$, and $c(x) = a(x) \times b(x)$ in $R_q$. Then

$$ \begin{aligned} c(x) & = a(x)(b_0 + b_1 x + b_2 x^2 + \cdots + b_{n-1} x^{n-1}) \\ & = b_0 a(x) + b_1 x \cdot a(x) + b_2 x^2 \cdot a(x) + \cdots + b_{n-1} x^{n-1} \cdot a(x). \end{aligned} $$

We have:

$$ \begin{aligned} x \cdot a(x) & = a_0 x + a_1 x^2 + \cdots + a_{n-2} x^{n-1} + a_{n-1} x^n \\ & = -a_{n-1} + a_0 x + a_1 x^2 + \cdots + a_{n-2} x^{n-1} \pmod{x^n+1}. \end{aligned} $$

This corresponds to the vector $(-a_{n-1}, a_0, a_1, \ldots, a_{n-2})$ — that is, the vector of $x \cdot a(x)$ is a right cyclic shift of the vector of $a(x)$, except that the element wrapped around to the front gets negated. From this it follows that if $c(x) = a(x) \times b(x)$ in $R_q$, then

$$ \begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ \vdots \ c_{n-1} \end{bmatrix} = \underbrace{ \begin{bmatrix} a_0 & -a_{n-1} & -a_{n-2} & \cdots & -a_1 \\ a_1 & a_0 & -a_{n-1} & \cdots & -a_2 \\ a_2 & a_1 & a_0 & \cdots & -a_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n-1} & a_{n-2} & a_{n-3} & \cdots & a_0 \end{bmatrix} }_{\text{circ}(a)} \cdot \begin{bmatrix} b_0 \\ b_1 \\ b_2 \\ \vdots \\ b_{n-1} \end{bmatrix} $$

The $n \times n$ matrix above is called an anti-circulant matrix, denoted $A = \text{circ}(a)$.

Definition

Size. For an odd integer $q \ge 3$, the size of an integer $r \in \mathbb{Z}_q$ is its infinity norm, denoted $\lVert r\rVert_{\infty} = |r \ \text{mods } q|$.

Definition

The size (infinity norm) of a polynomial $f(x) = f_0+f_1x+f_2x^2+\cdots+f_{n-1}x^{n-1} \in R_q$ is $\lVert f\rVert_\infty = \max_i \lVert f_i\Vert_\infty$.

Definition

Let $\eta$ be a positive integer that is very small relative to $\dfrac{q}{2}$. The set of small polynomials in $R_q$ is $S_\eta = \left\lbrace f \in R_q \ | \ \lVert f\rVert _\infty \le \eta\right\rbrace $.

Theorem

Let $R_q = \mathbb{Z}_q[x]/(x^n+1)$ and let $\eta_1, \eta_2$ be positive integers satisfying $n\eta_1\eta_2 < \dfrac{q}{2}$. For $f \in S_{\eta_1}$ and $g \in S_{\eta_2}$, we have $fg \in S_{n\eta_1\eta_2}$.

Proof

Let $f(x) = f_0 + f_1x + \cdots + f_{n-1}x^{n-1} \in S_{\eta_1}$ and $g(x) = g_0+g_1x+ \cdots + g_{n-1}x^{n-1} \in S_{\eta_2}$. Let $h(x) = h_0 + h_1x + \cdots + h_{n-1}x^{n-1}$ be the product of $f(x)$ and $g(x)$ in $R_q$. Carrying out the multiplication and substituting $x^{n+j}=-x^j \pmod{x^n+1}$ for $0 \le j \le n-1$, we obtain $$h_i = f_0g_i + f_1g_{i-1} + \cdots + f_ig_0 - f_{i+1}g_{n-1} - f_{i+2}g_{n-2}-\cdots-f_{n-1}g_{i+1}.$$ From this, $\lVert h_i\rVert _\infty \le n\eta_1\eta_2 \Rightarrow \lVert h\rVert _\infty \le n\eta_1\eta_2$.

Module-LWE (MLWE)

A module generalizes the notion of a vector space by replacing the field of coefficients with a ring. Here, the module $R_q^k$ consists of length-$k$ vectors whose entries are each a polynomial in $R_q$. Addition and subtraction of two such vectors again yield an element of $R_q^k$, while their inner product yields a single polynomial in $R_q$. We now generalize the LWE and DLWE problems to Module Learning With Errors (MLWE) and Decisional Module Learning With Errors (D-MLWE) by replacing integers modulo $q$ with polynomials in the ring $R_q=\mathbb{Z}_q[x]/(x^n+1)$.

Definition

Module Learning With Errors, denoted $\text{MLWE}(k,l,n,q,B)$. Let $A \in_R R_q^{k \times l}$ (i.e. the columns $A_1, A_2,\cdots,A_l$ belong to the module $R_q^k$), $s \in_R R^l_q$, and $e \in_R S_B^k$, where $k>l$, $B \ll \dfrac{q}{2}$, and $R_q = \mathbb{Z}_q[x]/(x^n+1)$. Given $A$ and $t = As+e \in R_q^k$, find $s$.

Definition

Decisional Module Learning With Errors, denoted $\text{D-MLWE}(k,l,n,q,B)$. Let $A \in_R R_q^{k \times l}$, $s \in_R R^l_q$, $e \in_R S_B^k$, $r \in_R R_q^k$, and $t = As +e \in R_q^k$. Uniformly at random set $z=t$ or $z=r$, each with probability $\dfrac{1}{2}$. Given $A$ and $z$, decide whether $z=t$ or $z=r$ with probability noticeably greater than $\dfrac{1}{2}$.

In the variants of MLWE and D-MLWE, the vector $s$ is chosen to have small coefficients.

Definition

Short-secret Module Learning With Errors, denoted $\text{ss-MLWE}(k,l,n,q,\eta_1,\eta_2)$. Let $A \in_R R_q^{k \times l}$, $s \in_R S_{\eta_1}^l$, and $e \in_R S_{\eta_2}^k$, where $k \ge l$ and $\eta_1, \eta_2 \ll \dfrac{q}{2}$. Given $A$ and $t=As+e \in R_q^k$, find $s$.

Definition

Short-secret Decisional Module Learning With Errors, denoted $\text{ss-D-MLWE}(k,l,n,q,\eta_1,\eta_2)$. Let $A \in_R R_q^{k \times l}$, $s \in_R S_{\eta_1}^l$, $e \in_R S_{\eta_2}^k$, $r \in_R R_q^k$, and $t = As +e \in R_q^k$. Uniformly at random set $z=t$ or $z=r$, each with probability $\dfrac{1}{2}$. Given $A$ and $z$, decide whether $z=t$ or $z=r$ with probability noticeably greater than $\dfrac{1}{2}$.

Hardness of MLWE

No attacks against MLWE (or its decisional and short-secret variants) are currently known to be faster than attacks against plain LWE — that is, no attack has yet been found that exploits the special anti-circulant block structure of the matrix $A$.

The Kyber public-key encryption scheme

Kyber-PKE is post-quantum secure, based on the hardness of MLWE.

Notation

$R_q = \mathbb{Z}_q[x]/(x^n+1)$
$S_\eta = \left\lbrace f \in R_q \ | \ \lVert f\rVert_\infty \le \eta\right\rbrace $
$\lceil x \rfloor$ denotes the nearest integer to $x$; ties (e.g. $1.5$) round up (e.g. to $2$).
The plaintext space is $\left\lbrace 0,1\right\rbrace ^n$. A plaintext $m = (m_0,m_1,\cdots,m_{n-1}) \in \left\lbrace 0,1\right\rbrace ^n$ is mapped to the polynomial $m(x) = m_0 + m_1x+ \cdots + m_{n-1}x^{n-1} \in R_q$.

Kyber-PKE uses the same $\text{mods}$ and $\text{Round}_q(x)$ functions defined earlier for Lindner–Peikert. The function $\text{Round}_q(x)$ extends to polynomials by applying it coefficient-wise.

Example

$\text{Round}_{3329}(3000+2500x+2010x^2+37x^3)=x+x^2$

Kyber-PKE (without ciphertext compression)

Domain parameters

$q,n,k,\eta_1,\eta_2$.

Key generation

Bob performs:

Choose $A \in_R R_q^{k \times k}$, $s \in_R S_{\eta_1}^k$, and $e \in_R S_{\eta_1}^k$.
Compute $t=As+e$.
The public key is $(A,t)$; the secret key is $s$.

Encryption

Alice encrypts a message $m \in \left\lbrace 0,1\right\rbrace ^n$ by:

Obtaining Bob’s public key $(A,t)$.
Choosing $r \in_R S_{\eta_1}^k$, $e_1 \in_R S_{\eta_2}^k$, and $e_2 \in_R S_{\eta_2}$.
Computing $u=A^Tr+e_1$ and $v=t^Tr+e_2 + \lceil \dfrac{q}{2} \rfloor m$.
Returning the ciphertext $c = (u,v)$.

Decryption

To decrypt, Bob computes $m = \text{Round}_q(v-s^Tu)$.

Correctness

We have:

$$ \begin{aligned} v-s^Tu & = (t^Tr+e_2+ \lceil \dfrac{q}{2} \rfloor m) - s^T(A^Tr+e_1) \\ & = (s^TA^T+e^T)r + e_2 + \lceil \dfrac{q}{2} \rfloor m - s^T(A^Tr+e_1) \quad (\text{since } t = As+ e \Rightarrow t^T = s^TA^T + e^T) \\ & = e^Tr +e_2-s^Te_1+ \lceil \dfrac{q}{2} \rfloor m. \end{aligned} $$

Let $E(x) = e^Tr +e_2-s^Te_1$. Then:

$$ \begin{cases} e = (e^{(1)},e^{(2)},\cdots,e^{(k)}) \\ r = (r^{(1)}, r^{(2)}, \cdots, r^{(k)}) \end{cases} \Rightarrow e^Tr = e^{(1)}r^{(1)}+e^{(2)}r^{(2)}+\cdots+e^{(k)}r^{(k)}. $$

Applying the theorem from the ring section above:

$$ \begin{aligned} & \begin{cases} \lVert e^{(i)}\rVert _\infty \le \eta_1 \\ \lVert r^{(i)}\rVert _\infty \le \eta_1 \end{cases} \quad \forall i \in \left\lbrace 1, 2, \cdots, k\right\rbrace \\ \Rightarrow & \lVert e^{(i)}r^{(i)}\rVert _\infty \le n\eta_1^2 \\ \Rightarrow & \lVert (e^Tr)\rVert _\infty = \left \lVert \sum_{i=1}^k (e^{(i)}r^{(i)}) \right \rVert _\infty \le \sum_{i=1}^k \lVert (e^{(i)}r^{(i)})\rVert _\infty \ (\text{triangle inequality}) \le kn\eta_1^2\ \end{aligned} $$

Similarly, $\lVert s^Te_1\rVert _\infty \le kn\eta_1\eta_2$. Therefore:

$$ \begin{aligned} \lVert E_i\rVert _\infty & \le \max_{i \in \left\lbrace 1,\cdots,k\right\rbrace } \lVert E_i\rVert _\infty \\ & = \lVert E\rVert _\infty \\ & = \lVert e^Tr +e_2-s^Te_1\rVert _\infty \\ & \le \lVert e^Tr\rVert _\infty + \lVert e_2\rVert _\infty + \lVert s^Te_1\rVert _\infty \\ & \le kn\eta_1^2 + \eta_2 + kn\eta_1\eta_2. \end{aligned} $$

So, if $kn\eta_1^2 + \eta_2 + kn\eta_1\eta_2 < \dfrac{q}{4}$, correctness holds (this is only a sufficient, one-directional condition), as shown earlier for Lindner–Peikert. In practice, however, ML-KEM-768 with parameters $q=3329, n=256, k=3, \eta_1=2, \eta_2=2$ does not satisfy that inequality. Nevertheless, the probability that $\lVert E\rVert _\infty \ge \dfrac{q}{4}$ is only $2^{-164}$; for ML-KEM-1024, with parameters $q=3329, n=256, k=4, \eta_1=2, \eta_2=2$, that probability is $2^{-174}$ — both negligibly small failure probabilities.

Security

Theorem

Kyber-PKE is semantically secure against chosen-plaintext attack, assuming the ss-D-MLWE problem is intractable.

Proof

Encryption can be rewritten as

$$ \begin{bmatrix} u \\ v \end{bmatrix} = \begin{bmatrix} A^T \\ t^T \end{bmatrix} r + \begin{bmatrix} e_1 \\ e_2 \end{bmatrix} + \begin{bmatrix} 0 \\ \left\lceil \dfrac{q}{2} \right\rfloor m \end{bmatrix}. $$

Assuming ss-D-MLWE is hard, the matrix

$$ \begin{bmatrix} A^T \\ t^T \end{bmatrix} $$

is computationally indistinguishable from a uniformly random matrix. Under this same assumption,

$$ \begin{bmatrix} A^T \\ t^T \end{bmatrix} r + \begin{bmatrix} e_1 \\ e_2 \end{bmatrix} = \begin{bmatrix} A^T r + e_1 \\ t^T r + e_2 \end{bmatrix} $$

is also indistinguishable from random. So, from an attacker’s viewpoint, $v$ is the sum of a random polynomial $t^T r + e_2$ and the scaled message polynomial $\left\lceil \dfrac{q}{2} \right\rfloor m$. Since $u$ does not depend on $m$ either, no information about $m$ leaks. Hence the attacker learns nothing about the plaintext $m$.

Ciphertext compression

The FIPS 203 standard describes a method for compressing and decompressing Kyber-PKE ciphertexts. The approach discards the low-order bits of the coefficients across all polynomials in the ciphertext $c = (u,v)$. The compression parameters are chosen carefully so that decompression does not affect decryption.

Choose a compression parameter $1 \le d < \log_2q$. For $X \in [0,q-1]$, define the compression function

$$ \text{Compress}_q(X,d)=\left\lceil\dfrac{2^d}{q}\cdot X\right\rfloor \bmod{2^d}, $$

and for $Y \in [0,2^d-1]$, the decompression function

$$ \text{Decompress}_q(Y,d)=\left\lceil\dfrac{q}{2^d}\cdot Y\right\rfloor\bmod{q}. $$

Theorem

Decompression error. For $d \in [1,\lfloor \log_2q\rfloor]$, $X \in [0, q-1]$, $Y = \text{Compress}_q(X,d)$, and $X’ = \text{Decompress}_q(Y,d)$: $\lVert X’-X\rVert _\infty \le \left \lceil \dfrac{q}{2^{d+1}}\right\rfloor$.

The compression and decompression functions extend to polynomials in $R_q$ and vectors of polynomials in $R_q^k$ by applying them coefficient-wise.

The Kyber key encapsulation mechanism

Kyber-KEM is a post-quantum secure key encapsulation mechanism, standardized by NIST in FIPS 203 under the official name ML-KEM (Module-Lattice-based KEM). Kyber-KEM is built by applying a variant of the Fujisaki–Okamoto (FO) transform to Kyber-PKE — a general technique for converting a chosen-plaintext-secure scheme into a chosen-ciphertext-secure one.

Domain parameters

Kyber-PKE: $q,n=256,k,\eta_1,\eta_2$
Hash functions:
- $G:\left\lbrace 0,1\right\rbrace ^* \rightarrow \left\lbrace 0,1\right\rbrace ^{2n}$
- $H:\left\lbrace 0,1\right\rbrace ^* \rightarrow \left\lbrace 0,1\right\rbrace ^{n}$
- $J:\left\lbrace 0,1\right\rbrace ^* \rightarrow \left\lbrace 0,1\right\rbrace ^{n}$

These three hash functions are built from SHA3 and SHAKE256.

Key generation

Bob performs:

Generate a Kyber-PKE key pair: encryption key $(A,t)$ and decryption key $s$.
Choose $z \in_R \left\lbrace 0,1\right\rbrace ^{256}$ at random.
Publish encapsulation (public) key $ek=(A,t)$ and keep decapsulation (private) key $dk = (s,ek,H(ek),z)$.

Encapsulation

To establish an $n$-bit shared secret key with Bob, Alice performs:

Obtain the encapsulation key $ek$ from Bob.
Choose $m \in_R \left\lbrace 0,1\right\rbrace ^{256}$ at random.
Compute $h=H(ek)$ and $(K,R) = G(m,h)$, with $K,R \in \left\lbrace 0,1\right\rbrace ^{256}$.
Encrypt $m$ under Kyber-PKE using $ek$, using $R$ as a seed to deterministically derive $e_1,e_2,r$ (rather than sampling them freshly at random), producing ciphertext $c$.
Send $c$ to Bob and set $K$ as the shared secret key.

Decapsulation

To recover $K$ from $c$, Bob performs:

Decrypt $c$ using Kyber-PKE decryption with secret key $s$, obtaining $m’$.
Compute $(K’,R’) = G(m’,H(ek))$.
Compute $\overline{K} = J(z,c)$.
Re-encrypt $m’$ under Kyber-PKE using $ek$, deriving $e_1,e_2,r$ from $R’$, producing $c’$.
If $c \ne c’$, return $\overline{K}$.
Otherwise, return $K$.

So, if $c = c’$, Bob accepts $K$ as the shared secret key. If not, Bob instead produces a pseudorandom key $\overline{K}$ by hashing $c$ together with the secret value $z$. Decapsulation therefore “fails” — in the sense of producing a mismatched key — exactly when $c \ne c’$, which can still occur between two honest parties due to the (extremely small) probability that Kyber-PKE decryption is incorrect, i.e. $m \ne m’$. Under the parameters specified in FIPS 203, this failure probability is negligible.

Security

Kyber-KEM has been proven IND-CCA secure against chosen-ciphertext attack, assuming the D-MLWE problem is hard and that $G, H, J$ behave as random oracles. It is additionally secure against quantum adversaries.

Plaintext awareness

The idea behind the FO transform is that Kyber-KEM has the plaintext-awareness property: decapsulation returns the “correct” key $K$ only if the party performing encapsulation actually knew $K$. If an attacker already knows $K$, the attack yields no new information; if the attacker does not know $K$, Bob will (with overwhelming probability) return a key different from $K$, so the attacker gains no useful information either way.

From a simple encryption scheme over $\mathbb{Z}_q^n$ to ML-KEM — NIST’s official post-quantum key-encapsulation standard — we can trace a single consistent thread: every refinement along the way (moving to a polynomial ring, generalizing to modules, applying the FO transform) is aimed at resolving a concrete tradeoff between performance and provable security. The structure “the LWE matrix looks random under a decisional assumption” runs from Lindner–Peikert all the way to Kyber, illustrating the power of proving security through a sequence of computationally indistinguishable distributions.

References

Alfred Menezes. (2025, April 30). A Gentle Introduction to Lattice-Based Cryptography. Retrieved from https://drive.google.com/file/d/1-G9qYuQhuHr0W4-YglVGub1PxdLyFHC6/view
Alfred Menezes. Textbook of Applied Cryptography. Retrieved from https://drive.google.com/file/d/1xGAODc0PyMvH65spbGBCW-Xgkbe0leif/view

Connect with Me

Connect with me on Facebook, LinkedIn, via email at dangduongminhnhat2003@gmail.com, GitHub, or by phone at +84 829 258 815.