Welcome to the resource topic for 2025/1057
Title:
Efficient Mixed-Mode Oblivious RAMs
Authors: Wenhao Zhang, Xiao Wang, Chenkai Weng
Abstract:Oblivious RAMs (ORAMs) allow data outsourcing to servers so that the access pattern to the outsourced data is kept private. It is also a crucial building block to enable private RAM access within secure multi-party computation (MPC). In recent years, schemes that match the ORAM lower bound have been proposed in both the outsourcing setting and the RAM-model MPC setting, seemingly putting an epilogue in the theory of ORAM. In this paper, we initiate a study of mixed-mode ORAMs, where accesses to the ORAM are a mix of both public and private accesses. Although existing ORAMs can support public access by treating them as private ones, achieving better efficiency is highly non-trivial.
-
We present a mixed-mode ORAM algorithm, assuming the existence of private information retrieval (PIR). When the PIR scheme is communication-efficient, this ORAM achieves the best possible outcome: it has a bandwidth blowup of O(\log N) for private accesses and O(1) for public accesses. This construction can be easily extended for the MPC setting achieving O(B\log N ) circuit size for private accesses to B-sized blocks and O(B) circuit size for public accesses to the same array.
-
We instantiate the above protocol in the three-party computation (3PC) setting with more concrete optimizations, yielding a protocol that performs almost as efficiently as state-of-the-art RAM-3PC protocols for private accesses while being 3\times more efficient for public accesses in the LAN setting.
ePrint: https://eprint.iacr.org/2025/1057
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .