Inequality (8), p. A:44 — the query-free simulator built from and keeps the gap
ProvedObfImpossibility.PseudoOracle.inequality_8p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandomnessquery-complexitysimulation
Let be natural numbers, , a distinguisher, injective and . Define to simulate , answering each oracle query with and halting with output at a query . Assume
- (Property 2 of Claim B.1.1) for every , never queries its oracle at an element of ;
- (Property 3, in the sign case at hand) , where .
Then depends only on and the restriction (any injective agreeing with off gives the same ), and
In the proof of Claim B.1.2 this lets the description of replace oracle access to on : is computable from the part of already described, and it still separates from .
Formalization Note As in the paper, the absolute value of Property 3 is dropped and the case is treated; the other case is symmetric (with outputting at a query in ) and is not stated. is (D y).runAvoid G S_G.
Preamble
import Mathlib import Definitions.Def_ObfImpossibility_PseudoOracle_Setting
Formal statement
namespace ObfImpossibility.PseudoOracle
/-- Inequality (8), p. A:44 (proof of Claim B.1.2). `M(y) := (D y).runAvoid G S_G`
simulates `D(y)`, answering a query `z ∉ S_G` with `G(z)` and halting with output `0` at a
query `z ∈ S_G`. Then `M` depends only on `S_G` and `G|_{[K] \ S_G}`, and if Property 2 of
Claim B.1.1 holds and `Pr_{x∈S_G}[D^G(G(x)) = 1] - Pr_{y∈L_G}[D^G(y) = 1] > 1/(2K^δ)`, then
`Pr_{x∈S_G}[M(G(x)) = 1] - Pr_{y∈L_G}[M(y) = 1] > 1/(2K^δ)`. -/
theorem inequality_8 (K L : ℕ) (δ : ℝ) (D : Fin L → QTree K L) (G : Fin K ↪ Fin L)
(SG : Finset (Fin K))
(hprop2 : ∀ x ∈ SG, (D (G x)).hits G SG = false)
(hgap : 1 / (2 * (K : ℝ) ^ δ) <
avg SG (fun x => (D (G x)).run G) - avg (LG G SG) (fun y => (D y).run G)) :
(∀ G' : Fin K ↪ Fin L, (∀ z, z ∉ SG → G' z = G z) →
∀ y, (D y).runAvoid G' SG = (D y).runAvoid G SG) ∧
1 / (2 * (K : ℝ) ^ δ) <
avg SG (fun x => (D (G x)).runAvoid G SG) -
avg (LG G SG) (fun y => (D y).runAvoid G SG) := 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, proof of Claim B.1.2, inequality (8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.