Lemma 5.1 (Correctness), p. 34:35 — if Pr_{χ^⋆k}[|e| < ⌊p/2⌋/2] > 1 − δ for all k ≤ m, decryption is correct with probability ≥ 1 − δ

Let $p \ge 2$ and $n, m \ge 0$ be integers, let $\chi$ be a probability distribution on $\mathbb Z_p$, and let $\delta > 0$. For $a \in \mathbb Z_p$ let $|a|$ be its distance from $0$ modulo $p$, and let $\chi^{\star k}$ be the distribution of the sum of $k$ independent samples from $\chi$ ($\chi^{\star 0}$ the point mass at $0$). Assume that for every $k \in \{0, 1, \dots, m\}$,

Then the probability of decryption error of Regev's cryptosystem with parameters $n, m, p, \chi$ is at most $\delta$: for each bit $c \in \{0, 1\}$, if the private key $s$ is chosen uniformly in $\mathbb Z_p^n$, the public key $(a_i, \langle a_i, s\rangle + e_i)_{i=1}^m$ is formed with $a_i$ independent and uniform in $\mathbb Z_p^n$ and $e_i$ independent with law $\chi$, $c$ is encrypted with a uniformly random subset $S \subseteq [m]$, and the result is decrypted with $s$, then

the probability being over all of $s$, $a_1, \dots, a_m$, $e_1, \dots, e_m$ and $S$.

This is the correctness half of Regev's LWE-based public-key cryptosystem: it turns a tail bound on the noise distribution into a bound on the decryption error. For the paper's parameters, Claim 5.2 supplies the hypothesis with a negligible $\delta$.

Formalization Note The hypothesis and conclusion are stated in $\mathbb R$, with probabilities taken as toReal of PMF masses (exact, since they are at most $1$). An $\mathbb R_{\ge 0}^{\infty}$ form with ENNReal.ofReal (1 − δ) < was rejected: for $\delta \ge 1$ it would demand a positive probability, a hypothesis the page does not make. $p \ge 2$ is the paper's standing range for $\mathbb Z_p$ (p. 34:14); primality, which the paper's parameter choice includes, is not assumed, since the lemma does not use it. $\lfloor p/2\rfloor/2$ is a real number.