In this quick post, we will derive the decryption error probability bound that frequently appears in LWE and RLWE-based encryption schemes, using a simple Gaussian tail bound argument.
This derivation explains why, under standard parameter choices, the decryption error is negligibly small, typically on the order of $2^{-p}$ for some security parameter $p$.
1. Decryption Correctness Condition
In LWE/RLWE-based encryption, after decryption we recover a phase of the form:
$$
\text{phase} = \mu + e
$$
where $\mu$ is the encoded message and $e$ is the error term sampled from a Gaussian distribution $\mathcal{N}(0, \alpha^2)$.
Let $\mathcal{M}$ be the message space, and let $R$ be the packing radius, i.e., half the minimum distance between any two messages in $\mathcal{M}$.
- Decryption is correct if the noise doesn’t push the phase closer to a different message:
$$
|e| < R
$$ - Decryption fails if:
$$
|e| \ge R
$$
Therefore, the decryption failure probability is exactly the tail probability of the noise exceeding $R$.
2. Gaussian Tail Bound
For a Gaussian (or more generally, $\sigma$-subgaussian) random variable $X$ with standard deviation $\sigma$, the following standard tail bound holds [cite: 86]:
$$
P(|X| \ge x) \le 2 \exp\left(-\frac{x^2}{2\sigma^2}\right)
$$
Here:
- $X = e$
- $\sigma = \alpha$
- $x = R$
Substituting, the probability that the noise exceeds $R$ is:
$$
P(\text{failure}) = P(|e| \ge R) \le 2 \exp\left(-\frac{R^2}{2\alpha^2}\right)
$$
This already shows that the failure probability decreases exponentially in $R^2 / \alpha^2$.
3. Substituting the Noise Parameter
The paper specifies that the noise parameter $\alpha$ is chosen on the order of:
$$
\alpha = O\left(\frac{R}{\sqrt{p}}\right)
$$
where $p$ is the security parameter controlling the correctness error. We can write this more explicitly as:
$$
\alpha = \frac{R}{c\sqrt{p}}
$$
for some constant $c$ hidden by the Big-O notation.
Substitute this into the tail bound:
$$
P(\text{failure}) \le 2 \exp\left(-\frac{R^2}{2\left(\frac{R}{c\sqrt{p}}\right)^2}\right)
= 2 \exp\left(-\frac{R^2 \cdot c^2 p}{2 R^2}\right)
= 2 \exp\left(-\frac{c^2 p}{2}\right)
$$
4. Exponentially Small Failure Probability
The final expression
$$
P(\text{failure}) \le 2 \exp\left(-\frac{c^2 p}{2}\right)
$$
shows that by increasing $p$ (and shrinking $\alpha$ accordingly), the decryption error probability decays exponentially in $p$.
This is often expressed in cryptography as being negligible in $p$, e.g.
$$
P(\text{failure}) \le 2^{-p}
$$
after appropriate choice of constants.
5. Intuition Recap
- Decryption correctness is equivalent to the noise staying within the packing radius.
- Gaussian noise is sharply concentrated around 0.
- By setting $\alpha$ small relative to $R$, the chance of noise “escaping” becomes negligible.
- The tail bound provides a clean way to quantify this probability.
This derivation underpins the reliability of LWE/RLWE-based cryptosystems: with appropriate parameter choices, the probability of incorrect decryption can be made exponentially small in the security parameter.
peace. da1729