constructed of simple gates which take at most two inputs and produce as most

one output. In a Yao circuit a gate which takes n inputs and produces m outputs

is encoded as a look up table which has 2n rows, each consisting of a string of

O(m · t) bits (where t is the security parameter which denotes the length of a

key). Hence, it is often more e¬cient to use non-standard gates in a Yao circuit

construction. For example a traditional circuit component consisting of k 2-to-1

gates, with n input and m output wires can be more e¬ciently encoded as a

single n-to-m gate if 4k > 2n . In what follows we therefore assume the more

suitable n-to-m gate construction. The extension of the above gate description

to this more general case is immediate.

3 The Lindell-Pinkas Protocol

The protocol was presented in [13] and was proved there to be secure according

to the real/ideal-model simulation paradigm [6,8]. The proof is in the standard

model, with no random oracle model or common random string assumptions. We

describe below the protocol in some detail, for full details see [13]. We remark

that this description is not essential in order to understand the results of our

paper. The important things to note are the basic structure of the protocol,

as described in the next paragraph, and the fact that the protocol is based

on the use of di¬erent types of commitments (statistically binding, statistically

hiding, and computational), and of an oblivious transfer protocol. We describe

the implementation of these primitives in Section 4.

The basic structure of the protocol: The protocol proceeds in the following

steps. It has statistical security parameters s1 and s2 . We replace P2 ™s input wires

with a new set of O(s2 ) input wires, and change the original circuit by adding

to it a new part which translates the values of the new input wires to those of

the original wires. Then P1 generates s1 copies of Yao circuits and passes them

to P2 , along with O(s2 ) commitments to the inputs. The input decommitments

1

for P1 ™s inputs are transferred to P2 via a batched oblivious transfer. Finally,

after executing a number of cut-and-choose checks on the transferred circuits and

Implementing Two-Party Computation 7

commitments, P2 evaluates half of the circuits and determines the output value

as the majority value of the outputs of these circuits. One of the contributions

of this paper is to examine each of the above operations in turn and optimize

the parameters and components used in the Lindell-Pinkas description.

3.1 The Protocol in Detail

As explained in [13] it su¬ces to present a protocol for the case where the output

is learnt by P2 and P1 learns nothing. We consider the computation of f (x, y)

where P1 ™s input is x ∈ {0, 1}n and P2 ™s input is y ∈ {0, 1}n.

The protocol is parameterized by two statistical security parameters s1 and s2 .

(In [13] these are a single statistical security parameter but we shall see later that

in order to optimize performance these parameters really need to be treated sepa-

rately.) The protocol takes as input a circuit description C 0 (x, y) which describes

the function f (x, y). We use the notation comb to refer to a statistically binding

commitment scheme, comh to refer to a statistically hiding commitment scheme,

and comc to refer to a commitment scheme which is only computationally binding

and hiding. See Section 4 for our precise choice of these protocols.

The protocol itself is quite elaborate, but, as demonstrated in Section 5, it

can be implemented quite e¬ciently.

0. Circuit construction: The parties replace C 0 , in which P2 has n input

wires, with a circuit C in which P2 has input wires, where = max(4n, 8s2 ).

The only di¬erence between the circuits is that each original input wire of P2

in C 0 is replaced with an internal value which is computed as the exclusive-

or of a random subset of the input wires of C. (Given an input to the

original circuit, P2 should therefore choose a random input to the new circuit,

subject to the constraint that the internal values are equal to the original

input values.) The exact construction is presented in Section 5.2 of [13]. (In

order to avoid unnecessary extra gates in the circuit segment that computes

the original input wires as a function of the new input wires, we designed

the exact wiring using a variant of structured Gaussian elimination.)

We let the new input wires of P2 be given by y ← y1 , . . . , y .

ˆ ˆ ˆ

1. Commitment construction: P1 constructs the circuits and commits to

them, as follows:4

(a) P1 constructs s1 independent copies of a garbled circuit of C, denoted

GC1 , . . . , GCs1 .

(b) P1 commits to the garbled values of the wires corresponding to P2 ™s input

to each circuit. That is, for every input wire i corresponding to an input

