Data-dependent accesses to memory are necessary for many real-world applications, but their cost remains prohibitive in secure computation. Prior work either focused on minimizing the need for data-dependent access in these applications, or reduced its cost by improving oblivious RAM for secure computation (SC-ORAM). Despite extensive efforts to improve SC-ORAM, the most concretely efficient solutions still require \(\approx 0.7\) s per access to arrays of \(2^{30}\) entries. In this work, we take a pragmatic approach, exploring how concretely cheap MPC RAM access could be made if we are willing to allow one of the participants to learn the access pattern. We design a highly efficient Shared-Output Client-Server ORAM ( \(\textsf {SOCS-ORAM}\) ) that has constant overhead, uses one round trip of interaction per access, and whose access cost is independent of array size. \(\textsf {SOCS-ORAM}\) is useful in settings with hard performance constraints, where one party in the computation is more trust-worthy and is allowed to learn the RAM access pattern. Our \(\textsf {SOCS-ORAM}\) is assisted by a third helper party that helps initialize (and reinitialize, as needed) the protocol and is designed for the honest-majority semi-honest corruption model. We implement our construction in C++ and report its performance. For an array of length \(2^{30}\) with 4B entries, we communicate 13B per access and take essentially no overhead beyond network latency.
