Efficiency Improvements for Two-party Secure Computation
23 February 2012
We optimize the communication (and, indirectly, computation) complexity of two-party secure function evaluation (SFE). We propose a new approach, which relies on the {em information-theoretic} (IT) Garbled Circuit (GC), which is more efficient than Yao's GC on shallow circuits. When evaluating a large circuit, we ``slice'' it into thin layers and evaluate them with IT GC. Motivated by the client-server setting, we propose two variants of our construction: one for semi-honest model (relatively straightforward), and one secure against a semi-honest server and covert client (more technically involved). One of our new building blocks, String-selection Oblivious Transfer (SOT), may be of independent interest. Our approach, asymptotically, offers communication and computation improvement factor logarithmic in security parameter $kappa$, over standard state-of-the-art GC. In practical terms, already for today's $kappa in {128,256}$ our (unoptimized) algorithm offers approximately a factor $2$ communication improvement in the semi-honest model, and is only a factor $approx 1.5$ more costly in setting with covert client.
