log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
An Oblivious RAM with Sub-logarithmic Bandwidth Blowup
Kartik Nayak - UMD
Friday, September 30, 2016, 11:00 am-12:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract

Oblivious RAM (also known as ORAM) is a cryptographic primitive that allows a trusted client to outsource storage to an untrusted server while hiding the client's memory access patterns to the server. Since the initial work by Goldreich and Ostrovsky three decades ago, there has been a lot of effort to improve ORAMs. In the standard ORAM model, where the server supports only ``read'' and ``write'' operations, the bandwidth blowup between the client and the server has been improved from O(log^3 N) to O(log N). On the other hand, with the assumption that the server can perform computation, Oblivious RAM constructions with O(1) bandwidth blowup exists. However, in practice, the improvement in bandwidth comes with a huge cost in terms of server computation and the server computation (homomorphic encryptions) is the new bottleneck. In this work, we propose an Oblivious RAM construction that does not use expensive server computation and yet achieves sub-logarithmic bandwidth blowup.

This talk is organized by Mukul