Architectures based on Oblivious RAM for Enhancing User Privacy and their Applications to Genome Processing

The all increasing need for data protection has given raise to a plethora of privacy preserving cryptographic techniques that address this issue. Early on however, it was made clear that in many cases, simply protecting the contents of the data is not enough: The way encrypted data is accessed can leak important information that spans from reverse-engineering of programs, to totally breaking the privacy of users, once they store it on remote servers. To answer this question, the cryptographic community developed various solutions among which one of the most prominent is Oblivious RAM (ORAM), which guarantees data privacy in remotely outsourced private data. Yet, the dominant model under consideration is that of one client and one server, which although necessary as a means of abstractly dealing with the general problem, still has limited applications in real-world scenarios. In this work, we develop ORAM architectures that address this problem and generalise the above study. In particular, we propose solutions that allow multiple clients to store their private data on remote servers and either share with each other parts of their data, or selectively give access to parts of their data to third parties. This way, we introduce the study of ``Partially Sharing Multi-Client ORAMs'' and give concrete instantiations of such ORAMs. Proving that our constructions are secure, required the development of a new framework that allows for arguing on the security of such complex architectures. To this extent, we developed a versatile framework for ORAM security that is more rigorous than the frameworks used in practise today and at the same time far easier to use than the original Goldreich-Ostrovsky framework. Under this light, we believe that our new framework will prove itself to be very useful also in showing security for ORAM constructions that will be developed in the future. In order to show the applicability of the architectures we developed, we implemented and applied them to a problem domain that we believe will be of great significance in the following years. In particular, we address the problem of privacy preserving genomic studies. Using our newly developed techniques, we can store, access and update encrypted sequenced genomes of multiple clients, and by employing secure computation techniques, we can further process the outsourced data for a variety of tests ranging from simple DNA fingerprinting to more complex Genome Wide Association Studies