Proof of Claim B.1.1, p. A:44 — the triangle-inequality chain giving Property 3,
ProvedObfImpossibility.PseudoOracle.triangle_chaininequalitiesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandomness
For every there is such that the following holds for all and . Let be a distinguisher, injective, and with , where . Write , and . Assume that violates inequality (7),
and that satisfies the Chernoff-like bound . Then
and
This is the computation that turns a violation of (7) on all of and into a violation on the smaller sets and , i.e. Property 3 of Claim B.1.1. The paper bounds the three subtracted gaps by , and and uses that for large ; its "" in the second gap is a misprint for .
Formalization Note Both conclusions are stated; the first is a pure triangle inequality. Property (1) is read as .
Preamble
import Mathlib import Definitions.Def_ObfImpossibility_PseudoOracle_Setting
Formal statement
namespace ObfImpossibility.PseudoOracle
/-- The chain of inequalities closing the proof of Claim B.1.1, p. A:44: if `G` violates
(7), `S_G ⊆ S` with `|S_G| ≥ (1-γ)|S|`, `γ = K^{-3δ}`, and `S` satisfies the Chernoff-like
bound, then the four gaps satisfy the triangle inequality, and Property 3 holds:
`|Pr_{x∈S_G}[D^G(G(x)) = 1] - Pr_{y∈L_G}[D^G(y) = 1]| > 1/(2K^δ)`. -/
theorem triangle_chain :
∀ δ : ℝ, 0 < δ → δ ≤ 1 / 100 → ∃ K₀ : ℕ, ∀ K L : ℕ, K₀ ≤ K → K ^ 2 ≤ L →
∀ (D : Fin L → QTree K L) (G : Fin K ↪ Fin L) (S SG : Finset (Fin K)),
SG ⊆ S →
(1 - (K : ℝ) ^ (-(3 * δ))) * (S.card : ℝ) ≤ (SG.card : ℝ) →
1 / (K : ℝ) ^ δ < |prX D G - prY D G| →
|avg S (fun x => (D (G x)).run G) - prX D G| ≤ 1 / (4 * (K : ℝ) ^ δ) →
|prX D G - prY D G|
- |avg SG (fun x => (D (G x)).run G) - avg S (fun x => (D (G x)).run G)|
- |avg S (fun x => (D (G x)).run G) - prX D G|
- |prY D G - avg (LG G SG) (fun y => (D y).run G)|
≤ |avg SG (fun x => (D (G x)).run G) - avg (LG G SG) (fun y => (D y).run G)| ∧
1 / (2 * (K : ℝ) ^ δ) <
|avg SG (fun x => (D (G x)).run G) - avg (LG G SG) (fun y => (D y).run G)| := 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:44, Appendix B, end of the proof of Claim B.1.1 (display; x∈[S] read as x∈S)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.