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:
- Home page
- All papers, by:
- .. category
- .. author names
- .. publication date
- .. recently added
- .. recently updated
- Glossary
- About
- Just getting started in MPC?
- Guidelines
- Todo List
Search Papers
Bibliography Categories