Proof of Lemma 5.1, p. 34:36 — the decryption residue b − ⟨a, s⟩ equals Σ_{i∈S} e_i (plus ⌊p/2⌋ for bit 1)
ProvedRegevLWE.Correctness.residue_eqlattice-cryptographylearning-with-errorsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1public-key-encryption
Let , , , , , and let with be the public key of Regev's cryptosystem. For any subset , let be the encryption of a bit under , so that . Then
The identity reduces the correctness of decryption to the size of the accumulated noise .
Formalization Note The page states the bit-0 case and says the bit-1 case is similar; both are stated. No hypothesis on beyond [NeZero p] is needed for this algebraic identity.
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): for the public key `(aᵢ, bᵢ)` with
`bᵢ = ⟨aᵢ, s⟩ + eᵢ` and any subset `S ⊆ [m]`, the encryption `(a, b)` of `0` satisfies
`b − ⟨a, s⟩ = ∑_{i∈S} eᵢ`, and the encryption `(a, b)` of `1` satisfies
`b − ⟨a, s⟩ = ⌊p/2⌋ + ∑_{i∈S} eᵢ` ("the proof for an encryption of 1 is similar"). -/
theorem residue_eq {p : ℕ} [NeZero p] {n m : ℕ} (a : Fin m → Fin n → ZMod p)
(s : Fin n → ZMod p) (e : Fin m → ZMod p) (S : Finset (Fin m)) :
(encrypt (publicKey a s e) 0 S).2 - (encrypt (publicKey a s e) 0 S).1 ⬝ᵥ s
= ∑ i ∈ S, e i ∧
(encrypt (publicKey a s e) 1 S).2 - (encrypt (publicKey a s e) 1 S).1 ⬝ᵥ s
= ((p / 2 : ℕ) : ZMod p) + ∑ i ∈ S, e i := 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 (display and the sentence after it)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.