1. Initial Setup

• $\Delta = \frac{q}{t}$, where $t$ divides $q$
• $S \in_R \mathbb{Z}_2^k$

2. Encryption Input

\[m \in \mathbb{Z}_t,\quad A \in_R \mathbb{Z}_q^k,\quad e \sim \chi_{\sigma}\]

3. Encryption Steps

1. Scale the plaintext: \(\Delta \cdot m \in \mathbb{Z}_q\)

2. Compute: \(b = A \cdot S + \Delta \cdot m + e \pmod{q}\)

3. Output ciphertext: \(LWE_{S,\sigma}(\Delta m) = (A, b) \in \mathbb{Z}_q^{k+1}\)

1. Decryption Input

\[C = (A, b) \in \mathbb{Z}_q^{k+1}\]

2. Decryption Steps

1. Remove the secret term: \(b - A \cdot S = \Delta m + e \pmod{q}\)

2. Scale down: \(\frac{\left\lfloor \Delta m + e \right\rceil_{\Delta}}{\Delta} \;\; \bmod t = m \in \mathbb{Z}_t\)

3. Correctness Condition

\[e < \frac{\Delta}{2}\]

→ Ensures correct rounding and successful decryption

1. Setting

Now suppose that $t$ does not divide $q$.

Then we set the scaling factor as:

\[\Delta = \left\lfloor \frac{q}{t} \right\rfloor\]

→ Even if $m > t$, decryption still correctly recovers the result. But why?

2. Writing the plaintext as a wrapped value

To analyze this, we write the plaintext $m$ as

\[m = m' + kt, \quad m' \in \mathbb{Z}_t,\; k \in \mathbb{Z}\]

Here, $m’$ is the actual value of $m$ modulo $t$, and $kt$ represents how many times $m$ has wrapped around modulo $t$.

So the goal of decryption is really to recover $m’ = m \bmod t$.

3. Expanding the scaled plaintext

The scaled plaintext with noise is

\[\left\lfloor \frac{q}{t} \right\rfloor m + e\]

Substituting $m = m’ + kt$, we get

