TL;DR
This paper introduces SOCS-ORAM, a novel Oblivious RAM (ORAM) scheme designed for scenarios where performance is paramount and a slight privacy trade-off is acceptable. By leveraging a semi-honest third party for preprocessing and allowing one participant to learn the access pattern, SOCS-ORAM achieves significantly faster memory access times than previous secure ORAM solutions, making it practical for real-world applications with hard performance constraints.
What Problem Does This Paper Address?
Data-dependent memory accesses are crucial for many real-world applications, but they pose a significant challenge in secure computation (MPC). Traditional ORAM solutions, while providing strong privacy guarantees by hiding access patterns, are often too slow for practical use, with some requiring seconds per access. This paper addresses the need for faster ORAM solutions in settings where extreme performance is required, even if it means relaxing some privacy guarantees. Specifically, they target scenarios where one party in the secure computation can be trusted with the access pattern information, and where a third party can assist in preprocessing.
Methods
The core contribution is the Shared-Output Client-Server ORAM (SOCS-ORAM) protocol. Key aspects of their approach include:
- Server-Aided Preprocessing: A semi-honest third party (C) assists in the initialization and reinitialization of the ORAM structure. This preprocessing step is performed outside of the main secure computation, significantly reducing the overhead during actual memory accesses.
- Pragmatic Privacy-Efficiency Trade-off: Unlike traditional ORAMs that hide access patterns from all parties, SOCS-ORAM allows one party (the client, A) to learn the access pattern. This relaxation is the key to achieving higher performance.
- Constant Overhead Access: The protocol is designed to have constant overhead per access, independent of the array size. This is achieved through efficient techniques like PRG expansion for generating randomness and a single round-trip interaction per access.
- Shared Output: The results of memory accesses are XOR secret-shared between the client (A) and the server (B), allowing them to be directly used in subsequent MPC computations without further decryption or processing.
- Initialization and Reinitialization: The protocol includes efficient protocols for initial setup and for reinitializing the ORAM to handle more accesses, which is crucial for dynamic applications.
Datasets
Not discussed in the paper. The evaluation uses synthetic data structures (arrays of varying sizes and entry types) to measure performance.
Key Insights and Ideas
- The "Trusted Observer" Model is Practical: The paper demonstrates that a model where one party can observe access patterns (while others remain oblivious) can unlock significant performance gains in secure computation. This is a valuable trade-off for many real-world applications.
- Preprocessing is Key to Performance: Offloading complex ORAM setup to a helper party significantly reduces the latency of individual memory accesses, making ORAM viable for time-sensitive applications.
- Constant Access Overhead is Achievable: By carefully designing the protocol and leveraging techniques like PRG expansion, the authors show that ORAM access can be made nearly as fast as plaintext access, with overhead primarily limited by network latency.
- Shared Output Simplifies MPC Integration: Providing access results as XOR secret shares directly integrates with MPC protocols, avoiding additional costly operations.
Key Results
The paper presents a highly efficient implementation of SOCS-ORAM.
- Communication: For an array of 2^30 entries (4GB) with 4B entries, they achieve 13B of communication per access.
- Latency: On a low-latency network (2ms RTT), the wall-clock time for an access is essentially network latency, around 2.13ms.
- Initialization: For a 2^30 entry array and 2^20 accesses, initialization takes about 3.1 minutes and communicates 8GB. Reinitialization costs are similar.
- Comparison to Prior Work: This is a significant improvement over previous state-of-the-art 3-party SC-ORAMs, which reported around 0.7s CPU time per access. SOCS-ORAM achieves this speed with minimal computational overhead beyond network latency.
Limitations and Future Work
- Relaxed Privacy: The primary limitation is that one party (A) learns the access pattern. This makes SOCS-ORAM unsuitable for scenarios requiring full access pattern privacy from all participants.
- Semi-Honest Model: The security guarantees are for the semi-honest corruption model.
- Future Work: The authors briefly mention an optional extension to hide the operation (read/write) from party B, which would require an additional communication flow. Further exploration of this and other optimizations could enhance the protocol's applicability. They also suggest that the "trusted observer" model could be beneficial in other secure computation contexts.
Summary updated