Theory Seminar: Sub-logarithmic Distributed Oblivious RAM with Small Block Size

Tamer Mour (CS, Technion)
Wednesday, 6.6.2018, 12:30
Taub 201

Oblivious RAM (ORAM) is a cryptographic primitive that allows a client to securely execute RAM programs over data that is stored in an untrusted server. Distributed Oblivious RAM is a variant of ORAM, where the data is stored in m non-colluding servers. Extensive research over the last few decades have succeeded to reduce the bandwidth overhead of ORAM schemes, both in the single-server and the multi-server setting, from O(\sqrt{N}) to O(1). However, all known protocols that achieve a sub-logarithmic overhead either require heavy server-side computation (e.g. homomorphic encryption), or a relatively large block size of at least \Omega(\log^3 N).

In this talk, I will present some improvements for the aforementioned results.

This is a joint work with professor Eyal Kushilevitz.

Back to the index of events