UC Irvine

An Oblivious RAM (ORAM) protocol allows a client to access memory outsourced at the server without leaking the access pattern. A related notion is Multi-Party Computation ORAM (MPC-ORAM), which is a protocol that can implement the RAM functionality for secure computation of any RAM programs on large data, e.g., MPC processing of database queries on a secret-shared database. MPC-ORAM can be constructed from any (client-server) ORAM by implementing the ORAM client algorithm with MPC protocols. However, efficient ORAM does not necessarily translate to efficient MPC-ORAM. Most previous work constructed efficient MPC-ORAM in the two-party secure computation (2PC) setting, but since secure computation of many functions is more efficient in the three-party honest-majority setting than in the two-party setting, it is natural to ask if the cost of an MPC-ORAM scheme can be reduced if one is willing to use three servers instead of two and assumes an honest majority. In this study, we show four constructions of MPC-ORAM in the three-party setting (3PC-ORAM) with honest majority, using customized 3PC protocols for performance optimization, which can make the resulting 3PC-ORAM schemes to be orders of magnitude more efficient than the current best 2PC-ORAM schemes. These improvements help to achieve practical and efficient performance results, and make MPC-ORAM more suitable for real world applications.