Biblio

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.

Microblogging is a popular activity within the spectrum of Online Social Networking (OSN), which allows users to quicky exchange short messages. Such systems can be based on mobile clients that exchange their group-encrypted messages utilizing local communications such as Bluetooth. Since however in such cases, users do not want to disclose their group memberships, and thus have to wait for other group members to appear in the proximity, the message spread can be slow to non-existent. In this paper, we solve this problem and facilitate a higher message spread by employing a server that stores the messages of multiple groups in an Oblivious RAM (ORAM) data structure. The server can be accessed by the clients on demand to read or write their group-encrypted messages. Thus our solution can be used to add access pattern privacy on top of existing microblogging peer-2-peer architectures, and using an ORAM is a promising candidate to use in the given application scenario.