Proof of Claim B.1.1, p. A:43 — for most of size , at most a fraction of query (corrected)
ProvedObfImpossibility.PseudoOracle.property2_averagingLet , let be natural numbers, let be a distinguisher making at most oracle queries, and let be injective. Put and choose uniformly among the -element subsets of . Then
This is the averaging step behind Property 2 of Claim B.1.1: since makes at most queries and has density about , few have runs that hit the rest of , and discarding them leaves a large subset of that the remaining runs avoid.
The statement differs from the printed sentence in two ways. The paper writes "", a misprint for . More importantly, the paper counts queries at any element of , including itself; that version is false. A one-query distinguisher that queries and outputs iff the answer is , where , queries on input for every , and every such violates (7). The bound here excludes the query at and holds for every , hence also for drawn from the set of violating (7), as the paper uses it.
Formalization Note The probability is the number of good in Finset.powersetCard s univ divided by . "Fraction of " is written multiplicatively, , which is the same condition for . The restriction is the paper's "sufficiently small " made explicit.
import Mathlib import Definitions.Def_ObfImpossibility_PseudoOracle_Setting
namespace ObfImpossibility.PseudoOracle
/-- Proof of Claim B.1.1, p. A:43 (Property 2), corrected: for every `G`, with probability
at least `3/4` over a uniformly random `S ⊆ [K]` of size `⌊K^{1-5δ}⌋`, the run of
`D^G(G(x))` queries its oracle at an element of `S` other than `x` itself for at most a
`4K^{-4δ}` fraction of the `x ∈ S`. The paper prints `4/K^{-4δ}` and does not exclude the
query at `x`; the printed form is false (a one-query `D` that inverts `G` breaks it). -/
theorem property2_averaging :
∀ δ : ℝ, 0 < δ → δ ≤ 1 / 100 → ∀ K L : ℕ,
∀ D : Fin L → QTree K L, (∀ y, ((D y).depth : ℝ) ≤ (K : ℝ) ^ δ) →
∀ G : Fin K ↪ Fin L,
(3 / 4 : ℝ) ≤
((((Finset.univ : Finset (Fin K)).powersetCard ⌊(K : ℝ) ^ (1 - 5 * δ)⌋₊).filter
fun S => (((S.filter fun x => (D (G x)).hits G (S.erase x) = true).card : ℝ) ≤
4 * (K : ℝ) ^ (-(4 * δ)) * (S.card : ℝ))).card : ℝ) /
((K.choose ⌊(K : ℝ) ^ (1 - 5 * δ)⌋₊ : ℕ) : ℝ) := by sorry
end ObfImpossibility.PseudoOracle
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.