Yao's garbled circuit


Jump to: navigation, search


Yao's garbled circuit is a method Proposed by Andy Yao in 1986 for Secure multiparty computation. This is a two party protocol. This protocol is only secure against an adversary from the Honest-but-curious adversary model.

First assume we are dealing with the two party case. At a high level the scheme is as follows: Bob creates a "garbled circuit", and sends the circuit to Alice. Alice evaluates the circuit with her inputs and returns the result to Bob. The result of the circuit evaluation with Alice's inputs is the output of the function Alice and Bob wish to compute. Note that Bob does not send his inputs to Alice, instead his inputs are encoded into the "garbled circuit" such that Alice can not determine what they are.

An example

  1. Initial Setup
    • Alice has x = 2 bits, (a,b)
    • Bob as y = 2 bits, (c,d)
    • f(x,y) = (a \or c) \and (b \or d)
  2. Construction of the garbled circuit
    • for each gate in the circuit, construct a new truth table for each gate. A sample truth table below is an AND gate, with inputs p, q and output z.
    • construct output decryption tables consisting of the pairs (0, K^0_z) and (1, K^1_z) for an output z.
  3. Evaluation
    • After Alice has received the circuit and corresponding truth tables, she needs Bob's inputs before she can evaluate the circuit.
    • For Alice to get these values, use a 1-out-of-2 Oblivious transfer protocol.
    • Once Alice has the input values from Bob, she can "decrypt" each of the gates, and using her inputs evaluate the circuit.

input input ouput garbled computation
k_q^0 k_p^0 k_z^0 E_{k_q^0}(E_{k_p^0}(k_z^0))
k_q^0 k_p^1 k_z^0 E_{k_q^0}(E_{k_p^1}(k_z^0))
k_q^1 k_p^0 k_z^0 E_{k_q^1}(E_{k_p^0}(k_z^0))
k_q^1 k_p^1 k_z^1 E_{k_q^1}(E_{k_p^1}(k_z^1))
Personal tools