Encryption

Alice holds $pk = (\rho, \hat{\mathbf{t}})$ and wants to encrypt a 256-bit message $m$ using fresh randomness $r$.

01.The steps

E1. Rebuild $A^\top$. Alice runs the same rejection sampling on $\rho$ that key generation ran, reconstructing $A$, and takes its transpose.

The transpose is not cosmetic. Key generation multiplied by $A$, encryption multiplies by $A^\top$, and the cancellation in Why Decryption Works happens only because of that pairing. Getting it backwards produces a scheme that encrypts fine and never decrypts, which is a memorable way to lose an afternoon.

E2. Sample three small things. Using $r$ as a seed:

$$\mathbf{r} \in R_q^k \text{ from } \text{CBD}_{\eta_1}, \qquad \mathbf{e}_1 \in R_q^k \text{ from } \text{CBD}_{\eta_2}, \qquad e_2 \in R_q \text{ from } \text{CBD}_{\eta_2} .$$

Here $\mathbf{r}$ is Alice's own ephemeral secret, discarded after this one encryption. The other two are fresh errors whose job is to keep the outputs looking random.

E3. Compute $\mathbf{u}$.

$$\mathbf{u} \;=\; A^\top \mathbf{r} + \mathbf{e}_1 \;\in\; R_q^k .$$

Look at the shape of that. It is a Module-LWE sample, with $\mathbf{r}$ in the secret position. So to an attacker $\mathbf{u}$ is $k$ polynomials indistinguishable from uniform.

E4. Encode the message. Each of the 256 message bits becomes one coefficient:

$$m_j = 0 \;\longmapsto\; 0, \qquad m_j = 1 \;\longmapsto\; \left\lceil \frac{q}{2} \right\rceil = 1665 .$$

The two anchors are as far apart as $\mathbb{Z}_q$ allows. Decryption will recover each bit by asking which anchor the coefficient is nearer to, so maximising the separation maximises the noise that can be tolerated. Why Decryption Works turns that into an exact bound.

E5. Compute $v$.

$$v \;=\; \mathbf{t}^\top \mathbf{r} + e_2 + \text{Encode}(m) \;\in\; R_q .$$

A single polynomial holding the encoded message underneath a mask $\mathbf{t}^\top \mathbf{r} + e_2$, which again has the shape of a Module-LWE sample. Separating the message from the mask without $\mathbf{s}$ is the hard problem.

E6. Compress. Discard low-order bits of both parts before transmission, using $d_u = 10$ bits per coefficient of $\mathbf{u}$ and $d_v = 4$ bits per coefficient of $v$. Compression and Ciphertext Size covers the mechanics and why the two numbers differ.

E7. Emit.

$$c \;=\; \bigl(\text{Compress}(\mathbf{u}, d_u),\; \text{Compress}(v, d_v)\bigr).$$

For $k = 3$, $n = 256$, $d_u = 10$, $d_v = 4$:

$$\frac{3 \cdot 256 \cdot 10}{8} \;+\; \frac{256 \cdot 4}{8} \;=\; 960 + 128 \;=\; 1088 \text{ bytes} .$$

02.Why there are two ciphertext components

A reasonable question at this point is why the ciphertext has two parts with different shapes.

They do different jobs. The vector $\mathbf{u}$ carries Alice's ephemeral secret $\mathbf{r}$ in masked form, which is what lets Bob reconstruct the same mask she used. The single polynomial $v$ carries the message under that mask.

Bob's decryption is going to compute $v - \mathbf{s}^\top \mathbf{u}$. For that to strip the mask, $\mathbf{u}$ must contain $\mathbf{r}$ multiplied by something Bob's secret can undo, which is what $A^\top \mathbf{r}$ provides. Neither component alone reveals anything, and together they reveal the message only to whoever holds $\mathbf{s}$.

This is the same structural idea as Diffie-Hellman in Chapter 2, where each party sent a masked version of its own secret and the shared value emerged from combining them. Here the combination is lattice arithmetic and one side's contribution is baked into a published key rather than sent live.

03.What an attacker sees

The full ciphertext is $k + 1$ polynomials, all of which look uniform. There are two separate Module-LWE instances in play: one from key generation with secret $\mathbf{s}$, one from this encryption with secret $\mathbf{r}$.

Recovering the message needs one of them broken. The message itself sits in $v$ under a mask that is exactly as hard to remove as Module-LWE is to solve.

One consequence is worth flagging for the next chapter. The randomness $r$ in step E2 must be fresh for every encryption. Reusing it against the same public key produces two ciphertexts with the same $\mathbf{u}$, and their difference is the difference of the two encoded messages with all the masking cancelled. That is a total break, and it is why the wrapper in The Fujisaki-Okamoto Wrapper is careful about where randomness comes from.