Secure Two-Party Computation Is Practical

Secure Two-Party Computation Is Practical

Benny Pinkas, Thomas Schneider, Nigel P. Smart, Stephen C. Williams
ASIACRYPT 2009 [pdf] [bibtex]

In a circuit garbling scheme that uses the point-permute optimization, each wire {$i$} is associated with two wire labels {$W_i^0, W_i^1$} and a permute bit {$\pi_i$} so that {$W_i^{\pi_i}$} encodes "false" and {$W_i^{1 \oplus \pi_i}$} encodes true. The evaluator will eventually hold exactly one of these wire labels, {$W_i^{b_i}$} for some public select bit {$b_i$}.

This paper describes a method for row-reduction method, resulting in garbled gates of {$\sim 2k$} bits, where {$k$} is the security parameter. The classical Yao garbling approach requires {$4k$} bits, and prior optimization methods required {$3k$}.

The method works for any gate, but we give a sketch of the approach for an AND gate, where the permute bits are all zero. Let the gate have input wires {$i,j$} and output wire {$k$}, and {$W_i^0$}, {$W_j^0$}, {$W_k^0$} encode false on their respective wires. Very roughly, instead of choosing the output wire labels {$W_k^0, W_k^1$} randomly, we choose both of them implicitly as follows.

For {$a,b \in \{0,1\}$} define {$V_{a,b} = H(W_i^a, W_j^b)$}, where {$H$} is a random oracle or suitable KDF. Intuitively, an evaulator should be able to learn only one of the four {$V_{a,b}$} values, corresponding to the case that she knows {$W_i^a$} and {$W_j^b$}. The challenge is to arrange so that {$V_{0,0}$}, {$V_{0,1}$}, or {$V_{1,0}$} allow the evaluator to learn the "false" output wire label {$W_k^0$}, while {$V_{1,1}$} allows the evaluator to learn the "true" output wire label {$W_k^1$}.

Define {$P$} to be the unique degree-2 polynomial passing through points {$(1, V_{0,0}), (2, V_{0,1}), (3,V_{1,0})$}. Set {$W_k^0 := P(0)$}.

Then define {$Q$} to be the degree-2 polynomial passing through points {$(4,V_{1,1}), (5,P(5)), (6,P(6))$}. Set {$W_k^1 := Q(0)$}.

Now, the garbled circuit can simply contain the values {$P(5), P(6)$}. To evaluate, the evaluator holds {$W_i^a$} and {$W_j^b$}, and computes the degree-2 polynomial passing through {$(2a+b+1, H(W_i^a, W_j^b)), (5,P(5)), (6,P(6))$}. The polynomial will be either {$P$} or {$Q$} defined above, depending on the logical output of the AND-gate. The evaluator evaluates the polynomial on 0 to obtain the output wire label.

This method is incompatible with the Free XOR technique of KS08, since it sets both output wire labels {$W_k^0, W_k^1$} implicitly and unpredictably. Free XOR requires that each wire satisfy {$ W_k^0 \oplus W_k^1 = \Delta$} for some global {$\Delta$}, which is unlikely to hold when choosing wire labels according to this method.

Categories:

Garbling