Chapter 10: Regev encryption from scratch

Regev encryption hides a message bit inside LWE noise. The public key is an LWE sample $(A, b = A s + e)$. A ciphertext is a random $\{0, 1\}$-linear combination of the rows of this sample. The sender adds $\lfloor q/2 \rfloor \mu$ to the second coordinate to carry the bit $\mu$. Decryption computes $c_2 - c_1^\top s$ modulo $q$, which cancels the secret and leaves $\lfloor q/2 \rfloor \mu + e^\top r$. Rounding the result to the nearer of $0$ or $\lfloor q/2 \rfloor$ recovers $\mu$ whenever the noise stays inside the window the decoder tolerates.

For correctness, the noise budget is the entire story. Security adds two more pieces: the public-key indistinguishability from uniform under decisional LWE, and the leftover hash lemma applied to the joint hash $r \mapsto [A \,\|\, u]^\top r$.

A bit hidden in LWE noise

The toy parameters are $(n, q, m, B) = (4, 97, 8, 1)$, matching Chapter 8. Key generation draws a uniform secret $s \in \mathbb{Z}_{97}^4$ and a uniform matrix $A \in \mathbb{Z}_{97}^{8 \times 4}$. It also draws an error vector $e \in \{-1, 0, 1\}^8$ and sets $b = A s + e$ in $\mathbb{Z}_{97}^8$. The public key is the LWE sample $(A, b)$ and the secret key is $s$ (Regev, 2009).

Seeding numpy’s default generator at $0$ fixes a specific instance. The secret is $s = (82, 61, 49, 26)$. The error in symmetric representatives is $e = (-1, -1, 0, 0, 0, -1, -1, -1)$. Every coordinate of $e$ is at most $1$ in absolute value.

To encrypt the bit $\mu = 1$, the sender draws a random $r \in \{0, 1\}^8$. The ciphertext is $(c_1, c_2) = (A^\top r, b^\top r + 48) \bmod 97$. The shift $48 = \lfloor 97 / 2 \rfloor$ is the encoding of the bit $1$. At the same seed the draw is $r = (0, 1, 1, 1, 0, 1, 1, 0)$, and the ciphertext is $c_1 = (44, 50, 54, 74)$ with $c_2 = 21$.

Decryption uses the secret $s$ to compute $c_2 - c_1^\top s \bmod 97$. The result is $45$. In symmetric representatives this is distance $3$ from $48$, so it rounds to $48$ and decodes to the bit $1$. The noise did not flip the decoded bit because $|e^\top r| = 3$, and the decoder tolerates any $|e^\top r|$ up to $23$ at these parameters.

The same $r$ with the bit $\mu = 0$ gives $c_2 = 70$ instead of $21$, because the encoding shift drops from $48$ to $0$. The decrypted value is $c_2 - c_1^\top s = 94 \bmod 97$, which in symmetric representatives is $-3$. That rounds to $0$ and decodes to $0$. The distance from $-3$ to $0$ and the distance from $45$ to $48$ are both the same quantity $|e^\top r| = 3$.

A numpy block reproduces the walkthrough end to end.

import numpy as np

n, q, m, B = 4, 97, 8, 1
rng = np.random.default_rng(seed=0)
s = rng.integers(0, q, size=n, dtype=np.int64)
A = rng.integers(0, q, size=(m, n), dtype=np.int64)
e = rng.integers(-B, B + 1, size=m, dtype=np.int64)
b = (A @ s + e) % q
r = rng.integers(0, 2, size=m, dtype=np.int64)
half_q = q // 2

c1 = (A.T @ r) % q
c2_one = (int(b @ r) + half_q * 1) % q
c2_zero = (int(b @ r) + half_q * 0) % q
v_one = (c2_one - int(c1 @ s)) % q
v_zero = (c2_zero - int(c1 @ s)) % q

print("s =", s.tolist())
print("r =", r.tolist())
print("c1 =", c1.tolist())
print("c2 for mu=1:", c2_one, "c2 for mu=0:", c2_zero)
print("v for mu=1:", v_one, "v for mu=0:", v_zero)
# ==> s = [82, 61, 49, 26]
# ==> r = [0, 1, 1, 1, 0, 1, 1, 0]
# ==> c1 = [44, 50, 54, 74]
# ==> c2 for mu=1: 21 c2 for mu=0: 70
# ==> v for mu=1: 45 v for mu=0: 94

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch10/, one file per block. Appendix C covers the clone and the environment they run on.

Noise budget and symmetric representatives

Two notational conventions carry through the rest of the chapter. The first is symmetric representatives on $\mathbb{Z}_q$: every residue $v \in \{0, 1, \ldots, q - 1\}$ is mapped to the signed integer in the half-open interval $(-q/2, q/2]$ that shares its residue class. For odd $q$, this is the integer closest to $0$. For $q = 97$, the values $0, 1, \ldots, 48$ map to themselves, and the values $49, 50, \ldots, 96$ map to $-48, -47, \ldots, -1$. The symmetric representative of $94$ is $-3$; the symmetric representative of $45$ is $45$.

