## 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