circuits.

7. Correctness and consistency checks: Player P2 performs the following

checks; if any of them fails it aborts.

(a) Checking correctness of the check-circuits: P2 veri¬es that each check-

circuit GCi is a garbled version of C.

(b) Verifying P2 ™s input in the check-circuits: P2 veri¬es that P1 ™s decom-

mitments to the wires corresponding to P2 ™s input values in the check-

circuits are correct, and agree with the logical values of these wires

(the indicator bits). P2 also checks that the inputs it learned in the

oblivious transfer stage for the check-circuits correspond to its actual

input.

(c) Checking P1 ™s input to evaluation-circuits: Finally, P2 veri¬es that for

every input wire i of P1 the following two properties hold:

i. In every evaluation-set, P1 chooses one of the two sets and decom-

mitted to all the commitments in it which correspond to evaluation-

circuits.

ii. For every evaluation-circuit, all of the commitments that P1 opened

in evaluation-sets commit to the same garbled value.

8. Circuit evaluation: If any of the above checks fails, P2 aborts and outputs

⊥. Otherwise, P2 evaluates the evaluation circuits (in the same way as for the

semi-honest protocol of Yao). It might be that in certain circuits the garbled

values provided for P1 ™s inputs, or the garbled values learned by P2 in the

OT stage, do not match the tables and so decryption of the circuit fails. In

this case P2 also aborts and outputs ⊥. Otherwise, P2 takes the output that

appears in most circuits, and outputs it.

3.2 The Statistical Security Parameters

The protocol uses two statistical security parameters, s1 and s2 . The parame-

ter s1 is mainly used to prevent P1 from changing the circuit that is evaluated,

or providing inconsistent inputs to di¬erent copies of the circuit. The protocol

requires P1 to provide s1 copies of the garbled circuit, and provide (s1 )2 commit-

ments for each of its input bits. The security proof in [13] shows that a corrupt

P1 can cheat with a success probability that is exponentially small in s1 . The

original proof in [13] bounds the cheating probability at 2’s1 /17 , which would

require a large value of s1 in order to provide a meaningful security guarantee.

We conjecture that a ¬ner analysis can provide a bound of 2’s1 /4 , and in the

full version of this paper we intend to prove this; this conjecture is based on an

analysis of a similar problem that was shown in [10]. A bound of 2’s1 /4 would

mean that a relatively moderate value of s1 can be used.6

The experiments in Section 5 assume a bound of 2’s1 /4 . The overhead of di¬erent

6

parts of the protocol is either linear or quadratic in s1 . If we end up using a worse

bound of 2’s1 /c , where 4 < c ¤ 17, the timings in the experiments will be increased

by factor in the range c/4 to (c/4)2 .

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

The parameter s2 is used to prevent a di¬erent attack by P1 , in which it

provides corrupt values to certain inputs of the oblivious transfer protocol and

then uses P2 ™s reaction to these values to deduce information about P2 ™s inputs

(see [13] for details). It was shown that setting the number of new inputs to be

= max(4n, 8s2 ) bounds the success probability of this type of attack by 2’s2 .

The values of s1 and s2 should therefore be chosen subject to the constraint

that the total success probability of a cheating attempt, max(2’s1 /4 , 2’s2 ), is

acceptable. Therefore, one should set s1 = 4s2 .

3.3 Optimizing the Protocol Components

The protocol uses many components, which a¬ect its overall overhead. These

include the encryption scheme, the commitment schemes, and oblivious transfer.

Much of our work was concerned with optimizing these components, in order to

improve the performance of the entire protocol. We describe in the next section

the di¬erent optimizations that we applied to the di¬erent components.

4 Subprotocols

To implement the above protocol requires us to de¬ne a number of sub-protocols:

various commitment schemes, OT protocols and encryption schemes. In what fol-

lows we select the most e¬cient schemes we know of, in both the random oracle

model (ROM) and the standard model. We assume that the concrete computa-

tional security parameter (as opposed to the statistical security parameter) is

given by t. By this we mean that we select primitives which have security equiv-

alent to t bits of block cipher security. Thus we ¬rst select an elliptic curve E of

prime order q ≈ 22t , and a symmetric cryptographic function with a t-bit key.

Elliptic curve. We let P = Q = E, an elliptic curve of prime order q ≈ 22t ,

where no party knows the discrete logarithm of Q with respect to P .

Symmetric cryptographic function. The function that will be used for sym-

metric key cryptography is de¬ned as a key derivation function KDF(m, l), which

takes an input string m and outputs a bit string of length l. We use the KDF

de¬ned in ANSI X9.63, which is the standard KDF to use in the elliptic curve

community [19]. It is essentially implemented as encryption in CTR mode where

the encryption function is replaced by the SHA-1 hash function.

4.1 Encryption Scheme for Garbled Circuits

s

The encryption scheme Ek1 ,k2 (m) used to encrypt the values in the Yao circuit

is de¬ned by the algorithms in Figure 1. We assume that ki ∈ {0, 1}t . The ROM

version is secure on the assumption that the function KDF is modelled as a

random oracle, whilst the standard model scheme is secure on the assumption

that KDF(k s, l) is a pseudo-random function, when considered as a function

on s keyed by the key k. We remark that the encryption is secure as long as

Implementing Two-Party Computation 11

the string s is used only once for any choice of key k. Note that the non-ROM

version requires two invocations of the KDF, since we do not know how to

analyze the security of a pseudo-random function if part of its key is known to

an adversary (namely, if we use KDF(k1 k2 s, |m|), where KDF is modeled as a

pseudo-random function, k2 is secret and k1 is known to an adversary, we cannot

argue that the output is pseudo-random).

Input: Keys k1 , k2 of length t, and a string s. For encryption an l-bit message m in

also given. For decryption, an l-bit ciphertext c is given.

ROM Version Non-ROM Version

s s

Encryption Ek1 ,k2 (m) Encryption Ek1 ,k2 (m)

1. k ← KDF(k1 k2 s, |m|). 1. k ← KDF(k1 s, |m|).

2. c ← k • m. 2. k ← KDF(k2 s, |m|).

3. c ← m • k • k

Decryption

Decryption

1. k ← KDF(k1 k2 s, |m|).

2. m ← k • c. k ← KDF(k1 s, |c|).

1.

3. Return m. k ← KDF(k2 s, |c|).

2.

m←c•k•k .

3.

Return m.

4.

Fig. 1. ROM and non-ROM encryption algorithms for the Yao circuits

4.2 Commitment Schemes

Recall we have three types of commitment schemes; statistically binding, statis-

tically hiding and computationally binding/hiding, to commit to a value m ∈

{0, 1}t. (Note that the elliptic curve E is of order q ≈ 22t and so we can view m

as a number in Zq if desired.)

A Statistically Binding Commitment : comb (m)

We de¬ne the statistically binding commitment scheme as in Figure 2. The ran-

dom oracle model based scheme is statistically binding, since to break the binding

property we need to ¬nd collisions in the hash function H. Since H is modelled

as a random oracle, the probability of any adversary ¬nding a collision given

a polynomial number of points of H is negligible, even if it is computationally

unbounded. The scheme is also computationally hiding by the fact that H is

modelled as a random oracle (in fact, it™s even statistically hiding if the adver-

sary is limited to a polynomial number of points of H). The non-ROM scheme

is statistically binding because P and c1 fully determine r, which together with

Q and c2 in turn fully determine m. The fact that it is computationally hiding

follows directly from the DDH assumption over the elliptic curve used.

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