Examining Leakage of Access Counts in ORAM Constructions

Oblivious RAM is a cryptographic primitive that embodies one of the cornerstones of privacy-preserving technologies for database protection. While any Oblivious RAM (ORAM) construction offers access pattern hiding, there does not seem to be a construction that is safe against the potential leakage due to knowledge about the number of accesses performed by a client. Such leakage constitutes a privacy violation, as client data may be stored in a domain specific fashion. In this work, we examine this leakage by considering an adversary that can probe the server that stores an ORAM database, and who takes regular snapshots of it. We show that even against such a weak adversary, no major ORAM architecture is resilient, except for the trivial case, where the client scans the whole database in order to access a single element. In fact, we argue that constructing a non-trivial ORAM that is formally resilient seems impossible. Moreover, we quantify the leakage of different constructions to show which architecture offers the best privacy in practice.