Lemma C.1 — uniform logarithmic inversion (reading: x > 0 and c > 0)
ProvedMixedORAM.PublicRead.lemma_C_1inequalityp2o-gran-per-chapterp2o-plan-paperp2o-v1real-analysis
Let . There is a constant depending only on such that for all real , , and ,
Applied with , , and , it turns (14) into .
Differences from the source:
- reading: x unrestricted → x > 0; reason: the proof works on x > 0 ('f is increasing for x > 0') and every use has x a positive cost; as printed the lemma is false for x < 0 (INSIGHTS I1)
- reading: a constant c (sign not stated) → c > 0; reason: c is the positive constant of Theorem A.1 in every use; for c ≤ 0 the hypothesis holds for every x > 0 and the lemma is false (INSIGHTS I2)
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace MixedORAM.PublicRead
theorem lemma_C_1 (c : ℝ) (hc : 0 < c) :
∃ c' : ℝ, 0 < c' ∧ ∀ A D S x : ℝ, 2 ≤ A → 0 ≤ D → 0 < S → 0 < x →
c * S ≤ x * Real.logb 2 (A + D / x) → c' * S / Real.logb 2 (A + D / S) ≤ x := by sorry
end MixedORAM.PublicRead
Source
Ciszewski, Ragnoli, Access Cost Tradeoffs in Mixed-Mode Oblivious RAM, STOC 2027 submission (manuscript sha256 a4f849fd…), p. 35, Lemma C.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.