The second convention is the nearest-codeword decoder for the two encodings $0$ and $\lfloor q/2 \rfloor$. Given $v \in \mathbb{Z}_q$, the decoder asks which of $0$ and $\lfloor q/2 \rfloor$ is closer to $v$ on the cycle $\mathbb{Z}_q$. The integer expression $\lfloor (2 v + \lfloor q/2 \rfloor) / q \rfloor \bmod 2$ gives the same answer without any floating-point arithmetic. For $q = 97$ the decoder returns $0$ on the $49$ residues $\{0, \ldots, 24\} \cup \{73, \ldots, 96\}$ and $1$ on the $48$ residues $\{25, \ldots, 72\}$. The two regions have different widths because $q$ is odd, and the decoder breaks the midpoint tie toward the bit $0$. A ciphertext decodes correctly if and only if the decrypted value $v = c_2 - c_1^\top s \bmod q$ lands inside the region that contains its encoded value.

Figure 10.1. The Regev noise budget on $\mathbb{Z}_{97}$ in symmetric representatives. The bit-0 decoding region (blue, 49 residues) surrounds 0; the bit-1 region (amber, 48 residues) surrounds 48 and wraps around the cycle. Two honest ciphertexts land inside their respective regions: $v = -3$ decodes to 0 and $v = 45$ decodes to 1.

Interactive demo

An interactive version of this figure is at the Regev noise-budget demo. Slide the error bound $B$ and sample count $m$, scrub the noise inner product $e^\top r$, and toggle $q = 97$ against $q = 13$. While the budget $2 m B < \lfloor q/2 \rfloor$ holds, no honest ciphertext decodes wrongly. Past it the guarantee is gone, and a large enough realized $e^\top r$ carries the decoded point across the boundary and flips the bit.

The elementary noise bound is

$$|e^\top r| \leq \sum_{i \,:\, r_i = 1} |e_i| \leq m \cdot B,$$

for $r \in \{0, 1\}^m$ and $\|e\|_\infty \leq B$. The worst case is achieved when every coordinate of $r$ is $1$ and every coordinate of $e$ is $\pm B$.

Chapter 8’s note “Which error distribution” sets the toy’s bounded uniform error beside $\bar\Psi_\alpha$, the rounded Gaussian of width about $\alpha q$ that Regev’s theorem uses, and says why the two are not interchangeable inside a reduction (Regev, 2009). This chapter adds a difference in correctness. For bounded uniform errors with $|e_i| \leq B$, the typical $|e^\top r|$ scales as $O(B \sqrt{m})$ by sub-Gaussian concentration; for Regev’s Gaussian-shaped error distribution, the analogous scale is $O(\alpha q \sqrt{m})$.

The bounded-uniform typical size sits a factor of $\sqrt{m}$ below the deterministic worst case $m B$. The Gaussian error has no deterministic bound at all, which is why Regev’s correctness statement is a probability rather than an inequality. The uniform worst-case bound $m B$ is what the walkthrough code uses, and it suffices for decryption correctness at the toy parameters.

Key generation, encryption, decryption

Key generation, encryption, and decryption all live inside $\mathbb{Z}_q$. They use only matrix-vector multiplication, modular reduction, and the nearest-codeword decoder for the two encodings $0$ and $\lfloor q/2 \rfloor$. The blocks below pass the parameters $(n, q, m, B)$ around as loose integers so that each one runs on its own. The regev_pke package under solutions/ch10-regev-pke carries them in a RegevParams dataclass instead, with the noise budget exposed as a method on it.

Key generation. KeyGen takes the parameters $(n, q, m, B)$ and returns a public key $\text{pk} = (A, b)$ together with a secret key $\text{sk} = s$. The secret $s$ is drawn uniformly from $\mathbb{Z}_q^n$. The matrix $A$ is drawn uniformly from $\mathbb{Z}_q^{m \times n}$. The error $e$ is drawn uniformly from $\{-B, \ldots, B\}^m$. The public vector is $b = A s + e$ in $\mathbb{Z}_q^m$. The public key is the LWE sample $(A, b)$, and for the same error distribution $\chi$ it is computationally indistinguishable from uniform under decisional LWE from Chapter 8 (Regev, 2009).

import numpy as np

def keygen(n, q, m, B, rng):
    s = rng.integers(0, q, size=n, dtype=np.int64)
    A = rng.integers(0, q, size=(m, n), dtype=np.int64)
    e = rng.integers(-B, B + 1, size=m, dtype=np.int64)
    b = (A @ s + e) % q
    return (A, b), s

rng = np.random.default_rng(seed=0)
(A, b), s = keygen(4, 97, 8, 1, rng)

