§6, p. 470 — every visible pattern serves every request sequence
ProvedObliviousRAM.LowerBound.visible_satisfies_allaccess-patternoblivious-ramp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be a correct oblivious randomized player for rounds and balls. If a run occurs with positive probability for one request sequence , then for every other request sequence there is a positive-probability run of on with the same visible cell sequence as , and satisfies :
This gives the common visible pattern the capacity to serve all possible request sequences.
Formalization Note The player may randomize and know the complete sequence. Obliviousness equates the full distributions of visible patterns, rather than only their supports.
Preamble
import Mathlib import Definitions.Def_ObliviousRAM_LowerBound_Game
Formal statement
namespace ObliviousRAM.LowerBound
theorem visible_satisfies_all {b m t : ℕ} (P : ObliviousPlayer b m t)
(r : Fin t → Fin m) (a : List (Action m)) (ha : a ∈ (P.play r).support)
(r' : Fin t → Fin m) :
∃ a' ∈ (P.play r').support, visible a' = visible a ∧ Satisfies b a' r' := by sorry
end ObliviousRAM.LowerBound
Source
Goldreich and Ostrovsky, Software protection and simulation on oblivious RAMs, J. ACM 43 (1996), p. 470, §6, proof of THEOREM 6.1, obliviousness observation; https://doi.org/10.1145/233551.233553
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.