bit of P2 , and for every circuit GCr , P1 computes the ordered pair

(c0 , c1 ) ← (comc (ki,r ), comc (ki,r )),

0 1

i,r i,r

b

where ki,r is the garbled value associated with b on input wire i in circuit

GCr . We let (dc0 , dc1 ) denote the associated decommitment values.

i,r i,r

4

In [13] this commitment is done with a perfectly binding commitment scheme, how-

ever one which is computationally binding will su¬ce to guarantee security.

8 Y. Lindell, B. Pinkas, and N.P. Smart

(c) P1 computes commitment-sets for the garbled values that correspond

to its own inputs to the circuits. That is, for every wire i that corre-

sponds to an input bit of P1 , it generates s1 pairs of commitment sets

{Wi,j , Wi,j }s1 , in the following way:

j=1

b

Denote by ki,r the garbled value that was assigned by P1 to the value

b ∈ {0, 1} of wire i in GCr . Then, P1 chooses b ← {0, 1} and computes

Wi,j ← comc (b), comc (ki,1 ), . . . , comc (ki,s1 ) ,

b b

Wi,j ← comc (1’b), comc (ki,1 ), . . . , comc (ki,s1 ) .

1’b 1’b

There are a total of n · s1 commitment-sets (s1 per input wire). We

divide them into s1 supersets, where superset Sj is de¬ned to be the set

containing the jth commitment set for all wires. Namely, it is de¬ned as

Sj = {(Wk,j , Wk,j )}n . k=1

2. Oblivious transfers: For every input bit of P2 , parties P1 and P2 run a

1-out-of-2 oblivious transfer protocol in which P2 receives the garbled values

for the wires that correspond to its input bit (in every circuit).

Let i1 , . . . , iw be the input wires that correspond to P2 ™s input, then, for

every j = 1, . . . , w, parties P1 and P2 run a 1-out-of-2 OT protocol in which:

(a) P1 ™s input is the pair of vectors [dc0j ,1 , . . . , dc0j ,s1], and [dc1j ,1 , . . . , dc1j ,s1].

i i i i

y

ˆ y

ˆ

(b) P2 ™s input are the bits yj , and its output should be [dcijj,1 , . . . , dcijj,s1 ].

ˆ

3. Send circuits and commitments: P1 sends to P2 the garbled circuits, as

well as all of the commitments that it prepared above.

4. Prepare challenge strings:5

(a) P2 chooses a random string ρ2 ← {0, 1}s1 and sends comh (ρ2 ) to P1 .

(b) P1 chooses a random string ρ1 ∈ {0, 1}s1 and sends comb (ρ1 ) to P2 .

(c) P2 decommits, revealing ρ2 .

(d) P1 decommits, revealing ρ1 .

(e) P1 andP2 set ρ ← ρ1 • ρ2 .

The above steps are run a second time, de¬ning an additional string ρ .

5. Decommitment phase for check-circuits: We refer to the circuits for

which the corresponding bit in ρ is 1 as check-circuits, and we refer to the

other circuits as evaluation-circuits. Likewise, if the jth bit of ρ equals 1,

then all commitments sets in superset Sj = {(Wi,j , Wi,j )}n are referred to

i=1

as check-sets; otherwise, they are referred to as evaluation-sets.

For every check-circuit GCr , party P1 operates in the following way:

(a) For every input wire i corresponding to an input bit of P2 , party P1 de-

commits to the pair (c0 , c1 ).

i,r i,r

(b) For every input wire i corresponding to an input bit of P1 , party P1 de-

commits to the appropriate values in the check-sets {Wi,j , Wi,j }.

For every pair of check-sets (Wi,j , Wi,j ), party P1 decommits to the ¬rst

value in each set i.e., to the value that is supposed to be a commitment to

the indicator bit, com(0) or com(1)).

5

In [13] it is proposed to use perfectly binding and computationally hiding com-

mitments here, but statistically binding and computationally hiding commitments

actually su¬ce.

Implementing Two-Party Computation 9

6. Decommitment phase for P1 ™s input in evaluation-circuits: P1 de-