§6, p. 470 — the first-round lower bound of m accesses
ProvedObliviousRAM.LowerBound.length_ge_maccess-patternlower-boundoblivious-ramp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a hand capacity , balls and cells, and at least one request round. Let be a correct oblivious randomized player. For any request sequence and any run that performs with positive probability on ,
This is the first component of the access lower bound: even a run serving one particular request must cover all initially occupied cells because its visible pattern is possible for every request sequence.
Formalization Note Correctness holds for every positive-probability run, and obliviousness is equality of visible-pattern distributions. The at-least-one-round condition makes the first-round observation applicable.
Preamble
import Mathlib import Definitions.Def_ObliviousRAM_LowerBound_Game
Formal statement
namespace ObliviousRAM.LowerBound
theorem length_ge_m {b m t : ℕ} (ht : 1 ≤ t) (P : ObliviousPlayer b m t)
(r : Fin t → Fin m) (a : List (Action m)) (ha : a ∈ (P.play r).support) :
m ≤ a.length := 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, first-round observation; https://doi.org/10.1145/233551.233553
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.