Proof of Claim B.1.1, p. A:43 — a random of size estimates within
ProvedObfImpossibility.PseudoOracle.chernoff_over_Sconcentrationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandomnesssampling-without-replacement
For every there are a constant and a threshold such that the following holds for all , all , every distinguisher and every injective . Let be a uniformly random subset of of size , and let be the probability over that
Then
This is the sampling step behind Property 3 of Claim B.1.1: a random set of inputs estimates the acceptance probability of on , , to within . The paper prints the exponent as ; the minus sign is restored.
Formalization Note is rendered as an explicit constant that may depend on but not on , , or . Probabilities over are counting fractions over the subsets of size . The query bound on is not needed for this step and is not assumed.
Preamble
import Mathlib import Definitions.Def_ObfImpossibility_PseudoOracle_Setting
Formal statement
namespace ObfImpossibility.PseudoOracle
/-- Proof of Claim B.1.1, p. A:43 (Property 3), the Chernoff-like bound: for every `D`
and `G`, with probability at least `1 - exp(-Ω(K^{1-5δ}·(K^{-δ})²)) > 3/4` over a
uniformly random `S ⊆ [K]` of size `⌊K^{1-5δ}⌋`,
`|Pr_{x∈S}[D^G(G(x)) = 1] - Pr_{x∈[K]}[D^G(G(x)) = 1]| ≤ 1/(4K^δ)`. -/
theorem chernoff_over_S :
∀ δ : ℝ, 0 < δ → δ ≤ 1 / 100 → ∃ c : ℝ, 0 < c ∧ ∃ K₀ : ℕ, ∀ K L : ℕ, K₀ ≤ K →
∀ (D : Fin L → QTree K L) (G : Fin K ↪ Fin L),
1 - Real.exp (-(c * ((K : ℝ) ^ (1 - 5 * δ) * ((K : ℝ) ^ (-δ)) ^ 2))) ≤
((((Finset.univ : Finset (Fin K)).powersetCard ⌊(K : ℝ) ^ (1 - 5 * δ)⌋₊).filter
fun S => |avg S (fun x => (D (G x)).run G) - prX D G| ≤
1 / (4 * (K : ℝ) ^ δ)).card : ℝ) /
((K.choose ⌊(K : ℝ) ^ (1 - 5 * δ)⌋₊ : ℕ) : ℝ) ∧
(3 / 4 : ℝ) <
((((Finset.univ : Finset (Fin K)).powersetCard ⌊(K : ℝ) ^ (1 - 5 * δ)⌋₊).filter
fun S => |avg S (fun x => (D (G x)).run G) - prX D G| ≤
1 / (4 * (K : ℝ) ^ δ)).card : ℝ) /
((K.choose ⌊(K : ℝ) ^ (1 - 5 * δ)⌋₊ : ℕ) : ℝ) := by sorry
end ObfImpossibility.PseudoOracle
Source
Barak et al., On the (Im)possibility of Obfuscating Programs, J. ACM 59(2) (2012), author's copy, p. A:43, Appendix B, proof of Claim B.1.1 (Property 3, Chernoff-like bound)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.