Developing a Science for Statistical ORAMs
Abstract
The security and privacy or sensitive user data is under threat due to untrusted components in our computing platforms. In particular, when sensitive data is outsourced to untrusted memory or to cloud servers, then untrusted servers have the ability to analyze the memory access patterns to infer sensitive information about user operations (including cryptographic keys). Note that even when data is encrypted, memory access patterns are still revealed to malicious memory components, and such attacks present a critical vulnerability in the design of deployed systems. Traffic analysis attacks using memory access patterns have motivated the design of approaches that are able to protect the security/privacy of user/program s memory access patterns (also known as oblivious RAMs). However, previous efforts to design oblivious RAMs suffer from high overheads (100x-200x), making them hard to deploy in real-world applications. In this proposal, we aim to develop a scientific foundation for protecting the security/privacy of programs memory access patterns. We propose to explore a fundamentally novel approach of reducing ORAM overhead/bandwidth at the cost of statistical yet rigorous privacy guarantees (such as differential privacy). The intersection of differential privacy and oblivious RAMs opens up a new design space for our research community, and has the potential to support a constant overhead design point (providing several orders of magnitude improvement over state-of-the-art). Our key intellectual contributions include: (1) We will investigate metrics from the domain of statistical data privacy, that can rigorously quantify privacy leakage from memory access patterns. ln particular, we will explore and formalize the notion of a differentially private ORAM that provides statistical privacy guarantees, and which to the extent of our knowledge, is the first of its kind. (2) We will explore a new scientific theory, along with the design of associated algorithms, that can achieve desired tradeoffs between ORAM bandwidth and ORAM security. Our theory will allow ORAM protocols to be tailored as per the needs and constraints of the user application, serving as an enabler for practical deployment. (3) We will evaluate the security and performance of our approach both theoretically and using a real-world prototype implementation. We will rigorously characterize the security of our approach, as well as security-overhead tradeoffs (including fundamental limits). Our proposal provides a transformative capability to end users for protecting their memory access patterns against untrusted cloud and computational platforms. Cloud applications such as Dropbox and Google Drive are becoming increasingly popular, and our approach directly impacts the security of these users. Similarly, our approach is applicable at the chip level in the design of secure processors. Overall, our proposed work can have broad impact on the field of computing platforms, and directly furthers the ability of the armed forces to operate in untrusted computing environments.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 14, 2019
- Source ID
- W911NF1810312
Entities
People
- Prateek Mittal
Organizations
- Army Contracting Command
- Princeton University
- United States Army