An Oblivious RAM (ORAM) protocol [13] allows a client to retrieve N-th element of a data array D stored by the server s.t. the server learns no information about N. A related notion is that of an ORAM for Secure Computation (SC-ORAM) [17], which is a protocol that securely implements a RAM functionality, i.e. given a secret-sharing of both D and N, it computes a secret-sharing of D[N]. SC-ORAM can be used as a subprotocol for implementing the RAM functionality for secure computation of RAM programs [7,14,17]. It can also implement a public database service which hides each client's access pattern even if a threshold of servers colludes with any number of clients. Most previous works used two-party secure computation to implement each step of an ORAM client algorithm, but since secure computation of many functions becomes easier in the three-party honest-majority setting than in the two-party setting, it is natural to ask if the cost of an SC-ORAM scheme can be reduced if one was willing to use three servers instead of two and assumed an honest majority. We show a 3-party SC-ORAM scheme which is based on a variant of the Binary Tree Client-Server ORAM of Shi et al. [20]. However, whereas previous SC-ORAM implementations used general 2PC or MPC techniques like Yao's garbled circuits, e.g. [14,22], homomorphic encryption [11], or the SPDZ protocol for arithmetic circuits [15], our techniques are custom-made for the three-party setting, giving rise to a protocol which is secure against honest-but-curious faults using bandwidth and CPU costs which are comparable to those of the underlying Client-Server ORAM.
展开▼
