Abstract
An exciting recent direction in MPC research is secure computation of RAM programs. A fundamental building block of MPC for RAM programs is SC-ORAM, i.e. a Secure Computation protocol of the Oblivious RAM functionality, which on input a secret-sharing of a memory address computes a secret-sharing of the corresponding memory record. The main idea for realizing SC-ORAM has been to create a client-server ORAM scheme (which guarantees privacy against the server storing the encrypted memory but not the client who retrieves it) whose client algorithm is "secure computation friendly", in the sense that secure computation techniques yield a plausibly efficient protocol for secure computation of the corresponding shared-input-to-shared-output functionality. So far most efforts on SC-ORAM were devoted to the two-party setting, but since an honest-majority setting makes secure computation fundamentally easier, it seems worthwhile to investigate whether SC-ORAM, and hence secure computation of RAM programs, can be realized more efficiently in this setting. We will report on some initial progress in this direction by describing a design of a 3-party SC-ORAM protocol whose implementation is about two orders of magnitude faster than existing 2-party SC-ORAM implementations, bringing SC-ORAM to within the ballpark of the client-server ORAM schemes.