(DRAFT) Garbled Circuits for Three-Party Computation

Imagine a group of people have some private data, and they want to jointly compute a function of their private data, without sharing any of the data. Maybe they want to know the median of their salaries, without anyone revealing their own. Maybe a group of doctors wants to collaborate on a statistical study, without sharing any data about individual patients. This is the problem that multiparty computation solves.

If you haven't thought about this before, you'll want to start with the special case of two-party computation, which rests on Yao's garbled circuits protocol and a technique called oblivious transfer. This post by Gubsheep walks you through understanding how you would discover the protocol on your own. If you just want to see the protocol, Vitalik's post is also very good.

In this post I'm going to explain how to upgrade two-party computation to handle computations between three (or more) people, still using the basic idea of garbled circuits.

For this post, we're going to assume that all three parties carry out the protocol honestly… One could ask for stronger security guarantees. There are lots of different 3PC protocols, with different tradeoffs among security and complexity. There are also lots of good ideas that we won't get into in this blog post – for example, "cut-and-choose".

A three-party version of oblivious transfer

Alice has 4 messages:

$m_{00},m_{01},m_{10},m_{11}$. Bob and Carol each have a private bit – call them

$b$ and

$c$. Alice wants to transmit

$m_{bc}$ to Carol, in such a way that:

• Alice learns neither
  $b$ nor
  $c$
• Bob learns neither
  $c$ nor any information about the messages, and
• Carol learns neither
  $b$ nor any information about the other three messages.

If you've seen plain vanilla two-party oblivious transfer, it's not hard to come up with a protocol. Here's one:

• Alice randomly generates four symmetric encryption keys – two for Bob (
  ${\mathsf{Bobkey}}_0$ and
  ${\mathsf{Bobkey}}_1$) and two for Carol (
  ${\mathsf{Carkey}}_0$ and
  ${\mathsf{Carkey}}_1$).
• Alice performs a classical (two-party) oblivious transfer with Bob, sending him
  ${\mathsf{Bobkey}}_b$; Alice performs another OT with Carol, sending her
  ${\mathsf{Carkey}}_c$.
• Alice sends Bob this table.

(b, c)
(0, 0)	${\mathrm{Enc}}_{{\mathsf{Bobkey}}_0}({\mathrm{Enc}}_{{\mathsf{Carkey}}_0}(m_{00}))$
(0, 1)	${\mathrm{Enc}}_{{\mathsf{Bobkey}}_0}({\mathrm{Enc}}_{{\mathsf{Carkey}}_1}(m_{01}))$
(1, 0)	${\mathrm{Enc}}_{{\mathsf{Bobkey}}_1}({\mathrm{Enc}}_{{\mathsf{Carkey}}_0}(m_{10}))$
(1, 1)	${\mathrm{Enc}}_{{\mathsf{Bobkey}}_1}({\mathrm{Enc}}_{{\mathsf{Carkey}}_1}(m_{11}))$

• Bob uses
  ${\mathsf{Bobkey}}_b$ to decrypt the two messages
  ${\mathrm{Enc}}_{{\mathsf{Carkey}}_0}(m_{b0})$ and
  ${\mathrm{Enc}}_{{\mathsf{Carkey}}_1}(m_{b1})$, and sends them both to Carol.
• Carol uses
  ${\mathsf{Carkey}}_c$ to decrypt the one message
  $m_{bc}$.

Why is this secure?

• Alice doesn't learn anything about
  $b$ and
  $c$ because nobody sends her any messages (except as part of the original OT protocol, which we know is secure).
• Bob doesn't learn anything about
  $c$ because Carol never sends him any messages. He doesn't learn anything about any of the encrypted messages
  $m_{ij}$ because he doesn't know
  ${\mathsf{Carkey}}_0$ or
  ${\mathsf{Carkey}}_1$.
• Carol doesn't learn anything about
  $b$ because she only sees
  ${\mathrm{Enc}}_{{\mathsf{Carkey}}_0}(m_{b0})$ and
  ${\mathrm{Enc}}_{{\mathsf{Carkey}}_1}(m_{b1})$. She doesn't learn anything about the two messages
  $m_{i0}$ and
  $m_{i1}$ for
  $i\ne b$ because she never sees them, even in encrypted form; she doesn't learn the third message
  $m_{bk}$ for
  $k\ne c$ because she doesn't have the key to decrypt it.

