H is a hash function modeled as a random P and Q are elements on an elliptic

oracle. curve, as described above.

Commitment comb (m) Commitment comb (m)

1. r ← {0, 1}t . r ← Zq .

1.

2. c ← H(m r). c1 ← [r]P .

2.

3. Return c. c2 ← [r][m]Q.

3.

Return (c1 , c2 ).

4.

Decommitment

Decommitment

1. Reveal m and r.

2. Check if c = H(m r). Reveal m and r.

1.

3. Return m. Check if c1 = [r]P .

2.

Check if c2 = [r][m]Q.

3.

Return m.

4.

Fig. 2. ROM and non-ROM statistically binding commitment schemes

The Statistically Hiding Commitment : comh (m)

For the statistically hiding commitment scheme we use the Pederson commit-

ment [18]:

comh (m) ← [r]P + [m]Q

where r is a random number of size q and we treat m as an integer modulo q.

Note that 0 ¤ m < 2t < q < 22t . Decommitment is performed by revealing r

and m, and then verifying the commitment is valid. This is actually a perfectly

hiding commitment (since given comh (m) there exists, for any possible value

of m , a corresponding value r for which comh (m) = [r ]P + [m ]Q) and so in

particular the commitment is also statistically hiding. That the commitment is

computationally binding follows from the fact that any adversary who can break

the binding property can determine the discrete logarithm of Q with respect to P .

A Computational Commitment Scheme : comc (m)

We use the ROM version of the statistically binding commitment scheme in

Figure 2 for both the ROM and non-ROM commitments here. This is clearly

suitable in the ROM. Regarding the non-ROM case, this scheme is computation-

ally binding on the assumption that H is collision-resistant. Furthermore, it is

computationally hiding when H(m r) is modelled as a PRF with key r and mes-

sage m. We remark that when m is large, this latter assumption clearly does not

hold for typical hash functions based on the Merkle-Damg˚ paradigm (where

ard

given H(k m) one can easily compute H(k m m ) for some m ). However, it

is reasonable when m ¬ts into a single iteration of the underlying compression

function (as is the case here where m ∈ {0, 1}t and t is a computational security

parameter which we set to the value t = 128.).

Implementing Two-Party Computation 13

4.3 Oblivious Transfer

Recall in our main protocol we need to perform w = max(4n, 8s2 ) 1-out-of-

2 oblivious transfers in Stage 2. We batch these up so as to perform all the

OT™s in a single batch. The OT™s need to be performed in a manner which has

a simulation based proof of security against malicious adversaries, hence the

simple protocols of [17,1,12] are not suitable for our purposes (the simulation

based proof is needed in order to be able to use a composition of the OT protocol

in our protocol, see [6]). We therefore use a modi¬cation of the batched version

of the protocol of Hazay and Lindell [10], which we now describe in the elliptic

curve setting. (We note that this protocol has a simulation based proof of security

in the standard model, without any usage of a random oracle.)

We assume that P1 ™s input is two vectors of values

[x0 , . . . , x0 ] and [x1 , . . . , x1 ],

1 w 1 w

where |x0 | = |x1 |. Party P2 has as input the bits i1 , . . . , iw and wishes to obtain

j j

i1

the vector [x1 , . . . , xiw ].

w

We assume two zero-knowledge proofs-of-knowledge protocols which we shall

describe in Appendix A. The ¬rst, DL([x]P ; x), proves, in zero-knowledge, knowl-

edge of the discrete logarithm x of [x]P ; the second, DH(P, [a]P, [b]P, [ab]P ),

proves that the tuple P ,[a]P ,[b]P ,[ab]P is a Di¬e“Hellman tuple.

The protocol follows. The main things to notice are that the zero-knowledge

proofs of knowledge are performed only once, regardless of the number of items

to be transfered, and that protocol is composed of only two rounds (in addition

to the rounds needed by the zero-knowledge proofs).

1. P2 chooses ±0 , ±1 ∈ Zq and computes Q0 ← [±0 ]P and Q1 ← [±1 ]P , it then

executes the protocol DL(Q0 ; ±0 ) with party P1 .

2. For j = 1, . . . , w party P2 chooses rj ∈ Zq and computes Uj ← [rj ]P , V0,j ←

[rj ]Q0 + [ij ]P , V1,j ← [rj ]Q1 + [ij ]P . These values are then sent to P1 .

3. P1 chooses ρj ∈ Zq , for j = 1, . . . , w and sends them to P2 .

4. Both parties then locally compute

w w

U← V← [ρj ](V0,j ’ V1,j ).

[ρj ]Uj ,

j=1 j=1

Party P2 executes the protocol DH(P, Q0 ’ Q1 , U, V ) with party P1 .

5. For j = 1, . . . , w P1 then performs the following steps:

(a) Select R0,j , R1,j ∈ P at random.

(b) Select s0,j , t0,j , s1,j , t1,j ∈ Zq .

(c) Set e0,j ← (W0,j , Z0,j , y0,j ) where

W0,j ← [s0,j ]U + [t0,j ]P,

Z0,j ← [s0,j ]V0 + [t0,j ]Q0 + R0,j ,

y0,j ← x0 • KDF(R0,j , |x0 |).

j j

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

(d) Set e1,j ← (W1,j , Z1,j , y1,j ) where

W1,j ← [s1,j ]U + [t1,j ]P,

Z1,j ← [s1,j ](V1 ’ P ) + [t1,j ]Q1 + R1,j ,

y1,j ← x1 • KDF(R1,j , |x1 |).

j j

The values (e0,j , e1,j ) are then sent to P2 for each value of j.

6. For j = 1, . . . , w, party P2 then computes

R ← Zij ,j ’ [±ij ]Wij ,j

and outputs

i i

xjj ← yij ,j • KDF(R, |xjj |).

For each index in the vector of inputs, the protocol requires P1 to perform 10

multiplications, and P2 to perform 8 multiplications. (This is without consider-

ing the zero-knowledge proofs, which are performed once in the protocol.) The

security of the above scheme is fully proven in [10], with the only exception that

here a KDF is used to derive a random string in order to mask (i.e., encrypt) the

x0 and x1 values (in [10] it is assumed that x0 and x1 can be mapped into points

j j j j

in the Di¬e-Hellman group). The use of a KDF for this purpose was proven

secure in the context of hashed ElGamal in [22], on the assumption that KDF

is chosen from a family of hash functions which are entropy smoothing.

5 Timings

In our implementation we selected t = 128 as the security parameter. As a result,

we chose the KDF to be implemented by SHA-256, and as the elliptic curve E

we selected the curve secp256r1 from the SECG standard [20].

We performed a set of experiments which examined the system using a circuit

which evaluates the function x > y for inputs x and y of n = 16 bits in length.

The standard circuit (using simple 2-to-1 gates) for this problem consists of 61

2-to-1 gates and 93 internal wires. We optimized this circuit by replacing it with

a circuit consisting of 48 internal wires and ¬fteen 3-to-1 gates and one 2-to-1

gate. We only looked at the case of P2 obtaining the result, the extension to

the ¬rst party obtaining the result is standard and requires an extension to the