Certified finite feature enumeration for each fixed positive degree
DefinitionWitnessEncryption_Runtime_FeatureEnumerationFix a positive integer degree . For an input , put , and define
The module provides explicit finite enumeration programs for the row labels used in the order and basis construction: an index , a vector with , and a subset with . It includes the concrete list enumerators and their required counting, size, and resource certificates, together with fixed-degree binomial computation and binary normalization routines.
Let be the row-enumeration realizer and its output list. There are constants , depending on the fixed program parameter , such that every input satisfies
Here is the canonical physical coding volume; in particular the natural-number input has volume . Thus the certificate charges the actual enumeration output and machine operations. This is a family of polynomial resource bounds for each fixed positive degree, with no joint polynomial bound in a variable degree asserted. These routines supply the concrete finite feature lists used by the witness-encryption reduction.
import Definitions.Def_WitnessEncryption_Runtime_ListMetadataCompare
import Definitions.Def_WitnessEncryption_Runtime_SamplingSerialization
import Definitions.Def_GenericGroupWE_Main_Circuit
set_option autoImplicit false
section
-- Source: WitnessEncryption.ParameterBasic
namespace GenericGroupWE.Main
open scoped BigOperators
namespace ParameterProof
lemma weight_pos (N : ℕ) : 1 ≤ weightDegree N := le_max_left _ _
lemma choose_scale (d r : ℕ) (hr : 1 ≤ r) :
(1 / (d.factorial : ℝ)) * (r : ℝ)^d ≤ (Nat.choose (r + 2*d) d : ℝ) ∧
(Nat.choose (r + 2*d) d : ℝ) ≤ ((1 + 2*d : ℕ) : ℝ)^d * (r : ℝ)^d := by
constructor
· have h := Nat.pow_le_choose (α := ℝ) d (r + 2*d)
have hs : r ≤ r + 2*d + 1 - d := by omega
have hp : (r : ℝ)^d ≤ ((r + 2*d + 1 - d : ℕ) : ℝ)^d := by
gcongr
have hf : (0 : ℝ) < d.factorial := by exact_mod_cast d.factorial_pos
calc
(1 / (d.factorial : ℝ)) * (r : ℝ)^d = (r : ℝ)^d / d.factorial := by ring
_ ≤ ((r + 2*d + 1 - d : ℕ) : ℝ)^d / d.factorial := by gcongr
_ ≤ (Nat.choose (r + 2*d) d : ℝ) := h
· have h := Nat.choose_le_pow (r + 2*d) d
have hs : r + 2*d ≤ (1+2*d)*r := by nlinarith
calc
(Nat.choose (r + 2*d) d : ℝ) ≤ ((r + 2*d : ℕ) : ℝ)^d := by exact_mod_cast h
_ ≤ (((1 + 2*d)*r : ℕ) : ℝ)^d := by gcongr
_ = ((1+2*d : ℕ) : ℝ)^d * (r : ℝ)^d := by rw [Nat.cast_mul, mul_pow]
lemma matrixOrder_lower (N d : ℕ) (hd : 1 ≤ d) (hN : 2 ≤ N) :
N ≤ matrixOrder N d := by
have hsum : N ≤ ∑ j ∈ Finset.range (min d N + 1), Nat.choose N j := by
simpa using (Finset.single_le_sum (fun j _ => Nat.zero_le (Nat.choose N j))
(show 1 ∈ Finset.range (min d N + 1) by simp only [Finset.mem_range]; omega))
have hchoose : 1 ≤ Nat.choose ((rankTarget N d)^2 + weightDegree N) (weightDegree N) :=
Nat.choose_pos (by omega)
unfold matrixOrder
calc
N ≤ ∑ j ∈ Finset.range (min d N + 1), Nat.choose N j := hsum
_ ≤ (∑ j ∈ Finset.range (min d N + 1), Nat.choose N j) *
(N * ((rankTarget N d)^2 + weightDegree N) + 1) :=
Nat.le_mul_of_pos_right _ (Nat.succ_pos _)
_ ≤ _ := Nat.le_mul_of_pos_right _ hchoose
lemma label_log_bound (N d : ℕ) :
Real.logb 2 (Nat.choose ((rankTarget N d)^2 + weightDegree N) (weightDegree N) : ℝ) ≤
(weightDegree N : ℝ) * Real.logb 2 ((rankTarget N d)^2 + weightDegree N : ℝ) := by
have hr := weight_pos N
have hc : 0 < Nat.choose ((rankTarget N d)^2 + weightDegree N) (weightDegree N) :=
Nat.choose_pos (by omega)
have hp := Nat.choose_le_pow ((rankTarget N d)^2 + weightDegree N) (weightDegree N)
calc
Real.logb 2 (Nat.choose ((rankTarget N d)^2 + weightDegree N) (weightDegree N) : ℝ) ≤
Real.logb 2 ((((rankTarget N d)^2 + weightDegree N : ℕ) : ℝ)^(weightDegree N)) := by
apply Real.logb_le_logb_of_le (by norm_num)
· exact_mod_cast hc
· exact_mod_cast hp
_ = _ := by simp only [Real.logb_pow, Nat.cast_add, Nat.cast_pow]
lemma weight_log_bounds (N : ℕ) (hN : 2 ≤ N) :
Real.logb 2 (N : ℝ) ≤ 4*(weightDegree N : ℝ)^2 ∧
(weightDegree N : ℝ)^2 ≤ 3*Real.logb 2 (N : ℝ) := by
have hN' : (2 : ℝ) ≤ N := by exact_mod_cast hN
have hL : 1 ≤ Real.logb 2 (N : ℝ) := by
calc
1 = Real.logb 2 (2 : ℝ) := by norm_num [Real.logb]
_ ≤ Real.logb 2 (N : ℝ) :=
Real.logb_le_logb_of_le (by norm_num) (by norm_num) (by exact_mod_cast hN)
have hn0 : (0 : ℝ) < N := by exact_mod_cast (by omega : 0 < N)
have hlog0 : 0 ≤ Real.logb 2 ((N + 2 : ℕ) : ℝ) := by
apply Real.logb_nonneg (by norm_num)
exact_mod_cast (by omega : 1 ≤ N+2)
have hk : (Nat.log 2 (N+2) : ℝ) ≤ Real.logb 2 ((N+2 : ℕ) : ℝ) := by
rw [← Real.natFloor_logb_natCast]
exact Nat.floor_le hlog0
have hk' : Real.logb 2 ((N+2 : ℕ) : ℝ) < (Nat.log 2 (N+2) : ℝ) + 1 := by
rw [← Real.natFloor_logb_natCast]
exact Nat.lt_floor_add_one _
have hshift : Real.logb 2 ((N+2 : ℕ) : ℝ) ≤ Real.logb 2 (N : ℝ) + 1 := by
calc
_ ≤ Real.logb 2 (2 * (N : ℝ)) := by
apply Real.logb_le_logb_of_le (by norm_num) (by positivity)
push_cast
nlinarith
_ = _ := by
rw [Real.logb_mul (by norm_num) (ne_of_gt hn0)]
norm_num [Real.logb]
ring
have hmono : Real.logb 2 (N : ℝ) ≤ Real.logb 2 ((N+2 : ℕ) : ℝ) := by
apply Real.logb_le_logb_of_le (by norm_num) hn0
push_cast
linarith
have hr : (1 : ℝ) ≤ weightDegree N := by exact_mod_cast weight_pos N
have hs : (Nat.sqrt (Nat.log 2 (N+2)) : ℝ) ≤ weightDegree N := by
exact_mod_cast (le_max_right 1 (Nat.sqrt (Nat.log 2 (N+2))))
have hsq : (Nat.log 2 (N+2) : ℝ)+1 ≤
((Nat.sqrt (Nat.log 2 (N+2)) : ℝ)+1)^2 := by
exact_mod_cast Nat.succ_le_succ_sqrt' (Nat.log 2 (N+2))
have hrsq : (weightDegree N : ℝ)^2 ≤ (Nat.log 2 (N+2) : ℝ)+1 := by
have hx : (weightDegree N)^2 ≤ Nat.log 2 (N+2) + 1 := by
unfold weightDegree
rcases le_total 1 (Nat.sqrt (Nat.log 2 (N+2))) with h | h
· rw [max_eq_right h]
exact (Nat.sqrt_le' _).trans (Nat.le_succ _)
· rw [max_eq_left h]
simp
exact_mod_cast hx
constructor <;> nlinarith [sq_nonneg ((weightDegree N : ℝ) - 1)]
end ParameterProof
end GenericGroupWE.Main
end
section
-- Source: WitnessEncryption.ParameterScales
namespace GenericGroupWE.Main
namespace ParameterProof
lemma weight_sqrt_bounds (N : ℕ) (hN : 2 ≤ N) :
(1/2 : ℝ) * Real.sqrt (Real.logb 2 (N : ℝ)) ≤ (weightDegree N : ℝ) ∧
(weightDegree N : ℝ) ≤ 2 * Real.sqrt (Real.logb 2 (N : ℝ)) := by
obtain ⟨hl, hu⟩ := weight_log_bounds N hN
have hL : 0 ≤ Real.logb 2 (N : ℝ) := by
apply Real.logb_nonneg (by norm_num)
exact_mod_cast (by omega : 1 ≤ N)
have hr : 0 ≤ (weightDegree N : ℝ) := Nat.cast_nonneg _
have hs := Real.sq_sqrt hL
have hx := Real.sqrt_nonneg (Real.logb 2 (N : ℝ))
have hlo : Real.sqrt (Real.logb 2 (N : ℝ)) ≤ 2 * (weightDegree N : ℝ) := by
apply (sq_le_sq₀ hx (by positivity)).mp
nlinarith
have hhi : (weightDegree N : ℝ) ≤ 2 * Real.sqrt (Real.logb 2 (N : ℝ)) := by
apply (sq_le_sq₀ hr (by positivity)).mp
nlinarith
constructor
· linarith
· exact hhi
end ParameterProof
end GenericGroupWE.Main
end
section
-- Source: WitnessEncryption.ParameterEntropy
namespace GenericGroupWE.Main.ParameterProof
open Filter
lemma sqrt_log_sublinear (C ε : ℝ) (hC : 0 < C) (hε : 0 < ε) :
∃ threshold : ℕ, 4 ≤ threshold ∧ ∀ N : ℕ, threshold ≤ N →
C * Real.sqrt (Real.logb 2 (N : ℝ)) * Real.logb 2 (Real.logb 2 (N : ℝ)) ≤
ε * Real.logb 2 (N : ℝ) := by
have htwo : 0 < Real.log 2 := Real.log_pos (by norm_num)
have hη : 0 < ε * Real.log 2 / C := by positivity
have hs := (isLittleO_log_rpow_atTop (r := (1/2 : ℝ)) (by norm_num)).bound hη
have hlim : Tendsto (fun N : ℕ => Real.logb 2 (N : ℝ)) atTop atTop :=
(Real.tendsto_logb_atTop (by norm_num)).comp tendsto_natCast_atTop_atTop
have hevent := hlim.eventually hs
obtain ⟨T, hT⟩ := hevent.exists_forall_of_atTop
refine ⟨max T 4, le_max_right _ _, ?_⟩
intro N hN
have hbound := hT N ((le_max_left _ _).trans hN)
have hN' : (4 : ℝ) ≤ N := by exact_mod_cast ((le_max_right T 4).trans hN)
have hL : 1 ≤ Real.logb 2 (N : ℝ) := by
calc
1 = Real.logb 2 (2 : ℝ) := by norm_num [Real.logb]
_ ≤ _ := Real.logb_le_logb_of_le (by norm_num) (by norm_num) (by linarith)
have hlog : 0 ≤ Real.log (Real.logb 2 (N : ℝ)) := Real.log_nonneg hL
have hroot := Real.sqrt_nonneg (Real.logb 2 (N : ℝ))
have hsq := Real.sq_sqrt (by linarith : 0 ≤ Real.logb 2 (N : ℝ))
simp only [Real.norm_eq_abs, abs_of_nonneg hlog, ← Real.sqrt_eq_rpow,
abs_of_nonneg hroot] at hbound
calc
C * Real.sqrt (Real.logb 2 (N : ℝ)) * Real.logb 2 (Real.logb 2 (N : ℝ)) =
(C * Real.sqrt (Real.logb 2 (N : ℝ)) / Real.log 2) *
Real.log (Real.logb 2 (N : ℝ)) := by simp only [Real.logb]; ring
_ ≤ (C * Real.sqrt (Real.logb 2 (N : ℝ)) / Real.log 2) *
((ε * Real.log 2 / C) * Real.sqrt (Real.logb 2 (N : ℝ))) :=
mul_le_mul_of_nonneg_left hbound (by positivity)
_ = ε * Real.logb 2 (N : ℝ) := by
field_simp [ne_of_gt hC, ne_of_gt htwo]
nlinarith [hsq]
end GenericGroupWE.Main.ParameterProof
namespace GenericGroupWE.Main.ParameterProof
open Filter
end GenericGroupWE.Main.ParameterProof
namespace GenericGroupWE.Main
theorem parameter_weight_entropy_bound :
∀ d : ℕ, 1 ≤ d → ∃ C : ℝ, 0 < C ∧
∀ N : ℕ, 4 ≤ N →
(weightDegree N : ℝ) * Real.logb 2 ((rankTarget N d)^2 + weightDegree N : ℝ) ≤
C * Real.sqrt (Real.logb 2 (N : ℝ)) * Real.logb 2 (Real.logb 2 (N : ℝ)) := by
intro d hd
let B : ℝ := ((1+2*d : ℕ) : ℝ)^d
have hB : 0 < B := by dsimp [B]; positivity
have hlogB : 0 ≤ Real.logb 2 (B^2+1) :=
Real.logb_nonneg (by norm_num) (by nlinarith [sq_nonneg B])
have hd' : (1 : ℝ) ≤ d := by exact_mod_cast hd
refine ⟨2*(Real.logb 2 (B^2+1)+3*d), by positivity, ?_⟩
intro N hN
have hN2 : 2 ≤ N := by omega
have hN' : (4 : ℝ) ≤ N := by exact_mod_cast hN
have hr : (1 : ℝ) ≤ weightDegree N := by exact_mod_cast ParameterProof.weight_pos N
have hr0 : (0 : ℝ) < weightDegree N := by linarith
have hL : 2 ≤ Real.logb 2 (N : ℝ) := by
calc
2 = Real.logb 2 (4 : ℝ) := by
rw [show (4 : ℝ) = 2^2 by norm_num, Real.logb_pow]
norm_num [Real.logb]
_ ≤ _ := Real.logb_le_logb_of_le (by norm_num) (by norm_num) hN'
have hL0 : 0 < Real.logb 2 (N : ℝ) := by linarith
have hll : 1 ≤ Real.logb 2 (Real.logb 2 (N : ℝ)) := by
calc
1 = Real.logb 2 (2 : ℝ) := by norm_num [Real.logb]
_ ≤ _ := Real.logb_le_logb_of_le (by norm_num) (by norm_num) hL
have hscale := (ParameterProof.choose_scale d (weightDegree N) (ParameterProof.weight_pos N)).2
change (rankTarget N d : ℝ) ≤ B * (weightDegree N : ℝ)^d at hscale
have hsquare : (rankTarget N d : ℝ)^2 ≤ B^2 * (weightDegree N : ℝ)^(2*d) := by
calc
_ ≤ (B * (weightDegree N : ℝ)^d)^2 := by gcongr
_ = _ := by rw [mul_pow, ← pow_mul (weightDegree N : ℝ) d 2, Nat.mul_comm d 2]
have hrpow : (weightDegree N : ℝ) ≤ (weightDegree N : ℝ)^(2*d) := by
simpa using (pow_le_pow_right₀ hr (show 1 ≤ 2*d by omega))
have hbase : (rankTarget N d : ℝ)^2 + (weightDegree N : ℝ) ≤
(B^2+1) * (weightDegree N : ℝ)^(2*d) := by nlinarith
have hlogbase : Real.logb 2 ((rankTarget N d)^2 + weightDegree N : ℝ) ≤
Real.logb 2 (B^2+1) + ((2*d : ℕ) : ℝ) * Real.logb 2 (weightDegree N : ℝ) := by
calc
_ ≤ Real.logb 2 ((B^2+1) * (weightDegree N : ℝ)^(2*d)) :=
Real.logb_le_logb_of_le (by norm_num) (by positivity) hbase
_ = _ := by rw [Real.logb_mul (by positivity) (by positivity), Real.logb_pow]
have hroot : 0 < Real.sqrt (Real.logb 2 (N : ℝ)) := Real.sqrt_pos.2 hL0
have hsqrt := (ParameterProof.weight_sqrt_bounds N hN2).2
have hlogr : Real.logb 2 (weightDegree N : ℝ) ≤
1 + (1/2 : ℝ) * Real.logb 2 (Real.logb 2 (N : ℝ)) := by
calc
_ ≤ Real.logb 2 (2 * Real.sqrt (Real.logb 2 (N : ℝ))) :=
Real.logb_le_logb_of_le (by norm_num) hr0 hsqrt
_ = _ := by
rw [Real.logb_mul (by norm_num) (ne_of_gt hroot), Real.sqrt_eq_rpow,
Real.logb_rpow_eq_mul_logb_of_pos hL0]
norm_num [Real.logb]
have hmulLog := mul_le_mul_of_nonneg_left hlogr (show (0 : ℝ) ≤ 2*d by positivity)
have hlog : Real.logb 2 ((rankTarget N d)^2 + weightDegree N : ℝ) ≤
(Real.logb 2 (B^2+1)+3*d) * Real.logb 2 (Real.logb 2 (N : ℝ)) := by
push_cast at hlogbase
nlinarith [mul_le_mul_of_nonneg_left hll hlogB]
calc
(weightDegree N : ℝ) * Real.logb 2 ((rankTarget N d)^2 + weightDegree N : ℝ) ≤
(weightDegree N : ℝ) *
((Real.logb 2 (B^2+1)+3*d) * Real.logb 2 (Real.logb 2 (N : ℝ))) :=
mul_le_mul_of_nonneg_left hlog (le_of_lt hr0)
_ ≤ (2 * Real.sqrt (Real.logb 2 (N : ℝ))) *
((Real.logb 2 (B^2+1)+3*d) * Real.logb 2 (Real.logb 2 (N : ℝ))) :=
mul_le_mul_of_nonneg_right hsqrt (by positivity)
_ = _ := by ring
end GenericGroupWE.Main
end
section
-- Source: WitnessEncryption.ParameterOrder
namespace GenericGroupWE.Main.ParameterProof
open scoped BigOperators
lemma weight_le_twice (N : ℕ) (hN : 2 ≤ N) : weightDegree N ≤ 2*N := by
unfold weightDegree
apply max_le (by omega)
exact ((Nat.sqrt_le_self _).trans (Nat.log_le_self 2 (N+2))).trans (by omega)
lemma matrixOrder_poly_of_labels (N d : ℕ) (hd : 1 ≤ d) (hN : 2 ≤ N)
(hlabels : Nat.choose ((rankTarget N d)^2 + weightDegree N) (weightDegree N) ≤ N) :
matrixOrder N d ≤ (d+1)*(((d+2)^d)^2+3)*N^(3*d+2) := by
let D := (d+2)^d
let B := D^2+2
have hN1 : 1 ≤ N := by omega
have hr := weight_le_twice N hN
have hR : rankTarget N d ≤ D*N^d := by
calc
rankTarget N d ≤ (weightDegree N+2*d)^d := Nat.choose_le_pow _ _
_ ≤ ((d+2)*N)^d := by gcongr; nlinarith
_ = D*N^d := by rw [mul_pow]
have hp : N ≤ N^(2*d) := by
simpa using Nat.pow_le_pow_right hN1 (show 1 ≤ 2*d by omega)
have hbase : (rankTarget N d)^2 + weightDegree N ≤ B*N^(2*d) := by
have hR2 : (rankTarget N d)^2 ≤ D^2*N^(2*d) := by
calc
_ ≤ (D*N^d)^2 := by gcongr
_ = _ := by rw [mul_pow, ← pow_mul N d 2, Nat.mul_comm d 2]
dsimp [B]
nlinarith
have hsample : N*((rankTarget N d)^2+weightDegree N)+1 ≤ (B+1)*N^(2*d+1) := by
have hx := Nat.mul_le_mul_left N hbase
have hp1 : 1 ≤ N^(2*d+1) := Nat.one_le_pow _ _ hN1
calc
_ ≤ N*(B*N^(2*d)) + N^(2*d+1) := Nat.add_le_add hx hp1
_ = _ := by rw [pow_succ N (2*d)]; ring
have hcolumns : (∑ j ∈ Finset.range (min d N+1), Nat.choose N j) ≤ (d+1)*N^d := by
calc
_ ≤ ∑ _j ∈ Finset.range (min d N+1), N^d := by
apply Finset.sum_le_sum
intro j hj
have hjd : j ≤ d := by simp only [Finset.mem_range] at hj; omega
exact (Nat.choose_le_pow N j).trans (Nat.pow_le_pow_right hN1 hjd)
_ = (min d N+1)*N^d := by simp
_ ≤ (d+1)*N^d := Nat.mul_le_mul_right _ (by omega)
calc
matrixOrder N d ≤ ((d+1)*N^d) * ((B+1)*N^(2*d+1)) * N :=
Nat.mul_le_mul (Nat.mul_le_mul hcolumns hsample) hlabels
_ = (d+1)*(((d+2)^d)^2+3)*N^(3*d+2) := by
rw [show 3*d+2 = d+(2*d+1)+1 by omega,
pow_succ N (d+(2*d+1)), pow_add N d (2*d+1)]
dsimp [B, D]
ring
end GenericGroupWE.Main.ParameterProof
namespace GenericGroupWE.Main.ParameterProof
open scoped BigOperators
lemma polynomial_envelope (f : ℕ → ℕ) (e K T : ℕ)
(hf : ∀ N : ℕ, 2 ≤ N → T ≤ N → f N ≤ K*N^e) :
∃ C : ℝ, 0 < C ∧ ∀ N : ℕ, 2 ≤ N → (f N : ℝ) ≤ C*(N : ℝ)^C := by
let K' := K + ∑ n ∈ Finset.range T, f n
let E := max K' e + 1
have hE : 0 < E := by dsimp [E]; omega
have hEK : K' ≤ E := by dsimp [E]; omega
have hEe : e ≤ E := by dsimp [E]; omega
have hglobal : ∀ N : ℕ, 2 ≤ N → f N ≤ K'*N^e := by
intro N hN
by_cases hT : T ≤ N
· exact (hf N hN hT).trans (Nat.mul_le_mul_right _ (by dsimp [K']; omega))
· have hsum : f N ≤ ∑ n ∈ Finset.range T, f n :=
Finset.single_le_sum (fun _ _ => Nat.zero_le _) (by simp only [Finset.mem_range]; omega)
have hp : 1 ≤ N^e := Nat.one_le_pow e N (by omega)
calc
f N ≤ ∑ n ∈ Finset.range T, f n := hsum
_ ≤ K' := by dsimp [K']; omega
_ ≤ K'*N^e := Nat.le_mul_of_pos_right _ hp
refine ⟨(E : ℝ), by exact_mod_cast hE, ?_⟩
intro N hN
have hN1 : (1 : ℝ) ≤ N := by exact_mod_cast (by omega : 1 ≤ N)
calc
(f N : ℝ) ≤ (K' : ℝ)*(N : ℝ)^e := by exact_mod_cast hglobal N hN
_ ≤ (E : ℝ)*(N : ℝ)^e := by gcongr
_ = (E : ℝ)*(N : ℝ)^(e : ℝ) := by rw [Real.rpow_natCast]
_ ≤ (E : ℝ)*(N : ℝ)^(E : ℝ) := by
apply mul_le_mul_of_nonneg_left
· exact Real.rpow_le_rpow_of_exponent_le hN1 (by exact_mod_cast hEe)
· positivity
end GenericGroupWE.Main.ParameterProof
namespace GenericGroupWE.Main
theorem parameter_matrix_order_bound :
∀ d : ℕ, 1 ≤ d → ∃ C : ℝ, 0 < C ∧
∀ N : ℕ, 2 ≤ N → N ≤ matrixOrder N d ∧
(matrixOrder N d : ℝ) ≤ C * (N : ℝ)^C := by
intro d hd
obtain ⟨B, hB, hentropy⟩ := parameter_weight_entropy_bound d hd
obtain ⟨T, hT, hslow⟩ := ParameterProof.sqrt_log_sublinear B 1 hB (by norm_num)
have hlabels : ∀ N : ℕ, T ≤ N →
Nat.choose ((rankTarget N d)^2 + weightDegree N) (weightDegree N) ≤ N := by
intro N hN
have hN4 : 4 ≤ N := hT.trans hN
have hlog := (ParameterProof.label_log_bound N d).trans
((hentropy N hN4).trans (hslow N hN))
rw [one_mul] at hlog
have hc : 0 < Nat.choose ((rankTarget N d)^2+weightDegree N) (weightDegree N) :=
Nat.choose_pos (by omega)
have hreal := (Real.logb_le_logb (by norm_num)
(by exact_mod_cast hc) (by exact_mod_cast (by omega : 0 < N))).mp hlog
exact_mod_cast hreal
obtain ⟨C, hC, hbound⟩ := ParameterProof.polynomial_envelope
(fun N => matrixOrder N d) (3*d+2) ((d+1)*(((d+2)^d)^2+3)) T
(fun N hN hTN => ParameterProof.matrixOrder_poly_of_labels N d hd hN (hlabels N hTN))
exact ⟨C, hC, fun N hN => ⟨ParameterProof.matrixOrder_lower N d hd hN, hbound N hN⟩⟩
end GenericGroupWE.Main
end
section
-- Source: WitnessEncryption.BasisFeatureCounts
namespace GenericGroupWE.Main
namespace BasisFeatureProof
open scoped BigOperators
noncomputable def ordinarySlackEquiv (J r : ℕ) :
OrdinaryMonomial J r ≃ {f : Option (Fin J) → ℕ // ∑ i,f i=r} where
toFun a := ⟨fun i => match i with
| none => r-∑ j,(a.val j).val
| some j => (a.val j).val,by
rw [Fintype.sum_option]
exact Nat.sub_add_cancel a.property⟩
invFun f := ⟨fun j => ⟨f.val (some j),by
have hi : f.val (some j)≤∑ i,f.val i :=
Finset.single_le_sum (fun _ _ => Nat.zero_le _) (Finset.mem_univ _)
rw [f.property] at hi
omega⟩,by
change (∑ j,f.val (some j))≤r
have h := f.property
rw [Fintype.sum_option] at h
omega⟩
left_inv a := by
apply Subtype.ext
funext j
apply Fin.ext
rfl
right_inv f := by
apply Subtype.ext
funext i
cases i with
| none =>
change r-∑ j,f.val (some j)=f.val none
have h := f.property
rw [Fintype.sum_option] at h
omega
| some j => rfl
theorem ordinary_card (J r : ℕ) : Fintype.card (OrdinaryMonomial J r)=Nat.choose (J+r) r := by
classical
let : Fintype {f : Option (Fin J) → ℕ // ∑ i,f i=r} :=
Fintype.ofEquiv (Sym (Option (Fin J)) r) (Sym.equivNatSumOfFintype _ _)
calc
_ = Fintype.card {f : Option (Fin J) → ℕ // ∑ i,f i=r} :=
Fintype.card_congr (ordinarySlackEquiv J r)
_ = Fintype.card (Sym (Option (Fin J)) r) :=
Fintype.card_congr (Sym.equivNatSumOfFintype (Option (Fin J)) r).symm
_ = _ := by rw [Sym.card_sym_eq_choose]; simp
noncomputable def bitCardEquiv (N d : ℕ) : BitMonomial N d ≃
Σ j : Fin (min d N+1), {S : Finset (Fin N) // S.card=j.val} where
toFun S := ⟨⟨S.val.card,by
have hN : S.val.card≤N := by simpa using Finset.card_le_univ S.val
have hS := S.property
omega⟩,⟨S.val,rfl⟩⟩
invFun x := ⟨x.2.val,by have h := x.2.property; have hi := x.1.isLt; omega⟩
left_inv S := by apply Subtype.ext; rfl
right_inv x := by
rcases x with ⟨⟨j,hj⟩,⟨S,hS⟩⟩
dsimp only at hS
subst j
rfl
theorem bit_card (N d : ℕ) : Fintype.card (BitMonomial N d)=
∑ j∈Finset.range (min d N+1),Nat.choose N j := by
classical
calc
_ = Fintype.card (Σ j : Fin (min d N+1), {S : Finset (Fin N) // S.card=j.val}) :=
Fintype.card_congr (bitCardEquiv N d)
_ = ∑ j : Fin (min d N+1),Nat.choose N j.val := by
rw [Fintype.card_sigma]
simp only [Fintype.card_finset_len,Fintype.card_fin]
_ = _ := Fin.sum_univ_eq_sum_range _ _
theorem columnList_length (N d : ℕ) : (columnList N d).length=Fintype.card (BitMonomial N d) := by
classical
simp [columnList]
theorem rowList_nodup (N d : ℕ) : (rowList N d).Nodup := by
classical
exact (List.mergeSort_perm _ _).nodup_iff.mpr (Finset.nodup_toList _)
theorem columnList_nodup (N d : ℕ) : (columnList N d).Nodup := by
classical
exact (List.mergeSort_perm _ _).nodup_iff.mpr (Finset.nodup_toList _)
theorem mem_rowList {N d : ℕ} (row : StackRow N d) : row∈rowList N d := by
classical
simp [rowList]
theorem mem_columnList {N d : ℕ} (col : BitMonomial N d) : col∈columnList N d := by
classical
simp [columnList]
end BasisFeatureProof
end GenericGroupWE.Main
end
section
-- Source: WitnessEncryption.BasisWeakCompositions
namespace GenericGroupWE.Main
namespace BasisEnumerationProof
open scoped BigOperators
/-- Prefix expansion only through the remaining degree budget. No exponent box. -/
def weakCompositions : ℕ → ℕ → List (List ℕ)
| 0, _ => [[]]
| J+1, r => (weakCompositions J r).flatMap fun xs =>
(List.range (r-xs.sum+1)).map (fun k => k::xs)
theorem mem_weakCompositions (J r : ℕ) (xs : List ℕ) :
xs∈weakCompositions J r ↔ xs.length=J ∧ xs.sum≤r := by
induction J generalizing xs with
| zero =>
simp only [weakCompositions,List.mem_singleton]
constructor
· rintro rfl; simp
· rintro ⟨hl,_⟩; exact List.length_eq_zero_iff.mp hl
| succ J ih =>
cases xs with
| nil => simp [weakCompositions]
| cons k xs =>
constructor
· intro h
obtain ⟨ys,hys,hmap⟩ := List.mem_flatMap.mp h
obtain ⟨j,hj,hjeq⟩ := List.mem_map.mp hmap
obtain ⟨rfl,rfl⟩ := List.cons.inj hjeq
obtain ⟨hlen,hsum⟩ := (ih _).mp hys
simp only [List.length_cons,List.sum_cons]
simp only [List.mem_range] at hj
constructor <;> omega
· rintro ⟨hlen,hsum⟩
have htail : xs.sum≤r := by simp only [List.sum_cons] at hsum; omega
have hlen' : xs.length=J := by simp only [List.length_cons] at hlen; omega
apply List.mem_flatMap.mpr
refine ⟨xs,(ih _).mpr ⟨hlen',htail⟩,?_⟩
apply List.mem_map.mpr
refine ⟨k,?_,rfl⟩
simp only [List.mem_range,List.sum_cons] at hsum ⊢
omega
theorem weakCompositions_nodup (J r : ℕ) : (weakCompositions J r).Nodup := by
induction J with
| zero => simp [weakCompositions]
| succ J ih =>
apply List.nodup_flatMap.mpr
constructor
· intro xs hxs
exact (List.nodup_range).map (fun a b h => (List.cons.inj h).1)
· exact ih.imp (fun {xs ys} hne z hz1 hz2 => by
obtain ⟨a,ha,rfl⟩ := List.mem_map.mp hz1
obtain ⟨b,hb,heq⟩ := List.mem_map.mp hz2
exact hne (List.cons.inj heq).2.symm)
theorem ofFn_getD (xs : List ℕ) :
List.ofFn (fun i : Fin xs.length => xs.getD i.val 0)=xs := by
have hf : (fun i : Fin xs.length => xs.getD i.val 0)=xs.get := by
funext i
rw [List.getD_eq_getElem xs 0 i.isLt]
rfl
rw [hf,List.ofFn_get]
def fromList (J r : ℕ) (xs : List ℕ) (hlen : xs.length=J) (hsum : xs.sum≤r) :
OrdinaryMonomial J r :=
⟨fun i => ⟨xs.getD i.val 0,by
have hi : i.val<xs.length := by omega
have hm : xs.getD i.val 0∈xs := by
rw [List.getD_eq_getElem xs 0 hi]
exact List.getElem_mem hi
have hs := List.le_sum_of_mem hm
omega⟩,by
change (∑ i : Fin J,xs.getD i.val 0)≤r
subst J
rw [←List.sum_ofFn,ofFn_getD]
exact hsum⟩
theorem ofFn_fromList (J r : ℕ) (xs : List ℕ) (hlen : xs.length=J) (hsum : xs.sum≤r) :
List.ofFn (fun i => ((fromList J r xs hlen hsum).val i).val)=xs := by
change List.ofFn (fun i : Fin J => xs.getD i.val 0)=xs
subst J
exact ofFn_getD xs
noncomputable def ordinaryListEquiv (J r : ℕ) :
OrdinaryMonomial J r ≃ {xs : List ℕ // xs.length=J ∧ xs.sum≤r} :=
Equiv.ofBijective (fun a => ⟨List.ofFn (fun i => (a.val i).val),
by simpa only [List.length_ofFn,List.sum_ofFn,true_and] using a.property⟩) (by
constructor
· intro a b hab
apply Subtype.ext
have hl := congrArg Subtype.val hab
have hf := List.ofFn_injective hl
funext i
exact Fin.ext (congrFun hf i)
· intro xs
refine ⟨fromList J r xs.val xs.property.1 xs.property.2,?_⟩
apply Subtype.ext
exact ofFn_fromList J r xs.val xs.property.1 xs.property.2)
theorem weakCompositions_length (J r : ℕ) :
(weakCompositions J r).length=Nat.choose (J+r) r := by
classical
let : Fintype {xs : List ℕ // xs.length=J ∧ xs.sum≤r} :=
Fintype.ofEquiv (OrdinaryMonomial J r) (ordinaryListEquiv J r)
have hset : (weakCompositions J r).toFinset =
(Finset.univ : Finset {xs : List ℕ // xs.length=J ∧ xs.sum≤r}).image Subtype.val := by
ext xs
simp only [List.mem_toFinset,Finset.mem_image,Finset.mem_univ,true_and]
constructor
· intro hxs
exact ⟨⟨xs,(mem_weakCompositions J r xs).mp hxs⟩,rfl⟩
· rintro ⟨ys,rfl⟩
exact (mem_weakCompositions J r ys.val).mpr ys.property
calc
_ = (weakCompositions J r).toFinset.card :=
(List.toFinset_card_of_nodup (weakCompositions_nodup J r)).symm
_ = Fintype.card {xs : List ℕ // xs.length=J ∧ xs.sum≤r} := by
rw [hset,Finset.card_image_of_injective _ Subtype.val_injective,Finset.card_univ]
_ = Fintype.card (OrdinaryMonomial J r) := Fintype.card_congr (ordinaryListEquiv J r).symm
_ = _ := BasisFeatureProof.ordinary_card J r
end BasisEnumerationProof
end GenericGroupWE.Main
end
section
-- Source: WitnessEncryption.BasisSparseSubsets
namespace GenericGroupWE.Main
namespace BasisSubsetProof
open scoped BigOperators
/-- Descending sparse supports, extending only below the explicit degree cap. -/
def smallSubsets : ℕ → ℕ → List (List ℕ)
| 0, _ => [[]]
| N+1, d => smallSubsets N d ++
((smallSubsets N d).filter (fun xs => decide (xs.length < d))).map (fun xs => N::xs)
theorem mem_smallSubsets (N d : ℕ) (xs : List ℕ) :
xs∈smallSubsets N d ↔ xs.Pairwise (fun i j => j < i) ∧
(∀ i∈xs,i < N) ∧ xs.length ≤ d := by
induction N generalizing xs with
| zero =>
simp only [smallSubsets,List.mem_singleton]
constructor
· rintro rfl; simp
· rintro ⟨hp,hbound,hlen⟩
cases xs with
| nil => rfl
| cons i xs => have h := hbound i (by simp); omega
| succ N ih =>
constructor
· intro h
rcases List.mem_append.mp h with h | h
· obtain ⟨hp,hbound,hlen⟩ := (ih _).mp h
exact ⟨hp,fun i hi => Nat.lt_succ_of_lt (hbound i hi),hlen⟩
· obtain ⟨ys,hys,rfl⟩ := List.mem_map.mp h
obtain ⟨hys,hguard⟩ := List.mem_filter.mp hys
obtain ⟨hp,hbound,hlen⟩ := (ih _).mp hys
have hg : ys.length < d := of_decide_eq_true hguard
refine ⟨List.pairwise_cons.mpr ⟨hbound,hp⟩,?_,by simp; omega⟩
intro i hi
rcases List.mem_cons.mp hi with rfl | hi
· omega
· exact Nat.lt_succ_of_lt (hbound i hi)
· rintro ⟨hp,hbound,hlen⟩
cases xs with
| nil =>
apply List.mem_append.mpr
exact Or.inl ((ih _).mpr ⟨by simp,by simp,by simp⟩)
| cons i xs =>
have hiN := hbound i (by simp)
have hp' := List.pairwise_cons.mp hp
by_cases hi : i=N
· subst i
apply List.mem_append.mpr
apply Or.inr
apply List.mem_map.mpr
refine ⟨xs,?_,rfl⟩
apply List.mem_filter.mpr
refine ⟨(ih _).mpr ⟨hp'.2,hp'.1,?_⟩,?_⟩
· simp only [List.length_cons] at hlen; omega
· apply decide_eq_true
simp only [List.length_cons] at hlen; omega
· have hiLt : i < N := by omega
apply List.mem_append.mpr
apply Or.inl
apply (ih _).mpr
refine ⟨hp,?_,hlen⟩
intro j hj
rcases List.mem_cons.mp hj with rfl | hj
· exact hiLt
· exact (hp'.1 j hj).trans hiLt
/-- Proof-side subset code only; the sparse enumerator never executes powers. -/
def maskCode : List ℕ → ℕ
| [] => 0
| i::xs => 2^i+maskCode xs
theorem maskCode_bound (N d : ℕ) (xs : List ℕ) (hx : xs∈smallSubsets N d) :
maskCode xs < 2^N := by
induction N generalizing xs with
| zero =>
have heq := List.mem_singleton.mp hx
subst xs
simp [maskCode]
| succ N ih =>
rcases List.mem_append.mp hx with hx | hx
· have hh := ih xs hx
have hp : 0 < 2^N := by positivity
rw [pow_succ]
omega
· obtain ⟨ys,hys,rfl⟩ := List.mem_map.mp hx
have hh := ih ys (List.mem_filter.mp hys).1
rw [maskCode,pow_succ]
omega
theorem smallSubsets_maskCode_order (N d : ℕ) :
(smallSubsets N d).Pairwise (fun xs ys => maskCode xs < maskCode ys) := by
induction N with
| zero => simp [smallSubsets]
| succ N ih =>
apply List.pairwise_append.mpr
refine ⟨ih,?_,?_⟩
· apply List.pairwise_map.mpr
exact (ih.filter _).imp (fun {xs ys} h => by dsimp only [maskCode]; omega)
· intro xs hxs ys hys
obtain ⟨zs,hzs,rfl⟩ := List.mem_map.mp hys
have hh := maskCode_bound N d xs hxs
dsimp only [maskCode]
omega
def supportFin (N : ℕ) (xs : List ℕ) : Finset (Fin N) :=
Finset.univ.filter (fun i => i.val∈xs)
theorem supportFin_image (N : ℕ) (xs : List ℕ) (hbound : ∀ i∈xs,i < N) :
(supportFin N xs).image Fin.val=xs.toFinset := by
ext i
simp only [supportFin,Finset.mem_image,Finset.mem_filter,Finset.mem_univ,
true_and,List.mem_toFinset]
constructor
· rintro ⟨j,hj,rfl⟩; exact hj
· intro hi; exact ⟨⟨i,hbound i hi⟩,hi,rfl⟩
theorem supportFin_card (N : ℕ) (xs : List ℕ) (hn : xs.Nodup) (hbound : ∀ i∈xs,i < N) :
(supportFin N xs).card=xs.length := by
rw [←Finset.card_image_of_injective _ Fin.val_injective,supportFin_image N xs hbound]
exact List.toFinset_card_of_nodup hn
def asBit (N d : ℕ) (xs : List ℕ) (hp : xs.Pairwise (fun i j => j < i))
(hbound : ∀ i∈xs,i < N) (hlen : xs.length ≤ d) : BitMonomial N d :=
⟨supportFin N xs,by
have hn : xs.Nodup := hp.imp (fun {i j} h => Nat.ne_of_gt h)
rw [supportFin_card N xs hn hbound]
exact hlen⟩
theorem sparse_eq_of_support {xs ys : List ℕ}
(hp : xs.Pairwise (fun i j => j < i)) (hq : ys.Pairwise (fun i j => j < i))
(heq : xs.toFinset=ys.toFinset) : xs=ys := by
apply hp.sortedGT.eq_of_mem_iff hq.sortedGT
intro i
simp only [←List.mem_toFinset,heq]
theorem maskCode_sum (xs : List ℕ) : maskCode xs=(xs.map (fun i => 2^i)).sum := by
induction xs with
| nil => rfl
| cons i xs ih => simp only [maskCode,List.map_cons,List.sum_cons,ih]
theorem asBit_code (N d : ℕ) (xs : List ℕ) (hp : xs.Pairwise (fun i j => j < i))
(hbound : ∀ i∈xs,i < N) (hlen : xs.length ≤ d) :
subsetCode (asBit N d xs hp hbound hlen).val=maskCode xs := by
have hn : xs.Nodup := hp.imp (fun {i j} h => Nat.ne_of_gt h)
change (∑ i∈supportFin N xs,2^i.val)=maskCode xs
calc
_ = ∑ n∈(supportFin N xs).image Fin.val,2^n := by
rw [Finset.sum_image Fin.val_injective.injOn]
_ = ∑ n∈xs.toFinset,2^n := by rw [supportFin_image N xs hbound]
_ = (xs.map (fun n => 2^n)).sum := List.sum_toFinset _ hn
_ = _ := (maskCode_sum xs).symm
def enumeratedColumns (N d : ℕ) : List (BitMonomial N d) :=
(smallSubsets N d).attach.map (fun xs =>
asBit N d xs.val ((mem_smallSubsets N d xs.val).mp xs.property).1
((mem_smallSubsets N d xs.val).mp xs.property).2.1
((mem_smallSubsets N d xs.val).mp xs.property).2.2)
theorem enumeratedColumns_complete {N d : ℕ} (S : BitMonomial N d) : S∈enumeratedColumns N d := by
classical
let T := S.val.image Fin.val
let xs := T.sort (fun a b => b ≤ a)
have hp : xs.Pairwise (fun a b => b < a) := (Finset.sortedGT_sort T).pairwise
have hb : ∀ i∈xs,i < N := by
intro i hi
have ht : i∈T := (Finset.mem_sort _).mp hi
obtain ⟨j,hj,rfl⟩ := Finset.mem_image.mp ht
exact j.isLt
have hl : xs.length ≤ d := by
change (T.sort (fun a b => b ≤ a)).length ≤ d
rw [Finset.length_sort]
change (S.val.image Fin.val).card ≤ d
rw [Finset.card_image_of_injective _ Fin.val_injective]
exact S.property
have hm : xs∈smallSubsets N d := (mem_smallSubsets N d xs).mpr ⟨hp,hb,hl⟩
have heq : supportFin N xs=S.val := by
apply (Finset.image_inj Fin.val_injective).mp
rw [supportFin_image N xs hb]
exact Finset.sort_toFinset _ _
apply List.mem_map.mpr
refine ⟨⟨xs,hm⟩,by simp,?_⟩
exact Subtype.ext heq
theorem enumeratedColumns_order (N d : ℕ) :
(enumeratedColumns N d).Pairwise (fun S T => subsetCode S.val < subsetCode T.val) := by
apply List.pairwise_map.mpr
have hraw := smallSubsets_maskCode_order N d
have hatt := (List.pairwise_map (R := fun xs ys : List ℕ => maskCode xs < maskCode ys)
(f := fun xs : {xs // xs∈smallSubsets N d} => xs.val)
(l := (smallSubsets N d).attach)).mp
(by simpa only [List.attach_map_subtype_val] using hraw)
exact hatt.imp (fun {xs ys} h => by rw [asBit_code,asBit_code]; exact h)
theorem code_injective_of_complete_order {α : Type*} (l : List α) (code : α → ℕ)
(hcomplete : ∀ a,a∈l) (horder : l.Pairwise (fun a b => code a < code b)) :
Function.Injective code := by
intro a b hab
obtain ⟨i,hi,hia⟩ := List.mem_iff_getElem.mp (hcomplete a)
obtain ⟨j,hj,hjb⟩ := List.mem_iff_getElem.mp (hcomplete b)
rcases Nat.lt_trichotomy i j with hij | hij | hij
· have hh := List.pairwise_iff_getElem.mp horder i j hi hj hij
rw [hia,hjb,hab] at hh
exact False.elim (Nat.lt_irrefl _ hh)
· subst j
exact hia.symm.trans hjb
· have hh := List.pairwise_iff_getElem.mp horder j i hj hi hij
rw [hia,hjb,hab] at hh
exact False.elim (Nat.lt_irrefl _ hh)
theorem enumeratedColumns_eq (N d : ℕ) : enumeratedColumns N d=columnList N d := by
classical
let r : BitMonomial N d → BitMonomial N d → Prop :=
fun S T => subsetCode S.val ≤ subsetCode T.val
let : Std.Total r := ⟨fun a b => Nat.le_total _ _⟩
let : IsTrans (BitMonomial N d) r := ⟨fun a b c hab hbc => hab.trans hbc⟩
have hsorted := enumeratedColumns_order N d
have hcanonical : (columnList N d).Pairwise r := by
unfold columnList
exact List.pairwise_mergeSort' r _
have hnodup : (enumeratedColumns N d).Nodup := hsorted.imp (fun {a b} h hab => by
subst b
exact Nat.lt_irrefl _ h)
have hperm : (enumeratedColumns N d).Perm (columnList N d) :=
(List.perm_ext_iff_of_nodup hnodup (BasisFeatureProof.columnList_nodup N d)).mpr
(fun a => iff_of_true (enumeratedColumns_complete a) (BasisFeatureProof.mem_columnList a))
have hinj := code_injective_of_complete_order (enumeratedColumns N d)
(fun S => subsetCode S.val) enumeratedColumns_complete hsorted
exact List.Perm.eq_of_pairwise (fun a b _ _ hab hba => hinj (Nat.le_antisymm hab hba))
(hsorted.imp Nat.le_of_lt) hcanonical hperm
end BasisSubsetProof
end GenericGroupWE.Main
end
section
-- Source: WitnessEncryption.BasisFeatureEnumeration
namespace GenericGroupWE.Main
namespace BasisEnumerationOrderProof
open scoped BigOperators
open BasisEnumerationProof
/-- Proof-side positional code; the executable enumerator never calls it. -/
def digitCode (r : ℕ) : List ℕ → ℕ
| [] => 0
| i::xs => i+(r+1)*digitCode r xs
theorem digitCode_bound (r : ℕ) (xs : List ℕ) (hx : ∀ i∈xs,i ≤ r) :
digitCode r xs < (r+1)^xs.length := by
induction xs with
| nil => simp [digitCode]
| cons i xs ih =>
have hi := hx i (by simp)
have htail : ∀ j∈xs,j ≤ r := fun j hj => hx j (by simp [hj])
have hh := ih htail
have hp := Nat.mul_le_mul_left (r+1) (Nat.succ_le_of_lt hh)
rw [digitCode,List.length_cons,pow_succ]
nlinarith
theorem weak_digitCode_bound (J r : ℕ) (xs : List ℕ) (hx : xs∈weakCompositions J r) :
digitCode r xs < (r+1)^J := by
obtain ⟨hlen,hsum⟩ := (mem_weakCompositions J r xs).mp hx
have hbound : ∀ i∈xs,i ≤ r := fun i hi => (List.le_sum_of_mem hi).trans hsum
simpa only [hlen] using digitCode_bound r xs hbound
theorem weak_digitCode_order (J r : ℕ) :
(weakCompositions J r).Pairwise (fun xs ys => digitCode r xs < digitCode r ys) := by
induction J with
| zero => simp [weakCompositions]
| succ J ih =>
apply List.pairwise_flatMap.mpr
constructor
· intro xs hxs
apply List.pairwise_map.mpr
exact List.pairwise_lt_range.imp (fun {i j} hij => by dsimp only [digitCode]; omega)
· exact ih.imp (fun {xs ys} hxy a ha b hb => by
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp ha
obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hb
have hir : i ≤ r := by
simp only [List.mem_range] at hi
have hh := Nat.sub_le r xs.sum
omega
have hp := Nat.mul_le_mul_left (r+1) (Nat.succ_le_of_lt hxy)
dsimp only [digitCode]
nlinarith)
theorem digitCode_ofFn (J r : ℕ) (f : Fin J → ℕ) :
digitCode r (List.ofFn f)=∑ i : Fin J,f i*(r+1)^i.val := by
induction J with
| zero => simp [digitCode]
| succ J ih =>
rw [List.ofFn_succ,digitCode,ih,Fin.sum_univ_succ]
simp only [Fin.val_zero,pow_zero,mul_one,Fin.val_succ,pow_succ]
rw [Finset.mul_sum]
congr 1
apply Finset.sum_congr rfl
intro i hi
ring
theorem exponentCode_eq_digitCode {J r : ℕ} (a : OrdinaryMonomial J r) :
exponentCode a=digitCode r (List.ofFn (fun i => (a.val i).val)) :=
(digitCode_ofFn J r (fun i => (a.val i).val)).symm
end BasisEnumerationOrderProof
end GenericGroupWE.Main
namespace GenericGroupWE.Main
namespace BasisFeatureEnumerationProof
open scoped BigOperators
open BasisEnumerationProof BasisEnumerationOrderProof BasisSubsetProof
def enumeratedOrdinary (J r : ℕ) : List (OrdinaryMonomial J r) :=
(weakCompositions J r).attach.map (fun xs => fromList J r xs.val
((mem_weakCompositions J r xs.val).mp xs.property).1
((mem_weakCompositions J r xs.val).mp xs.property).2)
theorem enumeratedOrdinary_complete {J r : ℕ} (a : OrdinaryMonomial J r) :
a∈enumeratedOrdinary J r := by
let xs := List.ofFn (fun i => (a.val i).val)
have hl : xs.length=J := List.length_ofFn
have hs : xs.sum ≤ r := by simpa only [xs,List.sum_ofFn] using a.property
have hm : xs∈weakCompositions J r := (mem_weakCompositions J r xs).mpr ⟨hl,hs⟩
apply List.mem_map.mpr
refine ⟨⟨xs,hm⟩,by simp,?_⟩
apply Subtype.ext
funext i
apply Fin.ext
change xs.getD i.val 0=(a.val i).val
rw [List.getD_eq_getElem xs 0 (by simpa only [xs,List.length_ofFn] using i.isLt)]
simp [xs]
theorem enumeratedOrdinary_order (J r : ℕ) :
(enumeratedOrdinary J r).Pairwise (fun a b => exponentCode a < exponentCode b) := by
apply List.pairwise_map.mpr
have hatt := (List.pairwise_map (R := fun xs ys : List ℕ => digitCode r xs < digitCode r ys)
(f := fun xs : {xs // xs∈weakCompositions J r} => xs.val)
(l := (weakCompositions J r).attach)).mp
(by simpa only [List.attach_map_subtype_val] using weak_digitCode_order J r)
exact hatt.imp (fun {xs ys} h => by
rw [exponentCode_eq_digitCode,ofFn_fromList,exponentCode_eq_digitCode,ofFn_fromList]
exact h)
theorem exponentCode_bound {J r : ℕ} (a : OrdinaryMonomial J r) : exponentCode a < (r+1)^J := by
rw [exponentCode_eq_digitCode]
apply weak_digitCode_bound
apply (mem_weakCompositions J r _).mpr
simpa only [List.length_ofFn,List.sum_ofFn,true_and] using a.property
def enumeratedWeights (N d : ℕ) : List (WeightLabel N d) :=
(List.range (N*((rankTarget N d)^2+weightDegree N)+1)).attach.flatMap fun t =>
(enumeratedOrdinary ((rankTarget N d)^2) (weightDegree N)).map
(fun a => (⟨t.val,List.mem_range.mp t.property⟩,a))
def weightCode {N d : ℕ} (h : WeightLabel N d) : ℕ :=
h.1.val*(weightDegree N+1)^((rankTarget N d)^2)+exponentCode h.2
theorem enumeratedWeights_complete {N d : ℕ} (h : WeightLabel N d) : h∈enumeratedWeights N d := by
apply List.mem_flatMap.mpr
refine ⟨⟨h.1.val,List.mem_range.mpr h.1.isLt⟩,by simp,?_⟩
apply List.mem_map.mpr
exact ⟨h.2,enumeratedOrdinary_complete _,rfl⟩
theorem enumeratedWeights_order (N d : ℕ) :
(enumeratedWeights N d).Pairwise (fun a b => weightCode a < weightCode b) := by
apply List.pairwise_flatMap.mpr
constructor
· intro t ht
apply List.pairwise_map.mpr
exact (enumeratedOrdinary_order _ _).imp (fun {a b} h => by dsimp only [weightCode]; omega)
· have hatt := (List.pairwise_map (R := fun a b : ℕ => a < b)
(f := fun t : {t // t∈List.range (N*((rankTarget N d)^2+weightDegree N)+1)} => t.val)
(l := (List.range (N*((rankTarget N d)^2+weightDegree N)+1)).attach)).mp
(by simpa only [List.attach_map_subtype_val] using
(List.pairwise_lt_range (n := N*((rankTarget N d)^2+weightDegree N)+1)))
exact hatt.imp (fun {t u} htu a ha b hb => by
obtain ⟨alpha,halpha,rfl⟩ := List.mem_map.mp ha
obtain ⟨beta,hbeta,rfl⟩ := List.mem_map.mp hb
have hbound := exponentCode_bound alpha
have hp := Nat.mul_le_mul_right ((weightDegree N+1)^((rankTarget N d)^2))
(Nat.succ_le_of_lt htu)
dsimp only [weightCode]
nlinarith)
def enumeratedRows (N d : ℕ) : List (StackRow N d) :=
(enumeratedWeights N d).flatMap (fun h => (enumeratedColumns N d).map (fun S => (h,S)))
theorem enumeratedRows_complete {N d : ℕ} (row : StackRow N d) : row∈enumeratedRows N d := by
apply List.mem_flatMap.mpr
refine ⟨row.1,enumeratedWeights_complete _,?_⟩
exact List.mem_map.mpr ⟨row.2,enumeratedColumns_complete _,rfl⟩
theorem subsetCode_bound {N d : ℕ} (S : BitMonomial N d) : subsetCode S.val < 2^N := by
obtain ⟨xs,hxs,heq⟩ := List.mem_map.mp (enumeratedColumns_complete S)
rw [←heq,asBit_code]
exact maskCode_bound N d xs.val xs.property
theorem enumeratedRows_order (N d : ℕ) :
(enumeratedRows N d).Pairwise (fun a b => rowCode a < rowCode b) := by
apply List.pairwise_flatMap.mpr
constructor
· intro h hh
apply List.pairwise_map.mpr
exact (enumeratedColumns_order N d).imp (fun {S T} hST => by dsimp only [rowCode]; omega)
· exact (enumeratedWeights_order N d).imp (fun {h k} hhk a ha b hb => by
obtain ⟨S,hS,rfl⟩ := List.mem_map.mp ha
obtain ⟨T,hT,rfl⟩ := List.mem_map.mp hb
have hbound := subsetCode_bound S
have hp := Nat.mul_le_mul_right (2^N) (Nat.succ_le_of_lt hhk)
change weightCode h*(2^N)+subsetCode S.val < weightCode k*(2^N)+subsetCode T.val
nlinarith)
theorem enumeratedRows_eq (N d : ℕ) : enumeratedRows N d=rowList N d := by
classical
let r : StackRow N d → StackRow N d → Prop := fun a b => rowCode a ≤ rowCode b
let : Std.Total r := ⟨fun a b => Nat.le_total _ _⟩
let : IsTrans (StackRow N d) r := ⟨fun a b c hab hbc => hab.trans hbc⟩
have hsorted := enumeratedRows_order N d
have hcanonical : (rowList N d).Pairwise r := by
unfold rowList
exact List.pairwise_mergeSort' r _
have hnodup : (enumeratedRows N d).Nodup := hsorted.imp (fun {a b} h hab => by
subst b
exact Nat.lt_irrefl _ h)
have hperm : (enumeratedRows N d).Perm (rowList N d) :=
(List.perm_ext_iff_of_nodup hnodup (BasisFeatureProof.rowList_nodup N d)).mpr
(fun a => iff_of_true (enumeratedRows_complete a) (BasisFeatureProof.mem_rowList a))
have hinj := code_injective_of_complete_order (enumeratedRows N d)
rowCode enumeratedRows_complete hsorted
exact List.Perm.eq_of_pairwise (fun a b _ _ hab hba => hinj (Nat.le_antisymm hab hba))
(hsorted.imp Nat.le_of_lt) hcanonical hperm
end BasisFeatureEnumerationProof
end GenericGroupWE.Main
end
section
-- Source: WitnessEncryption.Runtime.Binary.Normalize
namespace WitnessEncryption.Runtime.Binary
open OAI.ThreeMachine.StackCompiler
open WitnessEncryption.Runtime.ListPrimitives
open GenericGroupWE.Main.SamplingRuntime
namespace NormalizeProof
abbrev Bits := List Bool
/-- Traverse from the high end, retaining bits once a one has been seen. -/
def step (x : Bool × Bits) : Bits :=
if x.1 then x.1::x.2 else if x.2.isEmpty then [] else x.1::x.2
def trim : Bits → Bits
| [] => []
| b::bs => step (b,trim bs)
theorem trim_eq_bits (bs : Bits) : trim bs = (value bs).bits := by
induction bs with
| nil => rfl
| cons b bs ih =>
cases b with
| true => simpa [trim,step,ih,value_cons,Nat.add_comm] using (Nat.bit1_bits (value bs)).symm
| false =>
by_cases hz : value bs=0
· simp [trim,step,ih,value_cons,hz]
· have hne : (value bs).bits≠[] := by
intro h
have hv := congrArg value h
exact hz (by simpa using hv)
have he : (value bs).bits.isEmpty=false := by
cases h : (value bs).bits with
| nil => exact (hne h).elim
| cons b tail => rfl
simp [trim,step,ih,he,value_cons,Nat.bit0_bits _ hz]
theorem reverse_fold (bs acc : Bits) :
(bs.reverse.foldl (fun s b => step (b,s)) acc) =
bs.foldr (fun b s => step (b,s)) acc := by
induction bs with
| nil => rfl
| cons b bs ih => simp only [List.reverse_cons,List.foldl_append,List.foldl_cons,
List.foldl_nil,List.foldr_cons,ih]
theorem trim_eq_fold (bs : Bits) :
bs.reverse.foldl (fun s b => step (b,s)) [] = trim bs := by
rw [reverse_fold]
induction bs with
| nil => rfl
| cons b bs ih => simp only [List.foldr_cons,trim,ih]
theorem step_length (b : Bool) (s : Bits) : (step (b,s)).length ≤ s.length+1 := by
cases b <;> cases s <;> simp [step]
theorem fold_length (bs s : Bits) :
(bs.foldl (fun s b => step (b,s)) s).length ≤ s.length+bs.length := by
induction bs generalizing s with
| nil => simp
| cons b bs ih =>
have h := ih (step (b,s))
have hs := step_length b s
simp only [List.foldl_cons,List.length_cons]
omega
def consR : Realizer (fun x : Bool × Bits => x.1::x.2) := Realizer.cons
def stepR : Realizer step :=
iteR Realizer.fst consR (iteR (Realizer.snd.comp bitsIsEmptyR) Realizer.nil consR)
theorem step_certified : Certified stepR :=
ite_certified Certified.fst cons_certified
(ite_certified (Certified.snd.comp bitsIsEmpty_certified) nil_certified cons_certified)
theorem fold_certified : Certified stepR.fold := by
apply Certified.fold step_certified
refine ⟨10,1,?_⟩
intro x j hj
let bs := (x.1.take j).foldl (fun s b => step (b,s)) x.2
have hw := fold_length (x.1.take j) x.2
change bs.length ≤ x.2.length+(x.1.take j).length at hw
have hv := volume_list_le bs 3 (fun b _ => volume_bool b)
have hx := length_le_volume x.1
have hs := length_le_volume x.2
have hp := List.length_take_le' j x.1
change volume bs ≤ 10*(volume x+2)^1
simp only [pow_one,volume_prod]
omega
end NormalizeProof
/-- Canonical little-endian binary encoding, without converting its value to unary. -/
def normalize : List Bool → List Bool := NormalizeProof.trim
theorem normalize_eq_bits (bs : List Bool) : normalize bs = (value bs).bits :=
NormalizeProof.trim_eq_bits bs
def normalizeR : Realizer normalize :=
((reverseR.pair Realizer.nil).comp NormalizeProof.stepR.fold).congr
NormalizeProof.trim_eq_fold
theorem normalize_certified : Certified normalizeR :=
((reverse_certified.pair nil_certified).comp NormalizeProof.fold_certified).congr
NormalizeProof.trim_eq_fold
end WitnessEncryption.Runtime.Binary
#print axioms WitnessEncryption.Runtime.Binary.normalize_eq_bits
#print axioms WitnessEncryption.Runtime.Binary.normalizeR
#print axioms WitnessEncryption.Runtime.Binary.normalize_certified
end
section
-- Source: WitnessEncryption.Runtime.Features.Enumeration
namespace WitnessEncryption.Runtime.FeatureParameters
open OAI.ThreeMachine.StackCompiler
open WitnessEncryption.Runtime.FeatureMetadata
def mulR : Realizer (fun x : ℕ × ℕ => x.1*x.2) :=
(((Realizer.fst.pair (Realizer.snd.comp Prime.UnaryPowerProof.unitsR)).comp
(ListMap.mapR (Realizer.fst : Realizer (Prod.fst : ℕ × Unit → ℕ)))).comp sumR).congr
(fun x => by simp only [Function.comp_apply,List.map_replicate,List.sum_replicate,
smul_eq_mul,Nat.mul_comm])
theorem mul_certified : Certified mulR := by
unfold mulR
apply Certified.congr
exact (((Certified.fst.pair (Certified.snd.comp Prime.UnaryPowerProof.unitsR_certified)).comp
(ListMap.map_certified Certified.fst)).comp sum_certified)
theorem sum_choose (n d : ℕ) : ((List.range n).map (fun i => i.choose d)).sum=n.choose (d+1) := by
induction n with
| zero => simp
| succ n ih =>
simp only [List.range_succ,List.map_append,List.sum_append,List.map_cons,List.map_nil,
List.sum_cons,List.sum_nil,Nat.add_zero,ih,Nat.choose_succ_succ,Nat.succ_eq_add_one]
omega
/-- The degree is a compile-time parameter; there is no uniform variable-degree claim. -/
def chooseR : (d : ℕ) → Realizer (fun n : ℕ => n.choose d)
| 0 => (Realizer.constant 1).congr (fun n => by simp)
| d+1 => ((((Realizer.constant ()).pair rangeR).comp
(ListMap.mapR (Realizer.snd.comp (chooseR d)))).comp sumR).congr
(fun n => by simp only [Function.comp_apply,sum_choose])
theorem choose_certified (d : ℕ) : Certified (chooseR d) := by
induction d with
| zero => exact (Certified.constant 1).congr (fun n => by simp)
| succ d ih =>
simp only [chooseR]
apply Certified.congr
exact ((((Certified.constant ()).pair range_certified).comp
(ListMap.map_certified (Certified.snd.comp ih))).comp sum_certified)
def bitsStep (x : Unit × List Bool) : List Bool := Binary.add x.2 [true]
def bitsStepR : Realizer bitsStep :=
(Realizer.snd.pair (Realizer.constant [true])).comp Binary.addR
theorem bitsStep_certified : Certified bitsStepR :=
(Certified.snd.pair (Certified.constant [true])).comp Binary.add_certified
theorem bits_fold_value (us : List Unit) (bs : List Bool) :
Binary.value (us.foldl (fun bs u => bitsStep (u,bs)) bs)=Binary.value bs+us.length := by
induction us generalizing bs with
| nil => simp
| cons u us ih =>
rw [List.foldl_cons,ih]
simp only [bitsStep,Binary.value_add,Binary.value_cons,Binary.value_nil,if_true,
Nat.mul_zero,Nat.add_zero,List.length_cons]
omega
theorem bits_fold_length (us : List Unit) (bs : List Bool) :
(us.foldl (fun bs u => bitsStep (u,bs)) bs).length ≤ bs.length+2*us.length := by
induction us generalizing bs with
| nil => simp
| cons u us ih =>
have hh := ih (bitsStep (u,bs))
have ha := Binary.length_add bs [true]
simp only [List.length_cons,List.length_nil] at ha ⊢
change (us.foldl (fun bs u => bitsStep (u,bs)) (bitsStep (u,bs))).length ≤ _
have hm : max bs.length 1 ≤ bs.length+1 := by omega
have hstep : (bitsStep (u,bs)).length ≤ bs.length+2 := by
change (Binary.add bs [true]).length ≤ _
omega
omega
theorem bitsFold_certified : Certified bitsStepR.fold := by
apply Certified.fold bitsStep_certified
refine ⟨20,1,?_⟩
intro x j hj
have hh := bits_fold_length (x.1.take j) x.2
have ht := List.length_take_le' j x.1
have hl := length_le_volume x.1
have hb := length_le_volume x.2
have hv := volume_list_le ((x.1.take j).foldl (fun bs u => bitsStep (u,bs)) x.2)
3 (fun b _ => volume_bool b)
change volume ((x.1.take j).foldl (fun bs u => bitsStep (u,bs)) x.2) ≤ _
simp only [pow_one,volume_prod]
omega
def bitsR : Realizer (Nat.bits : ℕ → List Bool) :=
((((Prime.UnaryPowerProof.unitsR.pair (Realizer.constant [])).comp bitsStepR.fold).comp
Binary.normalizeR)).congr (fun n => by
simp only [Function.comp_apply,Binary.normalize_eq_bits,bits_fold_value,
Binary.value_nil,List.length_replicate,Nat.zero_add])
theorem bits_certified : Certified bitsR := by
unfold bitsR
apply Certified.congr
exact (((Prime.UnaryPowerProof.unitsR_certified.pair (Certified.constant [])).comp
bitsFold_certified).comp Binary.normalize_certified)
theorem log_two_bits (n : ℕ) : Nat.log 2 n=n.bits.length-1 := by
induction n using Nat.binaryRec' with
| zero => simp
| bit b n hn ih =>
rw [Nat.bits_append_bit n b hn]
by_cases hz : n=0
· subst n
have hb := hn rfl
subst b
rfl
· rw [Nat.log_two_bit hz,ih]
have hp : 0<n.bits.length := by
rw [Nat.size_eq_bits_len]
exact Nat.size_pos.mpr (Nat.pos_of_ne_zero hz)
simp only [List.length_cons]
omega
def logR : Realizer (fun n : ℕ => Nat.log 2 n) :=
(((bitsR.comp lengthR).pair (Realizer.constant 1)).comp Realizer.sub).congr
(fun n => (log_two_bits n).symm)
theorem log_certified : Certified logR :=
((((bits_certified.comp length_certified).pair (Certified.constant 1)).comp
sub_certified)).congr (fun n => (log_two_bits n).symm)
def squareTestR : Realizer (fun x : ℕ × ℕ => decide (x.2*x.2 ≤ x.1)) :=
(((Realizer.snd.pair Realizer.snd).comp mulR).pair Realizer.fst).comp Realizer.le
theorem squareTest_certified : Certified squareTestR :=
(((Certified.snd.pair Certified.snd).comp mul_certified).pair Certified.fst).comp
NatPrimitives.le_certified
theorem sqrt_filter (n : ℕ) :
(List.range (n+1)).filter (fun k => decide (k*k ≤ n))=List.range (Nat.sqrt n+1) := by
apply List.SortedLT.eq_of_mem_iff
(List.pairwise_lt_range.filter _ |>.sortedLT) (List.sortedLT_range _)
intro k
simp only [List.mem_filter,List.mem_range,decide_eq_true_eq]
have hsq := Nat.sqrt_le_self n
constructor
· rintro ⟨hkn,hkk⟩
have hk := Nat.le_sqrt.mpr hkk
omega
· intro hk
have hkk := Nat.le_sqrt.mp (show k ≤ Nat.sqrt n by omega)
constructor <;> omega
def sqrtR : Realizer Nat.sqrt :=
((((Realizer.id.pair (Realizer.succ.comp rangeR)).comp
(filterR squareTestR)).comp lengthR).comp Realizer.pred).congr
(fun n => by simp only [Function.comp_apply,id_eq,sqrt_filter,List.length_range,Nat.pred_eq_sub_one,Nat.add_sub_cancel])
theorem sqrt_certified : Certified sqrtR := by
unfold sqrtR
apply Certified.congr
exact ((((Certified.identity.pair (NatPrimitives.succ_certified.comp range_certified)).comp
(filter_certified squareTest_certified)).comp length_certified).comp NatPrimitives.pred_certified)
def maxOneR : Realizer (fun n : ℕ => max 1 n) :=
((Realizer.positive.pair Realizer.id).comp
(Realizer.id.choose (Realizer.constant 1))).congr (fun n => by
cases n <;> simp)
theorem maxOne_certified : Certified maxOneR := by
unfold maxOneR
apply Certified.congr
exact ((NatPrimitives.positive_certified.pair Certified.identity).comp
(Certified.identity.choose (Certified.constant 1)))
def weightDegreeR : Realizer GenericGroupWE.Main.weightDegree :=
(((Realizer.succ.comp Realizer.succ).comp logR).comp sqrtR).comp maxOneR
theorem weightDegree_certified : Certified weightDegreeR :=
(((NatPrimitives.succ_certified.comp NatPrimitives.succ_certified).comp log_certified).comp
sqrt_certified).comp maxOne_certified
def rankTargetR (d : ℕ) : Realizer (fun N => GenericGroupWE.Main.rankTarget N d) :=
((weightDegreeR.pair (Realizer.constant (2*d))).comp Realizer.add).comp (chooseR d)
theorem rankTarget_certified (d : ℕ) : Certified (rankTargetR d) :=
(((weightDegree_certified.pair (Certified.constant (2*d))).comp NatPrimitives.add_certified).comp
(choose_certified d))
def tupleWidthR (d : ℕ) : Realizer (fun N => (GenericGroupWE.Main.rankTarget N d)^2) :=
(((rankTargetR d).pair (rankTargetR d)).comp mulR).congr (fun _N => (pow_two _).symm)
theorem tupleWidth_certified (d : ℕ) : Certified (tupleWidthR d) :=
((((rankTarget_certified d).pair (rankTarget_certified d)).comp mul_certified)).congr
(fun _N => (pow_two _).symm)
def samplesR (d : ℕ) : Realizer (fun N =>
N*((GenericGroupWE.Main.rankTarget N d)^2+GenericGroupWE.Main.weightDegree N)+1) :=
((Realizer.id.pair (((tupleWidthR d).pair weightDegreeR).comp Realizer.add)).comp mulR).comp
Realizer.succ
theorem samples_certified (d : ℕ) : Certified (samplesR d) :=
((Certified.identity.pair (((tupleWidth_certified d).pair weightDegree_certified).comp
NatPrimitives.add_certified)).comp mul_certified).comp NatPrimitives.succ_certified
def maxTwoR : Realizer (fun n : ℕ => max 2 n) :=
((((Realizer.constant 2).pair Realizer.id).comp Realizer.le).pair Realizer.id).comp
(Realizer.id.choose (Realizer.constant 2)) |>.congr (fun n => by
by_cases h : 2 ≤ n <;> simp [max_def,h])
theorem maxTwo_certified : Certified maxTwoR := by
unfold maxTwoR
apply Certified.congr
exact (((((Certified.constant 2).pair Certified.identity).comp NatPrimitives.le_certified).pair
Certified.identity).comp (Certified.identity.choose (Certified.constant 2)))
end WitnessEncryption.Runtime.FeatureParameters
namespace WitnessEncryption.Runtime.FeatureEnumeration
open OAI.ThreeMachine.StackCompiler
open WitnessEncryption.Runtime.FeatureMetadata
open WitnessEncryption.Runtime.ListPrimitives
abbrev Tuples := List (List ℕ)
def consAtR : Realizer (fun x : List ℕ × ℕ => x.2::x.1) :=
(Realizer.snd.pair Realizer.fst).comp Realizer.cons
theorem consAt_certified : Certified consAtR :=
(Certified.snd.pair Certified.fst).comp cons_certified
def branchesR : Realizer (fun x : ℕ × List ℕ =>
(List.range (x.1-x.2.sum+1)).map (fun k => k::x.2)) :=
(Realizer.snd.pair ((((Realizer.fst.pair (Realizer.snd.comp sumR)).comp
Realizer.sub).comp Realizer.succ).comp rangeR)).comp (ListMap.mapR consAtR)
theorem branches_certified : Certified branchesR :=
(Certified.snd.pair ((((Certified.fst.pair (Certified.snd.comp sum_certified)).comp
sub_certified).comp NatPrimitives.succ_certified).comp range_certified)).comp
(ListMap.map_certified consAt_certified)
def weakLayerR : Realizer (fun x : ℕ × Tuples => x.2.flatMap fun xs =>
(List.range (x.1-xs.sum+1)).map (fun k => k::xs)) :=
((ListMap.mapR branchesR).comp flattenR).congr (fun x => by
simp only [Function.comp_apply,List.flatMap_def])
theorem weakLayer_certified : Certified weakLayerR := by
unfold weakLayerR
apply Certified.congr
exact ((ListMap.map_certified branches_certified).comp flatten_certified)
def shortTestR : Realizer (fun x : ℕ × List ℕ => decide (x.2.length < x.1)) :=
(((Realizer.snd.comp lengthR).comp Realizer.succ).pair Realizer.fst).comp
Realizer.le |>.congr (fun x => by simp only [Function.comp_apply,Nat.succ_le_iff])
theorem shortTest_certified : Certified shortTestR := by
unfold shortTestR
apply Certified.congr
exact ((((Certified.snd.comp length_certified).comp NatPrimitives.succ_certified).pair
Certified.fst).comp NatPrimitives.le_certified)
def prependR : Realizer (fun x : ℕ × List ℕ => x.1::x.2) := Realizer.cons
def subsetLayerR : Realizer (fun x : ℕ × (ℕ × Tuples) => x.2.2++
((x.2.2.filter (fun xs => decide (xs.length < x.1))).map (fun xs => x.2.1::xs))) :=
((Realizer.snd.comp Realizer.snd).pair
(((Realizer.snd.comp Realizer.fst).pair
((Realizer.fst.pair (Realizer.snd.comp Realizer.snd)).comp (filterR shortTestR))).comp
(ListMap.mapR prependR))).comp appendR
theorem subsetLayer_certified : Certified subsetLayerR :=
((Certified.snd.comp Certified.snd).pair
(((Certified.snd.comp Certified.fst).pair
((Certified.fst.pair (Certified.snd.comp Certified.snd)).comp
(filter_certified shortTest_certified))).comp
(ListMap.map_certified cons_certified))).comp append_certified
end WitnessEncryption.Runtime.FeatureEnumeration
namespace WitnessEncryption.Runtime.FeatureBounds
open OAI.ThreeMachine.StackCompiler
open GenericGroupWE.Main
open scoped BigOperators
theorem matrixOrder_native_poly (d : ℕ) (hd : 1 ≤ d) :
∃ k, Poly (volume : ℕ → ℕ) (fun N => matrixOrder (max 2 N) d) k := by
obtain ⟨C,hC,hbound⟩ := parameter_matrix_order_bound d hd
let K := Nat.ceil C
have hCK : C ≤ (K : ℝ) := Nat.le_ceil C
have hn : ∀ N : ℕ, 2 ≤ N → matrixOrder N d ≤ K*N^K := by
intro N hN
have hN1 : (1 : ℝ) ≤ N := by exact_mod_cast (show 1 ≤ N by omega)
have hb : (matrixOrder N d : ℝ) ≤ (K : ℝ)*(N : ℝ)^K := by
calc
_ ≤ C*(N : ℝ)^C := (hbound N hN).2
_ ≤ (K : ℝ)*(N : ℝ)^C := mul_le_mul_of_nonneg_right hCK (Real.rpow_nonneg (by positivity) _)
_ ≤ (K : ℝ)*(N : ℝ)^(K : ℝ) := mul_le_mul_of_nonneg_left
(Real.rpow_le_rpow_of_exponent_le hN1 hCK) (by positivity)
_ = _ := by rw [Real.rpow_natCast]
exact_mod_cast hb
refine ⟨K,Poly.of_le (g := fun N : ℕ => K*(volume N+2)^K) ?_
(Poly.powerBase (volume : ℕ → ℕ) K K)⟩
intro N
exact (hn (max 2 N) (le_max_left _ _)).trans
(Nat.mul_le_mul_left K (Nat.pow_le_pow_left (by rw [volume_nat]; omega) K))
theorem tuple_volume (xs : List ℕ) : volume xs=2*xs.sum+2*xs.length+1 := by
induction xs with
| nil => simp
| cons a xs ih => simp only [volume_cons,volume_nat,List.sum_cons,List.length_cons,ih]; omega
theorem weak_volume (J r : ℕ) :
volume (BasisEnumerationProof.weakCompositions J r) ≤
(Nat.choose (J+r) r)*(2*r+2*J+2)+1 := by
have h := volume_list_le (BasisEnumerationProof.weakCompositions J r) (2*r+2*J+1) (by
intro xs hxs
have hm := (BasisEnumerationProof.mem_weakCompositions J r xs).mp hxs
rw [tuple_volume,hm.1]
omega)
simpa only [BasisEnumerationProof.weakCompositions_length,Nat.add_assoc] using h
theorem weak_prefix_volume (N d j : ℕ) (hj : j ≤ (rankTarget N d)^2) :
volume (BasisEnumerationProof.weakCompositions j (weightDegree N)) ≤
matrixOrder N d*(2*weightDegree N+2*(rankTarget N d)^2+2)+1 := by
have hM : Nat.choose ((rankTarget N d)^2+weightDegree N) (weightDegree N) ≤ matrixOrder N d := by
have hs : 1 ≤ N*((rankTarget N d)^2+weightDegree N)+1 := by omega
have hc : 1 ≤ ∑ i ∈ Finset.range (min d N+1), N.choose i := by
have ht := Finset.single_le_sum (fun i _ => Nat.zero_le (N.choose i))
(show 0 ∈ Finset.range (min d N+1) by simp)
simpa only [Nat.choose_zero_right] using ht
have hp := Nat.mul_le_mul hc hs
change 1 ≤ (∑ i ∈ Finset.range (min d N+1), N.choose i)*
(N*((rankTarget N d)^2+weightDegree N)+1) at hp
unfold matrixOrder
simpa only [Nat.one_mul] using Nat.mul_le_mul_right
(Nat.choose ((rankTarget N d)^2+weightDegree N) (weightDegree N)) hp
exact (weak_volume j (weightDegree N)).trans (by
apply Nat.add_le_add_right
apply Nat.mul_le_mul
· exact (Nat.choose_le_choose _ (Nat.add_le_add_right hj _)).trans hM
· omega)
theorem column_count_bound (N d : ℕ) :
Fintype.card (BitMonomial N d) ≤ (d+1)*(N+1)^d := by
rw [BasisFeatureProof.bit_card]
calc
_ ≤ ∑ _i ∈ Finset.range (min d N+1), (N+1)^d := by
apply Finset.sum_le_sum
intro i hi
have hid : i ≤ d := by simp only [Finset.mem_range] at hi; omega
exact (Nat.choose_le_pow N i).trans
((Nat.pow_le_pow_left (by omega : N ≤ N+1) i).trans
(Nat.pow_le_pow_right (by omega : 1 ≤ N+1) hid))
_ = (min d N+1)*(N+1)^d := by simp
_ ≤ (d+1)*(N+1)^d := Nat.mul_le_mul_right _ (by omega)
theorem sparse_volume (N d : ℕ) :
volume (BasisSubsetProof.smallSubsets N d) ≤
((d+1)*(N+1)^d)*(2*d*N+2*d+2)+1 := by
have hcount : (BasisSubsetProof.smallSubsets N d).length ≤ (d+1)*(N+1)^d := by
have hcols := BasisSubsetProof.enumeratedColumns_eq N d
have hlen := congrArg List.length hcols
simp only [BasisSubsetProof.enumeratedColumns,List.length_map,List.length_attach] at hlen
exact hlen.trans_le ((BasisFeatureProof.columnList_length N d).trans_le (column_count_bound N d))
have hvol := volume_list_le (BasisSubsetProof.smallSubsets N d) (2*d*N+2*d+1) (by
intro xs hxs
obtain ⟨hp,hi,hl⟩ := (BasisSubsetProof.mem_smallSubsets N d xs).mp hxs
have hs : xs.sum ≤ xs.length*N := by
have h := List.sum_le_card_nsmul xs N (fun i hi' => (hi i hi').le)
simpa only [smul_eq_mul,Nat.mul_comm] using h
rw [tuple_volume]
have hm := Nat.mul_le_mul_right N hl
nlinarith)
exact hvol.trans (by
simpa only [Nat.add_assoc] using Nat.add_le_add_right
(Nat.mul_le_mul_right (2*d*N+2*d+2) hcount) 1)
end WitnessEncryption.Runtime.FeatureBounds
namespace WitnessEncryption.Runtime.FeatureEnumeration
open OAI.ThreeMachine.StackCompiler
open GenericGroupWE.Main
open FeatureParameters
def weakStep (x : Unit × (ℕ × Tuples)) : ℕ × Tuples :=
(x.2.1,x.2.2.flatMap fun xs => (List.range (x.2.1-xs.sum+1)).map (fun k => k::xs))
def weakStepR : Realizer weakStep :=
(Realizer.snd.comp Realizer.fst).pair (Realizer.snd.comp weakLayerR)
theorem weakStep_certified : Certified weakStepR :=
(Certified.snd.comp Certified.fst).pair (Certified.snd.comp weakLayer_certified)
theorem weak_fold (us : List Unit) (r j : ℕ) :
us.foldl (fun s u => weakStep (u,s)) (r,BasisEnumerationProof.weakCompositions j r)=
(r,BasisEnumerationProof.weakCompositions (j+us.length) r) := by
induction us generalizing j with
| nil => simp
| cons u us ih =>
rw [List.foldl_cons]
change us.foldl (fun s u => weakStep (u,s))
(r,BasisEnumerationProof.weakCompositions (j+1) r)=_
rw [ih]
congr 2
simp only [List.length_cons]
omega
def weakPrepare (d N : ℕ) : List Unit × (ℕ × Tuples) :=
(List.replicate ((rankTarget (max 2 N) d)^2) (), (weightDegree (max 2 N),[[]]))
def weakPrepareR (d : ℕ) : Realizer (weakPrepare d) :=
(((maxTwoR.comp (tupleWidthR d)).comp Prime.UnaryPowerProof.unitsR).pair
((maxTwoR.comp weightDegreeR).pair (Realizer.constant [[]])))
theorem weakPrepare_certified (d : ℕ) : Certified (weakPrepareR d) :=
(((maxTwo_certified.comp (tupleWidth_certified d)).comp Prime.UnaryPowerProof.unitsR_certified).pair
((maxTwo_certified.comp weightDegree_certified).pair (Certified.constant [[]])))
theorem weakPrepared_certified (d : ℕ) (hd : 1 ≤ d) :
Certified ((weakPrepareR d).comp weakStepR.fold) := by
apply FeatureCost.prepared_fold (weakPrepareR d) (weakPrepare_certified d)
weakStepR weakStep_certified
obtain ⟨er,_,hrv⟩ := maxTwo_certified.comp weightDegree_certified
obtain ⟨eJ,_,hJv⟩ := maxTwo_certified.comp (tupleWidth_certified d)
obtain ⟨eM,hM⟩ := FeatureBounds.matrixOrder_native_poly d hd
have hr : Poly (volume : ℕ → ℕ) (fun N => weightDegree (max 2 N)) er :=
Poly.of_le (fun N => by change weightDegree (max 2 N) ≤ volume (weightDegree (max 2 N)); rw [volume_nat]; omega) hrv
have hJ : Poly (volume : ℕ → ℕ) (fun N => (rankTarget (max 2 N) d)^2) eJ :=
Poly.of_le (fun N => by change (rankTarget (max 2 N) d)^2 ≤ volume ((rankTarget (max 2 N) d)^2); rw [volume_nat]; omega) hJv
let size : ℕ → ℕ := volume
have hlin := (((OAI.ThreeMachine.StackCompiler.Poly.const size 2).mul hr).add ((OAI.ThreeMachine.StackCompiler.Poly.const size 2).mul hJ)).add (OAI.ThreeMachine.StackCompiler.Poly.const size 2)
have hB := (((OAI.ThreeMachine.StackCompiler.Poly.const size 2).mul hr).add (hM.mul hlin)).add (OAI.ThreeMachine.StackCompiler.Poly.const size 3)
simp only [Nat.zero_add,Nat.max_zero] at hB
rcases hB with ⟨C,hC⟩
refine ⟨C,max er (eM+max er eJ),?_⟩
intro N j hj
change j ≤ (List.replicate ((rankTarget (max 2 N) d)^2) ()).length at hj
rw [List.length_replicate] at hj
apply le_trans ?_ (hC N)
change volume (((List.replicate ((rankTarget (max 2 N) d)^2) ()).take j).foldl
(fun s u => weakStep (u,s)) (weightDegree (max 2 N),[[]])) ≤
2*weightDegree (max 2 N)+matrixOrder (max 2 N) d*
(2*weightDegree (max 2 N)+2*(rankTarget (max 2 N) d)^2+2)+3
have hf := weak_fold ((List.replicate ((rankTarget (max 2 N) d)^2) ()).take j)
(weightDegree (max 2 N)) 0
simp only [List.length_take,List.length_replicate,Nat.min_eq_left hj,Nat.zero_add] at hf
simp only [BasisEnumerationProof.weakCompositions] at hf
rw [hf]
have hw := FeatureBounds.weak_prefix_volume (max 2 N) d j hj
simp only [volume_prod,volume_nat]
omega
def weakR (d : ℕ) : Realizer (fun N =>
BasisEnumerationProof.weakCompositions ((rankTarget (max 2 N) d)^2) (weightDegree (max 2 N))) :=
(((weakPrepareR d).comp weakStepR.fold).comp Realizer.snd).congr (fun N => by
have hf := congrArg Prod.snd (weak_fold
(List.replicate ((rankTarget (max 2 N) d)^2) ()) (weightDegree (max 2 N)) 0)
simpa only [Function.comp_apply,weakPrepare,BasisEnumerationProof.weakCompositions,List.length_replicate,Nat.zero_add] using hf)
theorem weak_certified (d : ℕ) (hd : 1 ≤ d) : Certified (weakR d) := by
unfold weakR
apply Certified.congr
exact (weakPrepared_certified d hd).comp Certified.snd
def subsetStep (d : ℕ) (x : Unit × (ℕ × Tuples)) : ℕ × Tuples :=
(x.2.1+1,x.2.2++((x.2.2.filter (fun xs => decide (xs.length < d))).map (fun xs => x.2.1::xs)))
def subsetStepR (d : ℕ) : Realizer (subsetStep d) :=
((Realizer.snd.comp Realizer.fst).comp Realizer.succ).pair
(((Realizer.constant d).pair Realizer.snd).comp subsetLayerR)
theorem subsetStep_certified (d : ℕ) : Certified (subsetStepR d) :=
((Certified.snd.comp Certified.fst).comp NatPrimitives.succ_certified).pair
(((Certified.constant d).pair Certified.snd).comp subsetLayer_certified)
theorem subset_fold (us : List Unit) (d i : ℕ) :
us.foldl (fun s u => subsetStep d (u,s)) (i,BasisSubsetProof.smallSubsets i d)=
(i+us.length,BasisSubsetProof.smallSubsets (i+us.length) d) := by
induction us generalizing i with
| nil => simp
| cons u us ih =>
rw [List.foldl_cons]
change us.foldl (fun s u => subsetStep d (u,s))
(i+1,BasisSubsetProof.smallSubsets (i+1) d)=_
rw [ih]
have hidx : i+1+us.length=i+(u::us).length := by simp only [List.length_cons]; omega
exact congrArg (fun n => (n,BasisSubsetProof.smallSubsets n d)) hidx
def subsetPrepareR : Realizer (fun N : ℕ => (List.replicate N (),(0,([[]] : Tuples)))) :=
Prime.UnaryPowerProof.unitsR.pair (Realizer.constant (0,[[]]))
theorem subsetPrepare_certified : Certified subsetPrepareR :=
Prime.UnaryPowerProof.unitsR_certified.pair (Certified.constant (0,[[]]))
theorem subsetPrepared_certified (d : ℕ) : Certified (subsetPrepareR.comp (subsetStepR d).fold) := by
apply FeatureCost.prepared_fold subsetPrepareR subsetPrepare_certified
(subsetStepR d) (subsetStep_certified d)
let size : ℕ → ℕ := volume
have hn : Poly size (fun N : ℕ => N) 1 :=
Poly.of_le (fun N => by dsimp [size]; rw [volume_nat]; omega) (Poly.size size)
have hcount := (OAI.ThreeMachine.StackCompiler.Poly.const size (d+1)).mul ((hn.add (OAI.ThreeMachine.StackCompiler.Poly.const size 1)).pow d)
have hword := ((OAI.ThreeMachine.StackCompiler.Poly.const size (2*d)).mul hn).add (OAI.ThreeMachine.StackCompiler.Poly.const size (2*d+2))
have hB := (((OAI.ThreeMachine.StackCompiler.Poly.const size 2).mul hn).add (hcount.mul hword)).add (OAI.ThreeMachine.StackCompiler.Poly.const size 3)
simp only [Nat.zero_add,Nat.max_zero,Nat.one_mul] at hB
rcases hB with ⟨C,hC⟩
refine ⟨C,max 1 (d+1),?_⟩
intro N j hj
change j ≤ (List.replicate N ()).length at hj
rw [List.length_replicate] at hj
apply le_trans ?_ (hC N)
change volume (((List.replicate N ()).take j).foldl
(fun s u => subsetStep d (u,s)) (0,[[]])) ≤
2*N+((d+1)*(N+1)^d)*(2*d*N+2*d+2)+3
have hf := subset_fold ((List.replicate N ()).take j) d 0
simp only [List.length_take,List.length_replicate,Nat.min_eq_left hj,Nat.zero_add] at hf
simp only [BasisSubsetProof.smallSubsets] at hf
rw [hf]
have hw := FeatureBounds.sparse_volume j d
have hmono : ((d+1)*(j+1)^d)*(2*d*j+2*d+2) ≤ ((d+1)*(N+1)^d)*(2*d*N+2*d+2) := by
gcongr
simp only [volume_prod,volume_nat]
omega
def subsetsR (d : ℕ) : Realizer (fun N => BasisSubsetProof.smallSubsets N d) :=
((subsetPrepareR.comp (subsetStepR d).fold).comp Realizer.snd).congr (fun N => by
have hf := congrArg Prod.snd (subset_fold (List.replicate N ()) d 0)
simpa only [Function.comp_apply,BasisSubsetProof.smallSubsets,List.length_replicate,Nat.zero_add] using hf)
theorem subsets_certified (d : ℕ) : Certified (subsetsR d) := by
unfold subsetsR
apply Certified.congr
exact (subsetPrepared_certified d).comp Certified.snd
universe u v
variable {α : Type u} {β : Type v} [Coding α] [Coding β]
def crossR : Realizer (fun x : List α × List β => x.1.product x.2) :=
(((Realizer.snd.pair Realizer.fst).comp
(ListMap.mapR ((Realizer.snd.pair Realizer.fst).comp (ListMap.mapR Realizer.id)))).comp
FeatureMetadata.flattenR).congr (fun _x => rfl)
theorem cross_certified : Certified (crossR (α := α) (β := β)) := by
unfold crossR
apply Certified.congr
exact (((Certified.snd.pair Certified.fst).comp
(ListMap.map_certified ((Certified.snd.pair Certified.fst).comp
(ListMap.map_certified Certified.identity)))).comp FeatureMetadata.flatten_certified)
abbrev RawRow := ℕ × (List ℕ × List ℕ)
def rawRows (N d : ℕ) : List RawRow :=
(List.range (N*((rankTarget N d)^2+weightDegree N)+1)).product
((BasisEnumerationProof.weakCompositions ((rankTarget N d)^2) (weightDegree N)).product
(BasisSubsetProof.smallSubsets N d))
def rowFeaturesR (d : ℕ) : Realizer (fun N =>
(BasisEnumerationProof.weakCompositions ((rankTarget (max 2 N) d)^2) (weightDegree (max 2 N))).product
(BasisSubsetProof.smallSubsets (max 2 N) d)) :=
(((weakR d).pair (maxTwoR.comp (subsetsR d))).comp
(crossR (α := List ℕ) (β := List ℕ)))
theorem rowFeatures_certified (d : ℕ) (hd : 1 ≤ d) : Certified (rowFeaturesR d) :=
(((weak_certified d hd).pair (maxTwo_certified.comp (subsets_certified d))).comp cross_certified)
def sampleIndicesR (d : ℕ) : Realizer (fun N =>
List.range (max 2 N*((rankTarget (max 2 N) d)^2+weightDegree (max 2 N))+1)) :=
(maxTwoR.comp (samplesR d)).comp FeatureMetadata.rangeR
theorem sampleIndices_certified (d : ℕ) : Certified (sampleIndicesR d) :=
(maxTwo_certified.comp (samples_certified d)).comp FeatureMetadata.range_certified
set_option maxHeartbeats 1000000 in
def rowsR (d : ℕ) : Realizer (fun N => rawRows (max 2 N) d) :=
(((sampleIndicesR d).pair (rowFeaturesR d)).comp
(crossR (α := ℕ) (β := List ℕ × List ℕ))).congr (fun _N => rfl)
set_option maxHeartbeats 1000000 in
theorem rows_certified (d : ℕ) (hd : 1 ≤ d) : Certified (rowsR d) :=
(((sampleIndices_certified d).pair (rowFeatures_certified d hd)).comp cross_certified).congr (fun _N => rfl)
end WitnessEncryption.Runtime.FeatureEnumeration
namespace WitnessEncryption.Runtime.FeatureEnumeration
open GenericGroupWE.Main
open BasisEnumerationProof BasisSubsetProof BasisFeatureEnumerationProof
noncomputable def encodeColumn {N d : ℕ} (S : BitMonomial N d) : List ℕ :=
(S.val.image Fin.val).sort (fun i j => j ≤ i)
theorem encodeColumn_asBit (N d : ℕ) (xs : List ℕ)
(hp : xs.Pairwise (fun i j => j < i)) (hb : ∀ i ∈ xs, i < N) (hl : xs.length ≤ d) :
encodeColumn (asBit N d xs hp hb hl)=xs := by
change ((supportFin N xs).image Fin.val).sort (fun i j => j ≤ i)=xs
rw [supportFin_image N xs hb]
exact sparse_eq_of_support (Finset.sortedGT_sort _).pairwise hp (by simp)
def encodeOrdinary {J r : ℕ} (a : OrdinaryMonomial J r) : List ℕ :=
List.ofFn (fun j => (a.val j).val)
theorem columns_raw_agreement (N d : ℕ) :
(columnList N d).map encodeColumn=smallSubsets N d := by
rw [←enumeratedColumns_eq]
simp only [enumeratedColumns,List.map_map,Function.comp_def,
encodeColumn_asBit,List.attach_map_subtype_val]
noncomputable def encodeRow {N d : ℕ} (row : StackRow N d) : RawRow :=
(row.1.1.val,(encodeOrdinary row.1.2,encodeColumn row.2))
theorem rows_raw_agreement (N d : ℕ) :
(rowList N d).map encodeRow=rawRows N d := by
rw [←enumeratedRows_eq]
simp only [enumeratedRows,enumeratedWeights,enumeratedOrdinary,enumeratedColumns,
encodeRow,encodeOrdinary,rawRows,List.product,List.map_flatMap,List.flatMap_map,
List.flatMap_assoc,List.map_map,Function.comp_def,ofFn_fromList,encodeColumn_asBit]
simp only [List.flatMap_def]
have hinner (t : ℕ) (a : List ℕ) :
(smallSubsets N d).attach.map (fun x => (t,(a,x.val)))=
(smallSubsets N d).map (fun x => (t,(a,x))) :=
List.attach_map_val (l := smallSubsets N d) (f := fun x => (t,(a,x)))
simp_rw [hinner]
have hmiddle (t : ℕ) :
(weakCompositions ((rankTarget N d)^2) (weightDegree N)).attach.map
(fun a => (smallSubsets N d).map (fun x => (t,(a.val,x))))=
(weakCompositions ((rankTarget N d)^2) (weightDegree N)).map
(fun a => (smallSubsets N d).map (fun x => (t,(a,x)))) :=
List.attach_map_val (l := weakCompositions ((rankTarget N d)^2) (weightDegree N))
(f := fun a => (smallSubsets N d).map (fun x => (t,(a,x))))
simp_rw [hmiddle]
exact congrArg List.flatten (List.attach_map_val (f := fun t =>
((weakCompositions ((rankTarget N d)^2) (weightDegree N)).map
(fun a => (smallSubsets N d).map (fun x => (t,(a,x))))).flatten))
end WitnessEncryption.Runtime.FeatureEnumeration
end