§6, p. 470 — corrected count of requests served by a fixed run
ProvedObliviousRAM.LowerBound.card_satisfied_lecorrected-boundcountingoblivious-ramp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a run of accesses, a hand capacity , and request rounds. The number of request sequences that this run legally satisfies is bounded by
This bounds the request sequences associated with a single hidden action history, retaining the paper's non-strict round-end indices.
Formalization Note The printed proof says and footnote 29 offers ; both fail when round ends repeat. With and , a run that takes both balls serves all request sequences, exceeding while . The formal bound uses Nat.multichoose q t, equal to when , and is the corrected statement needed for Theorem 6.1. No legality hypothesis is needed: an illegal run satisfies no requests.
Preamble
import Mathlib import Definitions.Def_ObliviousRAM_LowerBound_Game
Formal statement
namespace ObliviousRAM.LowerBound
open Classical
theorem card_satisfied_le {b m t : ℕ} (a : List (Action m)) :
(Finset.univ.filter fun r : Fin t → Fin m => Satisfies b a r).card ≤
Nat.multichoose a.length t * b ^ t := 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 and footnote 29 (printed bounds corrected); https://doi.org/10.1145/233551.233553
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.