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