Proof of Lemma 2.15, p. 17 — for c ∈ t·I⁻¹ with c ≡ 1 mod J and v ∈ IM: c·v ∈ t·M and c·v − v ∈ IJM
ProvedLPRRingLWE.Clear.exists_preimagededekind-domainfractional-idealp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ring-lwe
Let be a number field with ring of integers , let be ideals with , let , and let be a fractional ideal of . Suppose satisfies and . Then for every :
- , i.e. for some ;
- .
In display form,
This is the surjectivity half of Lemma 2.15: is a preimage of under . Such a exists whenever is coprime to (apply the coprimality criterion of Lemma 2.13 to and ).
Formalization Note The element is taken as a hypothesis, so no coprimality assumption is needed. The paper computes "using the algorithm from Lemma 2.13"; the algorithm is not formalized. The paper's convention that and are nonzero is not assumed.
Preamble
import Mathlib import Definitions.Def_LPRRingLWE_Clear_Setting
Formal statement
namespace LPRRingLWE.Clear
open NumberField
open scoped nonZeroDivisors
/-- Proof of Lemma 2.15, p. 17 (surjectivity step): given `c ∈ t · I⁻¹` with `c ≡ 1 mod J`,
every `v ∈ IM` satisfies `c · v ∈ t · M` and `c · v − v ∈ IJM`. -/
theorem exists_preimage {K : Type*} [Field K] [NumberField K]
(I J : Ideal (𝓞 K)) (hI : I ≠ ⊥) (t : 𝓞 K) (ht : t ∈ I) (M : FractionalIdeal (𝓞 K)⁰ K)
(c : K) (hc : c ∈ cleared t I) (hc1 : c - 1 ∈ (J : FractionalIdeal (𝓞 K)⁰ K)) :
∀ v ∈ (I : FractionalIdeal (𝓞 K)⁰ K) * M,
(∃ w ∈ M, c * v = algebraMap (𝓞 K) K t * w) ∧
c * v - v ∈ (I : FractionalIdeal (𝓞 K)⁰ K) * J * M := by sorry
end LPRRingLWE.Clear
Source
Lyubashevsky, Peikert & Regev, On ideal lattices and learning with errors over rings, J. ACM 60(6) (2013), p. 17, proof of Lemma 2.15, third paragraph ("Let v ∈ IM be arbitrary … preimage of v mod IJM")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.