Most existing general secure computation systems
rely on a circuit abstraction.
A computation task is first expressed as a circuit, and then
a protocol is performed to securely evaluate the circuit over
the parties' private inputs.
There is a mismatch between the circuit model and the
way in which real-world computational tasks are expressed,
namely, programs.
Real-life programs
are written assuming a Random Access Machine (RAM) model of computation,
assuming a CPU and memory unit offering random access capabilities.
Unfortuately, compiling a general RAM program into
a circuit incurs a O(T N) overhead, where
T is an upper-bound on the RAM's run-time, and N is the memory size.
One hard
problem encountered by such a RAM-to-circuit compiler is how to deal with
dynamic memory accesses, e.g. arr[idx] where idx is
a variable that depends on the parties' secret inputs.
The value of idx cannot be predicted in general at
compile time -- and therefore, a naive compilation approach would have to
copy the entire dataset into the circuit for every such dynamic
memory access.
Consequently, the circuit abstraction of secure computation
limits it to small inputs.
In an ongoing project, we are working on