Random Access in Multiparty Computation

How can two strangers figure out how many phone contacts they have in common without revealing anything else about each other? Can this be done even in the absence of trusted third parties? How about the case of two strangers comparing genetic information to figure out how closely related they are? Many interesting applications have become possible with recent improvements in multiparty computation, and we are working to make it even more efficient and convenient to use.

In this talk, we will be focusing on random memory access in secure computation. In other words, we will try to efficiently solve the problem where a program needs to access a memory location without revealing which location is being accessed. The first part will be on specialized circuit structures that allow extremely efficient memory access for any circuit-based protocol (e.g. Yao, GMW), but only if the access pattern follows certain constraints. The second half of the talk will be a new Oblivious RAM construction that allows any arbitrary random access, but is less efficient. Although this problem had been “solved” in theory, past solutions only provide asymptotic benefits. They all had exorbitant initialization costs which dwarfed any per-access performance improvement they provided. Our construction provides a 100x improvement in initialization cost, and concrete benefits for as small as 144 bytes of data, inspite of being asymptotically inferior. We hope this will make secure multiparty computation easier to adopt in a greater variety of applications than was reasonable in the past.

No results