# Recompute A @ s with an explicit Python loop and verify that
# b - A s lives in the symmetric interval [-1, 1], which is the
# noise bound B = 1 set by the parameters.
As_loop = [sum(int(A[i, j]) * int(s[j]) for j in range(4)) % 97
           for i in range(8)]
residual = [(int(b[i]) - As_loop[i]) % 97 for i in range(8)]
e_sym = [v - 97 if v > 48 else v for v in residual]
print("s =", s.tolist())
print("b - A s (symmetric) =", e_sym)
# ==> s = [82, 61, 49, 26]
# ==> b - A s (symmetric) = [-1, -1, 0, 0, 0, -1, -1, -1]

Encryption. Encrypt takes the public key $(A, b)$ and a message bit $\mu \in \{0, 1\}$ and returns a ciphertext $(c_1, c_2)$. The sender draws a random $r \in \{0, 1\}^m$. The first coordinate is $c_1 = A^\top r \bmod q$. The second coordinate is $c_2 = b^\top r + \lfloor q/2 \rfloor \mu \bmod q$. The ciphertext lives in $\mathbb{Z}_q^n \times \mathbb{Z}_q$.

import numpy as np

def encrypt(A, b, bit, q, rng):
    m = b.shape[0]
    r = rng.integers(0, 2, size=m, dtype=np.int64)
    half_q = q // 2
    c1 = (A.T @ r) % q
    c2 = (int(b @ r) + half_q * bit) % q
    return c1, int(c2)

# Replay the seeded keygen so this block is self-contained.
rng = np.random.default_rng(seed=0)
n, q, m, B = 4, 97, 8, 1
s = rng.integers(0, q, size=n, dtype=np.int64)
A = rng.integers(0, q, size=(m, n), dtype=np.int64)
e = rng.integers(-B, B + 1, size=m, dtype=np.int64)
b = (A @ s + e) % q

c1_one, c2_one = encrypt(A, b, 1, q, rng)
print("mu = 1: c1 =", c1_one.tolist(), "c2 =", c2_one)
# ==> mu = 1: c1 = [44, 50, 54, 74] c2 = 21

Decryption. Decrypt takes the secret key $s$ and a ciphertext $(c_1, c_2)$ and returns the decoded bit. It computes $v = (c_2 - c_1^\top s) \bmod q$ and returns $\lfloor (2 v + \lfloor q/2 \rfloor) / q \rfloor \bmod 2$. The expression is the nearest-codeword decoder for $\{0, \lfloor q/2 \rfloor\}$ applied to $v$.

import numpy as np

