Exercise - Manual Kyber Computation

Exercise Solution: Manual Kyber Computation

Given:

• $q = 17$, $A = \begin{bmatrix} 3 & 5 \\ 7 & 2 \end{bmatrix}$, $s = \begin{bmatrix} 2 \\ 1 \end{bmatrix}$, $e = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$
• $r = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$, $m = 1$, $e_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$, $e_2 = 1$

Step 1: Public Key $t = As + e \pmod{17}$

Compute $As$:

$As = \begin{bmatrix} 3 & 5 \\ 7 & 2 \end{bmatrix} \begin{bmatrix} 2 \\ 1 \end{bmatrix} = \begin{bmatrix} (3)(2) + (5)(1) \\ (7)(2) + (2)(1) \end{bmatrix} = \begin{bmatrix} 6 + 5 \\ 14 + 2 \end{bmatrix} = \begin{bmatrix} 11 \\ 16 \end{bmatrix}$

Add noise $e$:

$t = As + e = \begin{bmatrix} 11 \\ 16 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 12 \\ 17 \end{bmatrix} \pmod{17} = \begin{bmatrix} 12 \\ 0 \end{bmatrix}$

$\boxed{t = \begin{bmatrix} 12 \\ 0 \end{bmatrix}}$

Public key is $pk = (A, t)$. Bob keeps $sk = s = [2, 1]^T$ secret.

Step 2a: Ciphertext $u = A^T r + e_1 \pmod{17}$

First, compute $A^T$:
$A^T = \begin{bmatrix} 3 & 7 \\ 5 & 2 \end{bmatrix}$

Compute $A^T r$:
$A^T r = \begin{bmatrix} 3 & 7 \\ 5 & 2 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \end{bmatrix} = \begin{bmatrix} (3)(1) + (7)(2) \\ (5)(1) + (2)(2) \end{bmatrix} = \begin{bmatrix} 3 + 14 \\ 5 + 4 \end{bmatrix} = \begin{bmatrix} 17 \\ 9 \end{bmatrix}$

Add noise $e_1$:
$u = A^T r + e_1 = \begin{bmatrix} 17 \\ 9 \end{bmatrix} + \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 18 \\ 9 \end{bmatrix} \pmod{17} = \begin{bmatrix} 1 \\ 9 \end{bmatrix}$

$\boxed{u = \begin{bmatrix} 1 \\ 9 \end{bmatrix}}$

Step 2b: Ciphertext $v = t^T r + e_2 + \lfloor q/2 \rfloor \cdot m \pmod{17}$

Compute $\lfloor q/2 \rfloor$:
$\left\lfloor \frac{17}{2} \right\rfloor = \lfloor 8.5 \rfloor = 8$
Compute $t^T r$:
$t^T r = \begin{bmatrix} 12 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \end{bmatrix} = (12)(1) + (0)(2) = 12$
Add $e_2$ and message encoding $\lfloor q/2 \rfloor \cdot m$:
$v = 12 + 1 + 8 \cdot 1 = 12 + 1 + 8 = 21 \pmod{17} = 4$

$\boxed{v = 4}$

Note: $m = 1$ is encoded as $\lfloor q/2 \rfloor = 8$ so it sits roughly in the "upper half" of $\mathbb{Z}_q$. If $m = 0$ it adds nothing. This is how a single bit is hidden inside the ciphertext.

Step 3: Bob Computes $v - s^T u \pmod{17}$

Compute $s^T u$:

$s^T u = \begin{bmatrix} 2 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 9 \end{bmatrix} = (2)(1) + (1)(9) = 2 + 9 = 11$

Subtract from $v$:

$v - s^T u = 4 - 11 = -7 \pmod{17} = 10$

$\boxed{v - s^T u = 10}$

Why does this work? Expanding the math:v - s^T u = (t^T r + e_2 + \lfloor q/2 \rfloor m) - s^T(A^T r + e_1)$$$$= t^T r - s^T A^T r + e_2 - s^T e_1 + \lfloor q/2 \rfloor m

Since $t = As + e$, we have $t^T = s^T A^T + e^T$, so $t^T r - s^T A^T r = e^T r$ (small noise).
The result is approximately $\lfloor q/2 \rfloor \cdot m$ plus small noise terms.

Step 4: Recover $m$

We got $v - s^T u = 10$.

Now check: is $10$ closer to $0$ or to $\lfloor q/2 \rfloor = 8$?

Since $10$ is closer to $8$ (which represents $m = 1$) than to $0$ (which represents $m = 0$):

$\boxed{m = 1} \quad \checkmark$

Decoding rule:

• If result is close to $0$ → $m = 0$
• If result is close to $\lfloor q/2 \rfloor = 8$ → $m = 1$

The threshold is at $q/4 \approx 4.25$. Values in $[0, 4]$ decode to $0$; values in $[5, 12]$ decode to $1$; and so on (wrapping around mod $q$).

The noise terms ($e^T r - s^T e_1$) were small enough not to push us past the threshold — that's the whole design!

Step 5: Shared Key $K = H(m)$

Both Alice and Bob recovered the same $m = 1$, so they compute:

$\boxed{K = H(1)}$

In real Kyber, $H$ = SHA3-256 (or SHAKE-256 for the final KDF):

$K = \text{SHAKE256}(K' \| H(c))$

In this toy example with $m = 1$:

$K = H(1) = \text{SHA3-256}(1) = \texttt{67...} \text{ (some 256-bit value)}$

Both parties now share the same secret key $K$, which is used for symmetric encryption:

$C = \text{AES-GCM}(K, \text{message})$

Full Solution Summary