Secure Computation with Sublinear Amortized Work

Secure Computation with Sublinear Amortized Work

S. Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Fernando Krell, Tal Malkin, Mariana Raykova, Yevgeniy Vahlis
CCS 2012 [pdf] [bibtex]

Presents a semi-honest-secure 2PC protocol based on oblivious RAM? evaluation rather than circuit evaluation. This allows, after a pre-processing phase to initialize the ORAM data structures, cost (in the online phase) that is sublinear in the total input size. The protocol is suited for situations where parties repeatedly evaluate ⚠ {$f(x_i,D)$} for many choices of a relatively short input ⚠ {$x_i$} and a common large input ⚠ {$D$}.

The main idea in the protocol is for two parties to hold secret shares of the internal state of an ORAM program for ⚠ {$f$}. They then repeatedly run a semi-honest 2PC that evaluates the RAM program's next-instruction circuit (i.e., the circuit that outputs the next read/write command). From the security of the ORAM, these memory instructions leak no information about the secret data and can be revealed in the clear. Then one party is tasked with managing the large ORAM memory: performing updates and reading data into the next-instruction circuit.

A specific ORAM construction is used, with additional optimizations to do as much work as possible outside of the next-instruction circuit 2PC. For instance, any ORAM construction will use encryption to protect the contents of its memory. With careful selection of encryption scheme, this encryption can be done outside of the circuit 2PC.

Overall the amortized cost of the protocol equals that of the RAM program times a polylog factor in the space complexity. The space requirements of the client (who holds only small inputs and does not manage the RAM memory during the protocol) is also logarithmic in the RAM's space complexity.

Categories:

Paradigms