Toward a 3PC Protocol

Let's make a couple of observations.

• What if Bob and Carol each have 2 bits (
  $b_0,b_1,c_0,c_1$), Alice has
  $2^4=16$ messages (
  $m_{0000},m_{0001},\dots ,m_{1111}$), and Alice wants to send Carol only the single message
  $m_{b_0,b_1,c_0,c_1}$ determined by Bob's 2 bits and Carol's 2 bits?

To make this work, Alice needs to give Bob (and Carol, but we'll focus on Bob for now) a

$\mathsf{Bobkey}$ for each of his two bits. So Alice chooses at random 4 symmetric keys,

${\mathsf{Bobkey}}_{0,0},{\mathsf{Bobkey}}_{0,1},{\mathsf{Bobkey}}_{1,0},{\mathsf{Bobkey}}_{1,1}$. Using two OTs, Alice transfers to Bob the key

${\mathsf{Bobkey}}_{0,b_0}$ corresponding to his first bit and the key

${\mathsf{Bobkey}}_{1,b_1}$ corresponding to his second bit. Now Bob computes a symmetric key

$\mathsf{Bobkey}=\mathrm{Hash}({\mathsf{Bobkey}}_{0,b_0},{\mathsf{Bobkey}}_{1,b_1})$. Alice does the same with Carol.

Now there are four possibilities for

$\mathsf{Bobkey}$ and four possibilities for

$\mathsf{Carkey}$, and Alice knows all of them. So Alice can publish a table – just like the table above, but with 16 rows – and at the end of the protocol, Carol learns only the one value she's supposed to.

In the actual protocol, Bob has 3 bits

$(b_0,b_1,b_2)$, Carol has 2 bits

$(c_0,c_1)$, and Alice's table has

$2^5=32$ rows.

Secret shares

Just like in the 2PC protocol, each bit

$x_i$ – each "wire" in the circuit – will be jointly held by Alice, Bob, and Carol, in the form of "secret shares". In other words: Alice will hold a bit

$a_i$, Bob

$b_i$, and Carol

$c_i$, with the property that

$a_i\oplus b_i\oplus c_i=x_i$.

In our protocol, Alice and Bob will choose her bit

$a_i$ at random. We might as well as choose Bob's shares

$b_i$ of gate output bits by simply setting them all equal to

$b_1$, Bob's first input bit. (This lets Alice send Bob his keys without using extra oblivious transfers.) And then

$c_i$ will be determined from the inputs to the gate,

$a_i$ and

$b_i$, by the rule

$c_i=a_i\oplus b_i\oplus x_i$.

The Protocol

Just as in the usual 2PC garbled circuits protocol, Alice sets up the initial "garbling" of the circuit.

We set up some notation first. Number Bob's inputs

$b_1,\dots ,b_m$ and

$c_{m+1},\dots ,c_{m+r}$. Number the gates

$G_{m+r+1},\dots ,G_{m+r+n}$, in some order (so that the inputs to each

$G_i$ are either inputs to the circuit, or outputs of previous gates).

Let's call all the bits (wires) in the circuit

$x_1,\dots ,x_{m+r+n}$. So

$x_1,\dots ,x_m$ is just another name for Bob's inputs

$b_1,\dots ,b_m$, and similarly for Carol's inputs. We'll call

$a_i,b_i,c_i$ the three parties' shares of the bit

$x_i$.

• For each gate
  $G_i$, Alice chooses at random her share
  $a_i$ of the output bit
  $x_i$.
• For each bit to be held by either Bob or Carol (this includes both their input bits to the circuit, and their shares of intermediate bits
  $x_i$), Alice chooses at random two keys, one for each value of the bit. So: for each
  $b_i$, Alice chooses
  ${\mathsf{Bobkey}}_{i,0}$ and
  ${\mathsf{Bobkey}}_{i,1}$. Similarly for Carol's bits
  $c_i$.
  • For Bob's shares of output bits, since we know
    $b_i=b_1$, we'll just use the same keys for Bob. So
    ${\mathsf{Bobkey}}_{i,b}={\mathsf{Bobkey}}_{1,b}$.
• For each gate
  $G_i$, Alice makes a 32-row table. Let
  $x_j$ and
  $x_k$ be the inputs to gate
  $G_i$. Then the table has the form:

(b_i, b_j, b_k, c_j, c_k)	${\mathrm{Enc}}_{\mathrm{Hash}({\mathsf{Bobkey}}_{i,b_i},{\mathsf{Bobkey}}_{j,b_j},{\mathsf{Bobkey}}_{k,b_k})}({\mathrm{Enc}}_{\mathrm{Hash}({\mathsf{Carkey}}_{j,c_j},{\mathsf{Carkey}}_{k,c_k})}(c_i:=x_i\oplus a_i\oplus b_i,{\mathsf{Carkey}}_{i,c_i})).$

• For each of Bob's and Carol's inputs

  $b_i$ and
  $c_i$, Alice sends Bob and Carol the keys
  ${\mathsf{Bobkey}}_{i,b_i}$ and
  ${\mathsf{Carkey}}_{i,c_i}$ by oblivious transfer – this is one OT per input bit to the circuit. (Note that Bob knows his keys for the whole circuit now, since they are all the same as his key
  ${\mathsf{Bobkey}}_{1,b_1}$.)

• Bob goes through each gate

  $G_i$ in order and uses his known key to decrypt the 4 rows of the table with his known values
  $b_i,b_j,b_k$. Bob then sends to Carol the 4 encrypted values
  $${\mathrm{Enc}}_{\mathrm{Hash}({\mathsf{Carkey}}_{j,c_j},{\mathsf{Carkey}}_{k,c_k})}(c_i:=x_i\oplus a_i\oplus b_i,{\mathsf{Carkey}}_{i,c_i}).$$

• Carol goes through the gates in order. For each gate

  $i$, she uses the known keys
  ${\mathsf{Carkey}}_{j,c_j},{\mathsf{Carkey}}_{k,c_k}$ to decrypt both
  $c_i$ and
  ${\mathsf{Carkey}}_{i,c_i}$.

• In the end, Carol computes her output bit

  $c_n$. She, Alice and Bob share their three bits
  $a_n,b_n,c_n$ to determine the final output
  $x_n=a_n\oplus b_n\oplus c_n$.

Security

First of all, notice that until the very last step information only ever travels from Alice –> Bob –> Carol. So (if the three parties don't communicate outside the protocol) Alice can't learn anything about Bob's or Carol's inputs, and Bob can't learn anything about Carol's.

Bob doesn't learn anything about Alice's inputs, either, since he only ever sees encrypted messages. And Carol only ever learns the bits

$c_i$, which are guaranteed to be uniformly random, because they are computed by

$c_i=a_i\oplus \text{stuff}$, and

$a_i$ is chosen uniformly at random.

But there's a more interesting question: If two of Alice, Bob and Carol team up, can they learn the third person's inputs?

Alice and Bob can't learn anything about Carol's inputs, because Carol never sends them any messages.

What can Bob and Carol learn? Even if they collaborate, they can't possibly learn more than the one row from each table. So they can learn

$b_i$ and

$c_i$ for each

$i$, but again that tells them nothing they didn't already know, because Bob chose

$b_i$ and

$a_i$ is random.

Alice and Carol can learn something, though. If Carol tells Alice which row of the table Bob sent her, Alice can work out Bob's bit

$b_i$. But

$b_i$ was the same as Bob's input bit

$b_1$. Even worse, once they know

$b_1$, they can figure out

$x_i$ for every

$i$.

Things get even worse if the players don't carry out the protocol honestly. Bob and Carol are constrained by the encryption: they only ever find out one key per bit, so they can only read the "correct" row of the table. But our protocol relies on Alice to garble the circuit correctly in the first place. Nothing stops a malicious Alice from writing any circuit she pleases.

We'll leave this as an example of a 3PC protocol and the level of security it affords – but if you want to know more, read about the "cut and choose" method.