of providing a variant of Yao™s protocol which is secure against malicious ad-

versaries. In the current paper we examine one of the more recent and e¬cient

protocols for providing security for Yao™s protocol against malicious adversaries,

namely the protocol of Lindell and Pinkas [13] which is proved to be secure ac-

cording to a standard simulation based de¬nition, and as such can be securely

used as a primitive in more complex protocols (see [8, Chapter 7], which in turn

follows [6]).

Our work presents the following contributions:

“ We provide an e¬cient implementation of the protocol of [13], which is se-

cure against malicious adversaries. This is, to our best knowledge, the ¬rst

implementation of a generic two-party protocol that is secure against mali-

cious adversaries according to a standard simulation based de¬nition. The

implementation demonstrates the feasibility of the use of such protocols.

“ We derive a number of optimizations and extensions to the protocol and to

the di¬erent primitives that it uses. Unlike prior implementations we pay

particular attention to using the most e¬cient constructions for the vari-

ous components. For example we use elliptic curve based oblivious transfer

protocols instead of ¬nite ¬eld discrete logarithm based protocols.

1

The cryptographic community denotes adversaries which can operate arbitrarily as

“malicious”. Semi-honest (or honest but curious) adversaries are supposed to follow

the protocol that normal users are running, but they might try to gain information

from the messages they receive in the protocol. It is, of course, easier to provide

security against semi-honest adversaries.

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

“ We also examine the di¬erence between using protocols which are secure in

the random oracle model (ROM) and protocols in the standard model.2 Of

particular interest is that our results show that there appears to be very

little bene¬t in using schemes which are secure in the ROM as opposed to

the standard model.3

1.1 Related Work

Research on security against malicious adversaries for computationally secure

protocols started with the seminal GMW compiler [9]. As we have mentioned,

we base our work on the protocol of [13], and we refer the reader to that work

for a discussion of other approaches for providing security against malicious

adversaries (e.g., [14,11,23]). We note that a simulation based proof of security

(as in [13]) is essential in order to enable the use of a protocol as a building

block in more complex protocols, while proving the security of the latter using

general composition theorems like those of [6,8]. This is a major motivation

for the work we present in this paper, which enables e¬cient construction of

secure function evaluation primitives that can be used by other protocols. (For

example, the secure protocol of [2] for ¬nding the k th ranked element is based on

invoking several secure computations of comparisons, and provides simulation

based security against malicious adversaries if the invoked computations have a

simulation based proof. Our work enables to e¬ciently implement that protocol.)

The ¬rst generic system implementing secure two-party computation was Fair-

Play [15], which provided security against semi-honest adversaries and limited se-

curity against malicious adversaries (see discussion above). FairPlayMP is a generic

system for secure multi-party computation, which only provides security against

semi-honest adversaries [3]. Another system in the multi-party scenario is SIMAP,

developing a secure evaluation of an auction using general techniques for secure

computation [5,4]. It, too, supports only security against semi-honest adversaries.

1.2 Paper Structure

Section 2 introduces Yao™s protocol for secure two-party computation, while Sec-

tion 3 presents the protocol of [13] which is secure against malicious adversaries.

Section 4 presents the di¬erent e¬cient sub-protocols that we used. Finally,

Section 5 presents the results of our experiments.

2

A random oracle is a function which is modeled as providing truly random answers.

This abstraction is very useful for proving the security of cryptographic primitives.

However, given any speci¬c implementation of a function (known to the users who

use it), this assumption no longer holds. Therefore it is preferable to prove security

in the standard model, namely without using any random oracle.

3

This is surprising since for more traditional cryptographic constructions, such as

encryption schemes or signature schemes, the random oracle constructions are almost

always twice as e¬cient in practice compared to the most e¬cient standard model

schemes known. Part of the reason for the extreme e¬ciency of our standard model

constructions is our use of a highly e¬cient oblivious transfer protocol which reduces

the amortized number of zero-knowledge proofs which are required to be performed.

