RouterORAM: an O(1)-Latency and Client-Work ORAM

EasyChair Preprint 15459

Abstract

An adversary can learn a lot only by studying data storage access patterns, even if the actual data being accessed remains encrypted. Oblivious RAM (ORAM) is a cryptographic primitive that hides access patterns. However, to achieve this privacy, the client has to perform a significant amount of additional work per access, which not only causes very high access latency but is also often impractical for resource-constrained clients. As a result, ORAMs are still not usable in most of the scenarios. This paper proposes RouterORAM. The central idea of it is to harness the server’s otherwise unutilized computation power to steer the deliberately misplaced blocks to their destined locations. To the best of our knowledge, RouterORAM is the first ORAM to drag both the access latency and the client’s burden together down to the asymptotic minimum level, O(1). It exploits the properties of homomorphic encryption to achieve the desired level of server obliviousness, and its privacy is proven with rigorous theoretical analysis. The long-term behavior of RouterORAM is captured with simulation, which vouches for its suitability for practical usage scenarios.

Keyphrases: Client-work, Latency, ORAM, homomorphic encryption

@booklet{EasyChair:15459,
  author    = {Sumit Paul and David Knox},
  title     = {RouterORAM: an O(1)-Latency and Client-Work ORAM},
  howpublished = {EasyChair Preprint 15459},
  year      = {EasyChair, 2024}}