Improved Secure Two-Party Computation via Information-Theoretic Garbled Circuits

Improved Secure Two-Party Computation via Information-Theoretic Garbled Circuits

Vladimir Kolesnikov, Ranjit Kumaresan
SCN 2012 [pdf] [bibtex]

A new approach for semi-honest-secure 2PC is proposed. The main idea is to build on the information-theoretic secure garbling scheme proposed in K05. Having information-theoretic security, such garbled circuits require no cryptographic operations and are quite fast to evaluate. However, wire labels must grow exponentially in length with the depth of the circuit (i.e., input wire labels are exponentially longer than output wire labels).

The approach in this paper is to evaluate low-depth "slices" of the target circuit using the information-theoretic garbling. Then all that is required is a mechanism to "translate" the short garbled outputs of one slice into the long garbled inputs of the next slice.

The authors propose such a mechanism which they call string-select OT (SSOT). In SSOT, the sender provides four strings ⚠ {$(x_0, y_0, x_1, y_1)$}, and the receiver provides a selection string ⚠ {$x^*$}. If ⚠ {$x^* = x_b$}, then the receiver gets output ⚠ {$y_b$}. Essentially, SSOT ensures that the receiver cannot learn the input wire labels ⚠ {$y_0, y_1$} of the next slice without knowing (or guessing) the corresponding output wire labels ⚠ {$x_0, x_1$} of the previous slice. Importantly, ⚠ {$x_0, x_1$} may be short (constant-length), which precludes other non-interactive solutions like encrypting ⚠ {$y_b$} under the key ⚠ {$x_b$}.

Unlike the classical Yao 2PC protocol, the resulting protocol is interactive, with SSOTs happening for each slice of the circuit. By controlling the length of the garbled outputs of each slice (i.e., the ⚠ {$x_b$} values in SSOT), one can bound the probability of a corrupt receiver "flipping a bit" on a wire during the SSOT steps. Hence, covert security can also be achieved with this protocol.

An efficient protocol for SSOT is described, based on plain OTs. Concretely, the authors suggest using slices of depth 3 for security parameter 256, which leads to a factor 2 improvement in communication over the classical Yao's protocol.

Categories:

Paradigms