slideshow 3

Complexity seminar

Stronger Lower Bounds for Online ORAM

Veronika Slivova


Friday, 1. March 2019 - 13:30 to 15:00

in IM, rear building, ground floor

Oblivious RAM (ORAM), introduced in the context of software protection
by Goldreich and Ostrovsky [JACM’96], aims at obfuscating the memory
access pattern induced by a RAM computation. We will show that every
implementation of Online Oblivious RAM has logarthmic overhead.

Joint work with P. Hubacek, M. Koucky and K. Kral.