Technology Background: Garbled Circuits Part 3

In this part we look at a key part of Yao’s Garbled Circuit protocol for two party MPC, namely the Oblivious Transfer (OT) protocol. OT is a key building block in various MPC protocols, and in some sense it is the most basic building block of all.

An OT protocol is a protocol between two parties, a sender and a receiver. The sender has two messages m_0 and m_1, where as the receiver has a single bit b ∈ {0,1}. At the end of the protocol the sender learns nothing about the bit b, and the receiver learns nothing about the message m_{1-b}. But the receiver does learn the message m_b.

To produce a fully secure OT protocol is a little complicated, but a simple protocol (which should not be used in practice, but which does illustrate the basic ideas) is quite easy to define using ElGamal on an elliptic curve as follows.

Let E be an elliptic curve with a point P of prime order q. We assume that we have a point C on E for which no one knows the discrete logarithm of C with respect to P. Such a point C can be produced using a simple hashing procedure.

The senders two messages are assumed to be points on the curve of order q, M_0 and M_1. Obviously we can use these “messages” as keys to encrypt real messages in a real application, but lets make this simplification for our purposes.

To execute the OT protocol the receiver first generates a private key x_b for the bit b they want to select. They then compute

Q_b = [x_b] P

Q_{1-b} = C-Q_b

Notice, that the receiver does not know the discrete logarithm of Q_{1-b} with respect to P, as they do not know the discrete logarithm of C with respect to P.

The two point Q’_0 = Q_0 is sent to the sender.

The sender then computes

Q’_1 = C-Q’_0

Note, if b=0 then Q’_1 = Q_1 as computed by the receiver, and if b=1 then Q’_1 =C-Q_0 =C-(C-Q_1) = Q_1 as computed by the receiver.

The sender then computes two “linked” ElGamal encryptions using Q’_0 and Q’_1 as the public keys.

C = [k] P

C_0 = [k] Q’_0 + M_0

C_1 = [k] Q’_1 + M_1

The values (C, C_0, C_1) are sent to the receiver, who can then recover M_b from…

C_b-[x_b] C = C_b-[x_b * k] P = C_b-[k]Q_b = M_b

The above protocol has a number of problems if used in “real life” as it does not protect either party against the other party cheating, i.e. giving invalid responses. But the protocol gives you the basic idea as to how OT protocols can be defined.