Improved secure two-party computation via information-theoretic garbled circuits

Abstract. We optimize the communication (and, indirectly, compu-tation) complexity of two-party secure function evaluation (SFE). We propose a new approach, which relies on the 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 indepen-dent interest. Our approach offers asymptotic improvement over the state-of-the-art GC, both in communication and computation, by a factor log κ, where κ is a security parameter. In practical terms, already for today’s κ ∈ {128, 256} our (unoptimized) algorithm offers approximately a factor 2 communication improvement in the semi-honest model, and is only a factor ≈ 1.5 more costly in setting with covert client.