\[\left\lfloor \frac{q}{t} \right\rfloor m + e = \left\lfloor \frac{q}{t} \right\rfloor m' + \left\lfloor \frac{q}{t} \right\rfloor kt + e\]

Now focus on the second term:

\[\left\lfloor \frac{q}{t} \right\rfloor kt\]

Since

\[\frac{q}{t} = \left\lfloor \frac{q}{t} \right\rfloor + \left(\frac{q}{t} - \left\lfloor \frac{q}{t} \right\rfloor\right),\]

we can rewrite it as

\[\left\lfloor \frac{q}{t} \right\rfloor kt = \frac{q}{t}kt - \left(\frac{q}{t} - \left\lfloor \frac{q}{t} \right\rfloor\right)kt\]

Because

\[\frac{q}{t}kt = qk,\]

this becomes

\[\left\lfloor \frac{q}{t} \right\rfloor kt = qk - \left(\frac{q}{t} - \left\lfloor \frac{q}{t} \right\rfloor\right)kt\]

Therefore,

\[\left\lfloor \frac{q}{t} \right\rfloor m + e = \left\lfloor \frac{q}{t} \right\rfloor m' + qk - \left(\frac{q}{t} - \left\lfloor \frac{q}{t} \right\rfloor\right)kt + e\]

4. What happens modulo $q$?

$qk$ is a multiple of $q$, so under modulo $q$ it disappears:

\[qk \equiv 0 \pmod q\]

So after reduction modulo $q$, the expression behaves like

\[\left\lfloor \frac{q}{t} \right\rfloor m' - \left(\frac{q}{t} - \left\lfloor \frac{q}{t} \right\rfloor\right)kt + e\]

That means the wrap-around part $kt$ does not remain as plaintext.
Instead, it gets absorbed into an additional error term.

5. Why is the extra error small?

Since

\[0 \le \frac{q}{t} - \left\lfloor \frac{q}{t} \right\rfloor < 1,\]

we have

\[0 \le \left(\frac{q}{t} - \left\lfloor \frac{q}{t} \right\rfloor\right)kt < kt\]

So this extra term is strictly smaller than $kt$.

The text therefore treats this part as an overestimated noise term and writes the expression conceptually as

\[\Delta m + e = \left\lfloor \frac{q}{t} \right\rfloor m + e \;\approx\; \left\lfloor \frac{q}{t} \right\rfloor m' + qk - e' + e,\]

where $e’ = kt$ is used as an upper bound, since the extra term is strictly smaller than $kt$.

In other words, the wrap-around portion of $m$ does not destroy correctness.
It only contributes some bounded extra noise.

6. Decryption

Recall the LWE decryption relation:

\[b - A \cdot S \bmod q = \Delta m + e\]

Using the rewritten form above,

\[\Delta m + e \;\approx\; \left\lfloor \frac{q}{t} \right\rfloor m' + qk - e' + e \pmod q\]

Now divide by $\left\lfloor \frac{q}{t} \right\rfloor$ and reduce modulo $t$:

\[\left[ \frac{1}{\left\lfloor q/t \right\rfloor} \cdot \left( \left\lfloor \frac{q}{t} \right\rfloor m' + qk - e' + e \;\bmod q \right) \right] \bmod t\]

7. Simplifying the expression

Since $qk \equiv 0 \pmod q$, the $qk$ term disappears:

\[\left[ \frac{1}{\left\lfloor q/t \right\rfloor} \cdot \left( \left\lfloor \frac{q}{t} \right\rfloor m' - e' + e \right) \right] \bmod t\]

Now divide by $\left\lfloor q/t \right\rfloor$:

\[m' + \frac{-kt + e}{\left\lfloor q/t \right\rfloor} = m' - \frac{kt - e}{\left\lfloor q/t \right\rfloor} \pmod t\]

→ For analysis, we upper bound this term as:

\[m' - \frac{kt + e}{\left\lfloor q/t \right\rfloor}\]

since $kt + e$ is a safe upper bound on the total error.

8. Correctness condition

So decryption correctly recovers $m’$ as long as the total error is small enough:

\[\frac{kt + e}{\left\lfloor q/t \right\rfloor} < \frac{1}{2}\]

If this holds, rounding removes the error term and we get

\[m' = m \bmod t\]

9. Interpretation

This condition can fail if:

(1) $e$ is too large

The term $e$ is the intrinsic LWE noise.

If $e$ becomes large, then the total error

\[\frac{kt + e}{\left\lfloor q/t \right\rfloor}\]

also increases.

→ The decrypted value may deviate too much, and rounding can fail.

(2) $t$ is too large

If $t$ increases, the scaling factor

\[\left\lfloor \frac{q}{t} \right\rfloor\]

becomes smaller.

Since the error is divided by this value,

\[\frac{kt + e}{\left\lfloor q/t \right\rfloor}\]

a smaller denominator leads to a larger overall error.

→ Intuitively, a larger $t$ weakens the scaling, so the noise is less suppressed.

(3) $k$ is too large

Recall:

\[m = m' + kt\]

If $k$ is large, then the wrap-around term $kt$ also becomes large.

Although $kt$ does not remain as plaintext after modulo $q$,
it contributes to the total error.

→ More wrap-around ⇒ larger additional noise.

🔑 Key insight

To keep decryption correct, we want:

\[q \gg t\]

so that

\[\left\lfloor \frac{q}{t} \right\rfloor\]

is large enough to absorb both the intrinsic noise $e$ and the additional error from $kt$.

10. Final takeaway

Even when $t$ does not divide $q$, decryption still works by setting

\[\Delta = \left\lfloor \frac{q}{t} \right\rfloor\]

The wrap-around part of $m$ does not remain in the plaintext.
It only contributes additional bounded noise.

So as long as

\[\frac{kt + e}{\left\lfloor q/t \right\rfloor} < \frac{1}{2},\]

the decrypted result is still

\[m \bmod t\]