Secure Multi Party Computation With Sublinear (Amortized) Input Access
17 January 2011
We propose a new mechanism for secure two party computation using a combination of Random Access Machines (RAM) and traditional MPC. RAMs [CookReckhow73] are a natural computational model, where an algorithm has direct access to the memory space. As secure two party computation protocols mature, we begin to identify and address bottlenecks in performance that stem from fundamental properties of the current techniques. One of the main such bottlenecks is the fact that MPC is based on boolean or arithmetic circuits, rather than Turing machines, or RAMs. Circuits, even if evaluated insecurely, must separately encode and process every possible evaluation path (e.g., both branches of if statements must be evaluated). In particular, the description of a boolean circuit must be at least as long as the input to the algorithm that the circuit encodes. When computing on large inputs, e.g., when accessing a database, this is prohibitive. For example, any type of search on sorted DB will always require accessing all records, instead of the logarithmic cost of the (insecure) binary search. The state of affairs is that there are currently no satisfactory solutions for privately computing on large databases.