def decrypt(s, c1, c2, q):
    v = (int(c2) - int(c1 @ s)) % q
    half_q = q // 2
    return ((2 * v + half_q) // q) % 2

# Replay keygen and produce ciphertexts for both message bits with
# the same random r, so the only difference is the encoding shift.
rng = np.random.default_rng(seed=0)
n, q, m, B = 4, 97, 8, 1
s = rng.integers(0, q, size=n, dtype=np.int64)
A = rng.integers(0, q, size=(m, n), dtype=np.int64)
e = rng.integers(-B, B + 1, size=m, dtype=np.int64)
b = (A @ s + e) % q
r = rng.integers(0, 2, size=m, dtype=np.int64)
c1 = (A.T @ r) % q
c2_one = (int(b @ r) + (q // 2) * 1) % q
c2_zero = (int(b @ r) + (q // 2) * 0) % q

print("decrypt mu = 1 ->", decrypt(s, c1, c2_one, q))
print("decrypt mu = 0 ->", decrypt(s, c1, c2_zero, q))
# ==> decrypt mu = 1 -> 1
# ==> decrypt mu = 0 -> 0

The secret-cancellation identity. Start from the definitions $c_1 = A^\top r \bmod q$ and $c_2 = b^\top r + \lfloor q/2 \rfloor \mu \bmod q$. Substituting $b = A s + e$ and expanding gives

$$c_2 - c_1^\top s = (A s + e)^\top r + \lfloor q/2 \rfloor \mu - (A^\top r)^\top s.$$

The expansion $(A s + e)^\top r = (A s)^\top r + e^\top r = r^\top A s + e^\top r$ uses distributivity and the matrix transpose identity. The subtracted term $(A^\top r)^\top s$ equals $r^\top A s$ by the same identity. Cancelling the two $r^\top A s$ summands leaves

$$c_2 - c_1^\top s \equiv \lfloor q/2 \rfloor \mu + e^\top r \pmod q.$$

The decryption input is therefore the encoded bit plus a small noise term, viewed modulo $q$. The multiple of $q$ vanishes in $\mathbb{Z}_q$ before the decoder runs.

The noise budget. The decoder returns $\mu$ correctly whenever $\lfloor q/2 \rfloor \mu + e^\top r$ lies inside the decoding region of the intended codeword. The two regions are separated by $\lfloor q/2 \rfloor$ on the cycle, and because $q$ is odd they are not perfectly symmetric. For $q \equiv 1 \pmod 4$, as at $97$ and $13$, the bit-$0$ region contains $\lceil q/2 \rceil$ residues and the bit-$1$ region contains $\lfloor q/2 \rfloor$; for $q \equiv 3 \pmod 4$ the counts swap. A clean symmetric sufficient condition that works for both message bits and both signs of the noise is

$$2 \, |e^\top r| < \lfloor q/2 \rfloor.$$

For large $q$ the right side is essentially $q/2$, and the condition is often written in the asymptotic form $|e^\top r| < q/4$. For $q = 97$ the symmetric form gives $|e^\top r| \leq 23$. The actual decoder boundary differs by at most one residue depending on the sign of the noise and the message bit. The symmetric form is the worst-case correctness condition used in the rest of this chapter.

The elementary bound gives $|e^\top r| \leq m \cdot B$ for $r \in \{0, 1\}^m$ and $\|e\|_\infty \leq B$. Combining the two inequalities produces the bounded-uniform correctness budget

$$2 \, m B < \lfloor q/2 \rfloor,$$

which is sufficient for every honest encryption to decrypt correctly. Regev’s original paper states correctness probabilistically through the distribution of sums of errors $\chi^{*k}$ rather than through a deterministic worst-case bound (Regev, 2009). The deterministic form above is the bounded-uniform analogue used by the toy code in this chapter.

At the toy parameters $(n, q, m, B) = (4, 97, 8, 1)$ the left side is $16$ and the right side is $48$, so the budget has a factor-of-three margin. At the parameters $(n, q, m, B) = (4, 13, 8, 1)$ the left side is still $16$ but the right side is $6$, so the budget is violated. The exact distribution of $e^\top r$ at those parameters predicts a failure rate of about $5\%$. The code block below shows an empirical rate of $6.75\%$ across $200$ seeds with both message bits encrypted. A sample of $200$ seeds is small for a $5\%$-rate event, so the empirical and analytical rates differ within typical sample-size variance.

import numpy as np

def keygen(n, q, m, B, rng):
    s = rng.integers(0, q, size=n, dtype=np.int64)
    A = rng.integers(0, q, size=(m, n), dtype=np.int64)
    e = rng.integers(-B, B + 1, size=m, dtype=np.int64)
    return (A, (A @ s + e) % q), s

def encrypt(A, b, bit, q, rng):
    m = b.shape[0]
    r = rng.integers(0, 2, size=m, dtype=np.int64)
    half_q = q // 2
    return (A.T @ r) % q, (int(b @ r) + half_q * bit) % q

def decrypt(s, c1, c2, q):
    v = (int(c2) - int(c1 @ s)) % q
    half_q = q // 2
    return ((2 * v + half_q) // q) % 2

def failure_rate(n, q, m, B, num_seeds):
    failures = 0
    for seed in range(num_seeds):
        rng = np.random.default_rng(seed=seed)
        (A, b), s = keygen(n, q, m, B, rng)
        for bit in (0, 1):
            c1, c2 = encrypt(A, b, bit, q, rng)
            if decrypt(s, c1, c2, q) != bit:
                failures += 1
    return failures / (2 * num_seeds)

print("feasible   (n=4, q=97, m=8, B=1):", failure_rate(4, 97, 8, 1, 200))
print("infeasible (n=4, q=13, m=8, B=1):", failure_rate(4, 13, 8, 1, 200))
# ==> feasible   (n=4, q=97, m=8, B=1): 0.0
# ==> infeasible (n=4, q=13, m=8, B=1): 0.0675

The Ring-LWE / LPR-style descendant. Replacing the flat LWE sample $(A, b)$ with a Ring-LWE sample $(a, b)$ in $R_q \times R_q$ keeps the same cancellation idea but changes the shape of the ciphertext. The construction is no longer literally Regev. Instead of a random $\{0, 1\}$-subset sum of many flat LWE samples, it works over $R_q$ with short polynomial secrets and adds fresh encryption errors $e_1, e_2 \in R_q$.

The public key is a single polynomial $a \in R_q$ together with $b = a \cdot s + e$ in $R_q$. Encryption draws a random short polynomial $r$ and the two fresh short errors $e_1, e_2$. The ciphertext is $(c_1, c_2) = (a \cdot r + e_1, b \cdot r + e_2 + \lfloor q/2 \rfloor \mathbf{m})$. The message polynomial $\mathbf{m} \in R_q$ encodes up to $n$ bits as coefficients in $\{0, 1\}$. Decryption computes $c_2 - c_1 \cdot s = \lfloor q/2 \rfloor \mathbf{m} + e \cdot r + e_2 - e_1 \cdot s$, and the noise term is now two small polynomial products plus the fresh error $e_2$. This two-element scheme is the one the journal version of the Ring-LWE paper presents. The conference version’s example cryptosystem is the dual-style scheme with about $\log q + 1$ ring elements per ciphertext (Lyubashevsky et al., 2013, sec. 1). Chapter 11 walks the Module-LWE refinement that ML-KEM uses and the Fujisaki-Okamoto transform that FIPS 203 applies to its component PKE, yielding a KEM that §3.2 says is believed to satisfy IND-CCA2 security (National Institute of Standards and Technology, 2024).

IND-CPA from decisional LWE

In the IND-CPA game, the adversary receives the public key, submits two equal-length messages $\mu_0$ and $\mu_1$ of its choice, receives an encryption of $\mu_\beta$ for a uniformly random bit $\beta$, and must guess $\beta$. The scheme is IND-CPA secure if every polynomial-time adversary guesses correctly with probability at most $1/2 + \text{negl}(\lambda)$, where $\lambda$ is the security parameter (Boneh & Shoup, 2023). For Regev PKE the two messages are the bit $0$ and the bit $1$, so the game reduces to: given $(A, b)$ and an encryption of a random bit $\mu$, guess $\mu$.

Security reduces to decisional LWE (DLWE) through a hybrid argument over three games, each changing one thing in the adversary’s view. Write $\text{Adv}_i$ for the adversary’s advantage in Hybrid $i$.

Hybrid	Public key	Challenge ciphertext	Reached by
0	$b = A s + e$	$(A^\top r,\ b^\top r + \lfloor q/2 \rfloor \mu)$	the real scheme
1	$u$ uniform in $\mathbb{Z}_q^m$	$(A^\top r,\ u^\top r + \lfloor q/2 \rfloor \mu)$	decisional LWE
2	$u$ uniform in $\mathbb{Z}_q^m$	uniform in $\mathbb{Z}_q^n \times \mathbb{Z}_q$	the leftover hash lemma

Hybrid 0 to Hybrid 1. A distinguisher $D$ for the two hybrids gives a DLWE distinguisher. On input $(A, y)$ with $y$ either $A s + e$ or uniform in $\mathbb{Z}_q^m$, $D$ installs $(A, y)$ as the public key. It then samples the IND-CPA challenge bit $\beta$ itself, forms the challenge ciphertext using $y$ (encryption does not need the secret), gives the ciphertext to the adversary, and outputs $1$ iff the adversary’s final guess equals $\beta$. If $y = A s + e$ the simulation is exactly Hybrid 0; if $y$ is uniform it is Hybrid 1. Any non-negligible gap in the adversary’s success probability between the two hybrids therefore gives a DLWE distinguisher with the same advantage, which Chapter 8 assumes is negligible (Regev, 2009).

Hybrid 1 to Hybrid 2. The adversary’s advantage in Hybrid 2 is exactly zero, because a challenge ciphertext drawn uniformly and independently of $\mu$ carries no information about $\mu$. The adversary’s view in Hybrid 1 is $(A, u, c_1, c_2) = (A, u, A^\top r, u^\top r + \lfloor q/2 \rfloor \mu)$, with $r$ uniform in $\{0, 1\}^m$. Apply the leftover hash lemma to the joint hash $r \mapsto [A \,\|\, u]^\top r \in \mathbb{Z}_q^{n+1}$. For uniform $A \in \mathbb{Z}_q^{m \times n}$ and uniform $u \in \mathbb{Z}_q^m$, the joint output is $\epsilon$-close to uniform on $\mathbb{Z}_q^{n+1}$ when $m \geq (n + 1) \log_2 q + 2 \log_2 (1/\epsilon)$ (Boneh & Shoup, 2023; Regev, 2009). The shift by $\lfloor q/2 \rfloor \mu$ preserves uniformity, so the Hybrid 1 view is $\epsilon$-close to the Hybrid 2 view and the advantage gap $|\text{Adv}_1 - \text{Adv}_2|$ is at most $\epsilon$.

Chaining the Hybrid 0 to Hybrid 1 to Hybrid 2 transitions bounds the real-world advantage: $\text{Adv}_0 \leq \text{Adv}_\text{DLWE} + \epsilon_\text{LHL}$, where $\text{Adv}_\text{DLWE}$ is the distinguishing advantage against decisional LWE and $\epsilon_\text{LHL}$ is the leftover hash lemma statistical distance. Both are negligible in $\lambda$ under the standard Regev parameterization, so the scheme is IND-CPA secure (Boneh & Shoup, 2023; Regev, 2009).

The toy parameters are not secure

$(n, q, m) = (4, 97, 8)$ does not satisfy the leftover hash lemma bound: $(n + 1) \log_2 q \approx 33$, far above $m = 8$. The toy is kept small only so the walkthrough fits on a page. The asymptotic security statement requires $m$ to grow with $n \log q$.

Recovering the encryption randomness. At $m = 8$ the randomness $r$ takes only $2^8 = 256$ values, so an eavesdropper who holds the public key can try them all. It computes $A^\top r$ for each candidate and looks for $c_1$ among the images. When only one candidate matches, it is the sender’s $r$, and then $c_2 - b^\top r \equiv \lfloor q/2 \rfloor \mu \pmod q$ with no noise left. The bit comes out without the secret, without a decryption oracle and without solving LWE. The block below runs the attack on the 200 seeded keys that the failure-rate block above uses at $q = 97$, with both bits encrypted under each.

import itertools
import numpy as np

def keygen(n, q, m, B, rng):
    s = rng.integers(0, q, size=n, dtype=np.int64)
    A = rng.integers(0, q, size=(m, n), dtype=np.int64)
    e = rng.integers(-B, B + 1, size=m, dtype=np.int64)
    return (A, (A @ s + e) % q), s

def encrypt(A, b, bit, q, rng):
    m = b.shape[0]
    r = rng.integers(0, 2, size=m, dtype=np.int64)
    half_q = q // 2
    return (A.T @ r) % q, (int(b @ r) + half_q * bit) % q

# The eavesdropper holds the public key (A, b) and a ciphertext
# (c1, c2), never s. It tabulates A^T r for all 2^m choices of r.
n, q, m, B = 4, 97, 8, 1
cube = np.array(list(itertools.product((0, 1), repeat=m)), dtype=np.int64)
one_to_one, recovered, shifts = 0, 0, set()
for seed in range(200):
    rng = np.random.default_rng(seed=seed)
    (A, b), _ = keygen(n, q, m, B, rng)
    table = {tuple(((A.T @ r) % q).tolist()): r for r in cube}
    one_to_one += len(table) == len(cube)
    for bit in (0, 1):
        c1, c2 = encrypt(A, b, bit, q, rng)
        r = table[tuple(c1.tolist())]
        shift = (c2 - int(b @ r)) % q
        shifts.add(shift)
        recovered += int(shift == q // 2) == bit

print("keys where r -> A^T r is one to one:", one_to_one, "of 200")
print("values of c2 - b^T r:", sorted(shifts))
print("bits recovered without s:", recovered, "of 400")
# ==> keys where r -> A^T r is one to one: 200 of 200
# ==> values of c2 - b^T r: [0, 48]
# ==> bits recovered without s: 400 of 400

In each of these keys the map $r \mapsto A^\top r$ is one to one on $\{0, 1\}^8$, so the match is unique and every bit comes back. That is a fact about these 200 matrices, not about every matrix: a zero row in $A$ already gives two choices of $r$ the same image. For a fixed $r$ and a uniform $A$, another $r' \in \{0, 1\}^8$ has the same image exactly when $A^\top (r - r') = 0$. That happens with probability $97^{-4}$, because $r - r'$ has an entry $\pm 1$, which makes $A^\top (r - r')$ uniform. A union bound over the $255$ other choices puts the chance that one of them shares the sender’s image at most $255/97^4 \approx 2.9 \times 10^{-6}$. That is the chance that the match on one ciphertext is not unique.

That attack is the toy’s failure, and its cost of $2^m$ trials is small only because $m$ is. The $(n + 1) \log_2 q$ term in the leftover hash lemma’s condition has a separate reason, which is a count. The step from Hybrid 1 to Hybrid 2 needs the joint output $[A \,\|\, u]^\top r$ to be close to uniform on $\mathbb{Z}_q^{n+1}$, and for a fixed $[A \,\|\, u]$ that output takes at most $2^m$ values.

The statistical distance between two distributions is the largest difference between the probabilities they give one set of outcomes. The uniform distribution puts probability at least $1 - 2^m/q^{n+1}$ on the points the output never takes, so the distance between the two is at least $1 - 2^m/q^{n+1} = 1 - 2^{m - (n + 1) \log_2 q}$. That stays at least $1/2$ until $m$ exceeds $(n + 1) \log_2 q - 1$. At the toy it is $1 - 256/97^5 \approx 1 - 3.0 \times 10^{-8}$: eight random bits cannot spread over a space of about $33$ bits.

The lemma’s condition, $m \geq (n + 1) \log_2 q + 2 \log_2(1/\epsilon)$, adds $2 \log_2(1/\epsilon)$ to the $(n + 1) \log_2 q$ term to reach the accuracy $\epsilon$. It is sufficient for $\epsilon$-closeness, not a threshold whose failure yields an attack. The count shows that the proof’s last step bounds nothing at $m = 8$, and the enumeration is what breaks the toy.

Decrypting the challenge with one query. The proof establishes IND-CPA security only. An IND-CCA2 adversary gets an additional decryption oracle that it can query on any ciphertext except the challenge, and against Regev’s scheme one query is enough to learn the challenge bit. Given the challenge $(c_1, c_2)$, the adversary asks for the decryption of $(c_1, c_2 + \lfloor q/2 \rfloor \bmod q)$. That ciphertext differs from the challenge in its second coordinate, so the oracle answers it.

With $E = e^\top r$ the challenge’s noise, the decrypted value moves from $v \equiv \lfloor q/2 \rfloor \mu + E$ to $v + \lfloor q/2 \rfloor \equiv \lfloor q/2 \rfloor (\mu + 1) + E \pmod q$. At the toy that is $48 + E$ for $\mu = 0$, and $96 + E \equiv E - 1 \pmod{97}$ for $\mu = 1$. An honest ciphertext of the toy has $\lvert E \rvert \leq m B = 8$, so the first lands in the bit-$1$ region, the second in the bit-$0$ region, and the oracle returns $1 - \mu$.

import numpy as np

def keygen(n, q, m, B, rng):
    s = rng.integers(0, q, size=n, dtype=np.int64)
    A = rng.integers(0, q, size=(m, n), dtype=np.int64)
    e = rng.integers(-B, B + 1, size=m, dtype=np.int64)
    return (A, (A @ s + e) % q), s

def encrypt(A, b, bit, q, rng):
    m = b.shape[0]
    r = rng.integers(0, 2, size=m, dtype=np.int64)
    half_q = q // 2
    return (A.T @ r) % q, (int(b @ r) + half_q * bit) % q

def decode(v, q):
    half_q = q // 2
    return ((2 * (v % q) + half_q) // q) % 2

def decrypt(s, c1, c2, q):
    return decode(int(c2) - int(c1 @ s), q)

# The challenger holds s and decrypts any ciphertext except the
# challenge. The adversary sends one query and flips the answer.
n, q, m, B = 4, 97, 8, 1
half_q = q // 2
wins = 0
for seed in range(200):
    rng = np.random.default_rng(seed=seed)
    (A, b), s = keygen(n, q, m, B, rng)
    for bit in (0, 1):
        c1, c2 = encrypt(A, b, bit, q, rng)
        answer = decrypt(s, c1, (c2 + half_q) % q, q)
        wins += (1 - answer) == bit
print("challenge bits found with one query:", wins, "of 400")

# Every honest noise value E = e^T r has |E| <= m B = 8.
flips = sum(decode(half_q * bit + E + half_q, q) == 1 - bit
            for bit in (0, 1) for E in range(-m * B, m * B + 1))
stuck = [v for v in range(q) if decode(v + half_q, q) == decode(v, q)]
print("pairs (bit, E) where the shift flips the bit:", flips, "of 34")
print("decrypted values the shift does not flip:", stuck)
# ==> challenge bits found with one query: 400 of 400
# ==> pairs (bit, E) where the shift flips the bit: 34 of 34
# ==> decrypted values the shift does not flip: [73]

The flip holds at all $34$ pairs of a bit and an $E$ with $\lvert E \rvert \leq 8$. It is not an identity on $\mathbb{Z}_{97}$. There the bit-$0$ region has $49$ residues and the bit-$1$ region $48$, so no shift can carry every bit-$0$ value into the bit-$1$ region. The one left behind is $73$, whose shift $121 \equiv 24$ also decodes to $0$. The value $73$ is not an honest one, since honest decrypted values lie within $8$ of $0$ or $48$.

The adversary never uses $s$, which the block holds only to play the oracle. Unlike the enumeration, the query does not depend on the small $m$: adding $\lfloor q/2 \rfloor$ to $c_2$ adds $\lfloor q/2 \rfloor$ to the decrypted value under every key. So the raw Regev scheme is not IND-CCA2 secure, and malformed ciphertexts can also leak the secret itself. Chapter 13’s decoder-boundary key recovery recovers the whole secret of a small-secret variant of this scheme in $2n$ decryption queries.

Chapter 11 moves from PKE to KEMs and adds the Fujisaki-Okamoto-style transform used by ML-KEM: decapsulation decrypts the ciphertext, derives the encryption randomness again from the decrypted message, re-encrypts, and compares the recomputed ciphertext to the received one. On mismatch, ML-KEM performs implicit rejection and returns a pseudorandom fallback key derived from a stored secret rather than an explicit failure symbol. The resulting KEM is believed to satisfy IND-CCA2 under the stated module-lattice assumptions and the FO-style random-oracle / quantum-random-oracle modeling assumptions. Chapter 11 walks that construction and states the Hofheinz-Hövelmanns-Kiltz theorem’s assumptions. Their random-oracle reduction for the implicit-rejection transform is the one FIPS 203 cites, and it builds on the original Fujisaki-Okamoto transform (Fujisaki & Okamoto, 1999; Hofheinz et al., 2017, sec. 3; National Institute of Standards and Technology, 2024, sec. 3.2). Chapter 11 also says what their quantum-random-oracle theorems for KEMs cover.

Tradeoffs inside Part II

Regev’s original flat construction uses only matrix-vector arithmetic over $\mathbb{Z}_q$, which is why the noise budget derivation and the IND-CPA proof in this chapter both fit in a page (Regev, 2009). The Ring-LWE framing from Chapter 9 improves public-key size and amortized bandwidth by replacing unstructured flat-LWE linear algebra with structured multiplication by ring elements in $R_q$. A single ring element $a \in R_q$ acts as a negacyclic convolution operator, so an entire $n \times n$ structured linear map is carried by one polynomial.

A strict single-bit comparison is closer to $n + 1$ field elements (flat Regev for one bit) versus $2 n$ field elements (the two-element Ring-LWE ciphertext) (Lyubashevsky et al., 2013, sec. 1). The structural gain comes from public-key compression, faster polynomial arithmetic, and message packing of up to $n$ bits per ciphertext. The cost is a security assumption that restricts to ideal lattices (Lyubashevsky et al., 2010).

Chapter 11 uses Module-LWE, where the secret is a vector of $k$ ring elements in $R_q$. At $k = 1$ this is Ring-LWE; at ring dimension $n = 1$ this is flat LWE. ML-KEM chooses $k$ and $n$ to match a target bandwidth and security level (National Institute of Standards and Technology, 2024). Chapter 13 walks primal and dual lattice attacks against the public LWE samples such a scheme’s key material exposes, and estimates their cost under a stated attack and cost model. It reads those estimates against the published category assessments rather than deriving a security level for arbitrary decisional-LWE parameters.

Chapter 11 is the immediate next step: it rebuilds key generation, encryption, and decryption over Module-LWE, then adds the Fujisaki-Okamoto transform that turns an IND-CPA scheme like this one into a KEM believed to satisfy IND-CCA2 (Hofheinz et al., 2017), standardized as ML-KEM (National Institute of Standards and Technology, 2024).

Exercises

1. Modify RegevParams to accept $(n = 4, q = 13, m = 8, B = 1)$ and measure the decryption failure rate across 1000 seeds with both message bits. Compare the observed rate against the analytical failure rate computed from the exact distribution of $e^\top r$ at those parameters.

2. Extend the single-bit scheme to encrypt a $k$-bit plaintext by running $k$ independent ciphertexts with the same public key. Report the ciphertext expansion factor in $\mathbb{Z}_q$ entries per plaintext bit.

3. Re-derive the noise budget for $r$ drawn uniformly from $\{-1, 0, 1\}^m$ instead of $\{0, 1\}^m$. Show that the worst-case bound remains $|e^\top r| \leq m B$, while the typical size increases by a constant factor because ternary $r$ is nonzero with probability $2/3$ rather than $1/2$. The signs make the sum symmetric but do not by themselves increase the variance when the error distribution is already symmetric.

4. Explain in two sentences why replacing the encoding shift $\lfloor q/2 \rfloor$ with $\lfloor q/3 \rfloor$ breaks the existing nearest-codeword decoder for $\{0, \lfloor q/2 \rfloor\}$. State the new noise bound that would make a redesigned nearest-codeword decoder for $\{0, \lfloor q/3 \rfloor\}$ work. Show that it tightens to roughly $|e^\top r| < q/6$.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 10. A separate track, for rebuilding rather than reading: the package exercises/ch10-regev-pke has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch10 to grade your version against the suite that proves the reference one.

References

Boneh, D., & Shoup, V. (2023). A Graduate Course in Applied Cryptography (v0.6). Free online textbook. https://toc.cryptobook.us/

Fujisaki, E., & Okamoto, T. (1999). Secure integration of asymmetric and symmetric encryption schemes. Advances in Cryptology – CRYPTO 1999, 1666, 537–554. https://doi.org/10.1007/3-540-48405-1_34

Hofheinz, D., Hövelmanns, K., & Kiltz, E. (2017). A modular analysis of the Fujisaki-Okamoto transformation. Theory of Cryptography – TCC 2017, Part I, 10677, 341–371. https://doi.org/10.1007/978-3-319-70500-2_12

Lyubashevsky, V., Peikert, C., & Regev, O. (2010). On ideal lattices and learning with errors over rings. In H. Gilbert (Ed.), Advances in Cryptology – EUROCRYPT 2010 (Vol. 6110, pp. 1–23). Springer. https://doi.org/10.1007/978-3-642-13190-5_1

Lyubashevsky, V., Peikert, C., & Regev, O. (2013). On ideal lattices and learning with errors over rings. Journal of the ACM, 60(6), 43:1-43:35. https://doi.org/10.1145/2535925

National Institute of Standards and Technology. (2024). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.203

Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6), 34:1-34:40. https://doi.org/10.1145/1568318.1568324