Secure 2-party computation (2PC) is becoming practical in some domains. However, most approaches are limited by the fact that the desired functionality must be represented as a boolean circuit. In response, the random-access machine (RAM) model has recently been investigated as a promising alternative to circuits.

 

In this talk, I will discuss some pitfalls of basing malicious-secure 2PC on the RAM model rather than circuits. I will then describe two new protocols for malicious-secure 2PC of RAM programs, whose performance relative to the semi-honest model matches the state of the art for circuit-based 2PC techniques. For malicious security with statistical security parameter s, our protocol without preprocessing has overhead s compared to the semi-honest model; our protocol with preprocessing has overhead roughly 2s/\log T, where T is the running time of the RAM program.