Oblivious RAM
Correctness of the simple ORAM scheme
| ← Previous revision | Revision as of 09:03, 23 April 2026 | ||
| Line 122: | Line 122: | ||
The following lemma completes the proof of correctness of the ORAM scheme. |
The following lemma completes the proof of correctness of the ORAM scheme. |
||
;Overflow Lemma:There exists a negligible function {{mvar|μ}} such that for every program {{math|Π}}, every {{mvar|n}} and input {{mvar|x}}, the program outputs overflow with probability at most . |
;Overflow Lemma:There exists a negligible function {{mvar|μ}} such that for every program {{math|Π}}, every {{mvar|n}} and input {{mvar|x}}, the program outputs overflow with probability at most . |
||
====Computational and memory overheads==== |
====Computational and memory overheads==== |
||
