Three Party ORAM for Secure Computation
An Oblivious RAM ORAM protocol [13] allows a client to retrieve \mathrm {N} th element of a data array \mathsf {D} stored by the server s.t. the server learns no information about \mathrm {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.i 3/4 given a secret sharing of both \mathsf {D} and \mathrm {N} it computes a secret sharing of \mathsf {D}\mathrm {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.
ASIACRYPT