Proof of Lemma 5.1, p. 34:36 — |x| < ⌊p/2⌋/2 implies x is closer to 0 than to ⌊p/2⌋, so decryption is correct
ProvedRegevLWE.Correctness.roundinglattice-cryptographylearning-with-errorsmodular-arithmeticp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and, for , let be its distance from modulo (the integer if , else ). Let satisfy
Then:
- is closer to than to modulo : ;
- the residue decrypts to ;
- the residue decrypts to .
Items 2 and 3 say that, when the accumulated noise is small, the decryption of an encryption of either bit is correct.
Formalization Note may be a half-integer, so the hypothesis compares with it in . "Decrypts to" refers to the decision rule decodeResidue applied to the residue . Item 3 is the bit-1 case the page calls "similar".
Preamble
import Mathlib import Definitions.Def_RegevLWE_Correctness_Cryptosystem open Matrix
Formal statement
namespace RegevLWE.Correctness
/-- Proof of Lemma 5.1 (Regev, J. ACM 2009, p. 34:36): let `p ≥ 2` and `x ∈ ℤ_p` with
`|x| < ⌊p/2⌋/2` (the bound compared in `ℝ`). Then `x` is closer to `0` than to `⌊p/2⌋`
modulo `p`, so the residue `x` decrypts to `0`, and the residue `⌊p/2⌋ + x` (an encryption
of `1`) decrypts to `1`. -/
theorem rounding {p : ℕ} [NeZero p] (hp : 2 ≤ p) (x : ZMod p)
(hx : (absZ x : ℝ) < ((p / 2 : ℕ) : ℝ) / 2) :
absZ x < absZ (x - ((p / 2 : ℕ) : ZMod p)) ∧
decodeResidue x = 0 ∧
decodeResidue (((p / 2 : ℕ) : ZMod p) + x) = 1 := by sorry
end RegevLWE.Correctness
Source
Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, J. ACM 56(6) (2009), Article 34, p. 34:36, proof of Lemma 5.1 ("In this case, it is closer to 0 than to ⌊p/2⌋ and therefore the decryption is correct.")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.