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