CSE Colloquium: Samee Zahur Al Islam

Title: Tools and techniques for secure multiparty computation

Abstract:

Can two strangers figure out how many phone contacts they have in common without revealing anything else in their contact list? 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 memory locations without revealing which locations are 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 have 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 a more useful tool in a wider variety of interesting applications which were impossible in the past.