Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with oblivious:
TR10-028 | 4th March 2010
Miklos Ajtai

Oblivious RAMs without Cryptographic Assumptions

Revisions: 1

Abstract. We show that oblivious on-line simulation with only
polylogarithmic increase in the time and space requirements is possible
on a probabilistic (coin flipping) RAM without using any cryptographic
assumptions. The simulation will fail with a negligible probability.
If $n$ memory locations are used, then the probability of failure is ... more >>>

ISSN 1433-8092 | Imprint