Oblivious RAM: From Theory to Large-Scale Real-World Deployment with Elaine Shi | a16z crypto

TL;DR

Oblivious RAM (ORAM) is a simple algorithmic technique that protects the privacy of memory access patterns. It has applications in various fields, including blockchain, privacy-preserving transactions, and secure multi-party computation.

Transcript

uh all right good afternoon everyone uh welcome to today's a16z crypto research seminar very pleased to welcome Elaine she uh professor at Carnegie Mellon University uh Elaine has worked on all kinds of different things across computer science for example she was visiting us last summer give us talk then about mechanism design funnily enough today ... Read More

Key Insights

• 💪 ORAM is an algorithmic technique that protects the privacy of memory access patterns, providing strong security similar to encryption.
• 😷 Access pattern leakage is a general problem, affecting various domains such as social network analysis, medical data storage, and binary search.
• 🥳 ORAM has practical applications in blockchain systems, privacy-preserving transactions, smart contracts, and secure multi-party computation.
• ❓ Implementing ORAM in distributed scenarios requires additional considerations, such as Byzantine-resilience and fault tolerance.

Questions & Answers

Q: What is the purpose of Oblivious RAM?

Oblivious RAM (ORAM) is an algorithmic technique that hides memory access patterns, providing strong privacy protection for sensitive information, such as contact discovery in messaging apps or medical data storage.

Q: How does access pattern leakage occur?

Access pattern leakage occurs when the order and frequency of memory accesses reveal sensitive information, even when the data itself is encrypted. This leakage can lead to privacy breaches in various scenarios, such as social network graph identification or medical condition inference.

Q: What are some real-world applications of ORAM?

ORAM has practical applications in privacy-preserving transactions and smart contracts in blockchain systems, secure multi-party computation, and lightweight clients needing access to restricted data.

Q: How is ORAM implemented to address the overflow problem?

ORAM implementations use eviction processes to prevent overflow in memory buckets or nodes. The exact protocol for eviction depends on the specific ORAM algorithm being used, and it needs to be carefully designed to balance efficiency and security.

Questions and Answers:

Q: Can ORAM be used in distributed settings?

Yes, ORAM can be implemented in distributed settings by distributing the subtrees of the binary tree structure across different nodes. However, additional considerations need to be taken into account to ensure Byzantine-resilience and fault tolerance.

Q: How is good randomness ensured for ORAM algorithms?

Generating good randomness is crucial for ORAM algorithms. Randomness can be obtained from trusted sources or by utilizing secure randomness generation techniques. Cryptographic primitives like AES can also be used to stretch short random values into longer ones.

Summary & Key Takeaways

• Oblivious RAM (ORAM) obfuscates memory access patterns to protect sensitive information.

• Signal, a messenger app, used ORAM to enhance privacy in contact discovery by preventing access pattern leakage.

• Access pattern leakage is a general problem, affecting areas such as medical data storage, binary search, and image processing.

• ORAM has applications in blockchain, privacy-preserving transactions, and lightweight clients.