End of App. B, p. A:45 — the set of violating (7) has density smaller than
ProvedObfImpossibility.PseudoOracle.density_boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandomnessquery-complexity
There is such that for every there is with the following property. For all and and every distinguisher making at most oracle queries, let be the set of injective with
Then the fraction of injective functions that lie in is smaller than .
This is the sentence that closes Appendix B. It is weaker than Lemma B.1, which bounds the same fraction by ; the counting bound of Claim B.1.2 supports the stronger conclusion once .
Formalization Note The fraction is divided by the number of embeddings Fin K ↪ Fin L. The existence of renders the paper's "sufficiently small ".
Preamble
import Mathlib import Definitions.Def_ObfImpossibility_PseudoOracle_Setting
Formal statement
namespace ObfImpossibility.PseudoOracle
/-- The density bound, p. A:45: for every sufficiently small `δ > 0`, for all large `K`,
all `L ≥ K²` and every `D` making at most `K^δ` queries, the set `𝒢` of injective
`G : [K] → [L]` violating (7) has density smaller than `K^{-δ}`. -/
theorem density_bound :
∃ δ₀ : ℝ, 0 < δ₀ ∧ ∀ δ : ℝ, 0 < δ → δ ≤ δ₀ → ∃ K₀ : ℕ, ∀ K L : ℕ, K₀ ≤ K → K ^ 2 ≤ L →
∀ D : Fin L → QTree K L, (∀ y, ((D y).depth : ℝ) ≤ (K : ℝ) ^ δ) →
((Finset.univ.filter fun G : Fin K ↪ Fin L =>
1 / (K : ℝ) ^ δ < |prX D G - prY D G|).card : ℝ) /
(Fintype.card (Fin K ↪ Fin L) : ℝ) < (K : ℝ) ^ (-δ) := 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:45, Appendix B, last paragraph (density of 𝒢)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.