Implementing Two-Party Computation 5

2 Yao™s Garbled Circuit

Two-party secure function evaluation makes use of the famous garbled circuit

construction of Yao [24]. In this section we brie¬‚y overview the idea. Note, how-

ever, that the following basic protocol is not secure against malicious adversaries,

which is why the advanced protocol in the next section is to be preferred. The

basic idea is to encode the function to be computed via a Binary circuit and

then to securely evaluate the circuit on the players™ inputs.

We consider two parties, denoted as P1 and P2 , who wish to compute a func-

tion securely. Suppose we have a simple Binary circuit consisting of a single

gate, the extension to many gates given what follows is immediate. The gate has

two input wires, denoted w1 and w2 , and an output wire w3 . Assume that P1

knows the input to wire w1 , which is denoted b1 , and that P2 knows the input to

wire w2 , which is denoted b2 . We assume that each gate has a unique identi¬er

Gid (this is to enable circuit fan out of greater than one, i.e. to enable for the

output wire of a gate to be used in more than one other gate). We want P2 to

determine the value of the gate on the two inputs without P1 learning anything,

and without P2 determining the input of P1 (bar what it can determine from

the output of the gate and its own input). We suppose that the output of the

gate is given by the function G(b1 , b2 ) ∈ {0, 1}.

Yao™s construction works as follows. P1 encodes, or garbles, each wire wi by

0 1

selecting two di¬erent cryptographic keys ki and ki of length t, where t is a

computational security parameter which su¬ces for the length of a symmetric

encryption scheme. In addition to each wire it associates a random permutation

πi of {0, 1}. The garbled value of the wire wi is then represented by the pair

b

(ki i , ci ), where ci = πi (bi ).

s

An encryption function Ek1 ,k2 (m) is selected which has as input two keys

of length t, a message m, and some additional information s. The additional

information s must be unique per invocation of the encryption function (i.e.,

used only once for any choice of keys). The precise encryption functions used are

described in Section 4.1. The gate itself is then replaced by a four entry table

indexed by the values of c1 and c2 , and given by

Gid c1 c2 G(b1 ,b2 )

c 1 , c2 : E k3 c3 ,

b b

k11 ,k22

’1 ’1

where b1 = π1 (c1 ), b2 = π2 (c2 ), and c3 = π3 (G(b1 , b2 )). Note that each entry

in the table corresponds to a combination of the values of the input wires, and

contains the encryption of the garbled value corresponding to these values of the

input wires, and the corresponding c value. The resulting look up table (or set

of look up tables in general) is called the Garbled Circuit.

b

P1 then sends to P2 the garbled circuit, its input value k11 , the value c1 =

π1 (b1 ), and the mapping from the set {k3 , k3 } to {0, 1} (i.e. the permutation

01

π3 ). P1 and P2 engage in an oblivious transfer (OT) protocol so that P2 learns

b

the value of k22 , c2 where c2 = π2 (b2 ). P2 can then decrypt the entry in the

b b

look up table indexed by (c1 , c2 ) using k11 and k22 ; this will reveal the value of

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

G(b ,b )

k3 1 2 c3 and P2 can determine the value of G(b1 , b2 ) by using the mapping

’1

π3 from the set c3 to {0, 1}.

In the general case the circuit consists of multiple gates. P1 chooses random

garbled values for all wires and uses them for constructing tables for all gates.

It sends these tables (i.e., the garbled circuit) to P2 , and in addition provides P2

with the garbled values and the c values of P1 ™s inputs, and with the permutations

π used to encode the output wires of the circuit. P2 uses invocations of oblivious

transfer to learn the garbled values and c values of its own inputs to the circuits.

Given these values P2 can evaluate the gates in the ¬rst level of the circuit, and

compute the garbled values and the c values of the values of their output wires.

It can then continue with this process and compute the garbled values of all

wires in the circuit. Finally, it uses the π permutations of the output wires of

the circuit to compute the real output values of the circuit.