In Part 2 of our Garbled Circuit series, we saw that it would be possible to evaluate arbitrary functions privately (that is, without revealing the inputs to the function to be computed) if we had a way for Alice to send Bob some information he needs without Alice knowing what information Bob received. Although it seems intuitively impossible, there is a way for a Sender (Alice) to offer a set of possible messages to a Receiver (Bob), such that Bob gets exactly the message he wants from Alice but Alice doesn't know which message Bob received - even though she provided the message!
To understand how oblivious transfer works, a basic understanding of public key cryptography is required (see the end of this post for more details). Rather than having a private key shared between users (as with AES), each user of public key cryptography has two mathematically related keys: a private key k known only to the user, and a public key kG where G is a public parameter. The user can reveal their public key kG to anyone, but must never reveal their private key k. Even though other users know both G and kG, it is not possible to extract the user’s private key k.
Let’s walk through how this protocol works to understand why the Receiver can only recover one message, and why the Sender has no idea which message was received:
- The Sender begins by publishing a public key value kG, for which only they know the value k. Even though both kG and G are public, it is not possible for anyone else to recover k.
- The receiver now constructs a value that depends on which message, M0 or M1, they want. This value has to be “blinded” by the value rG, as otherwise it would be clear to the Sender which message they were selecting.
- To receive M0, they construct and send R = 0(kG) + rG = rG
- To receive M1, they construct and send R = 1(kG) + rG
- Since the Sender doesn’t know the value rG, they can’t distinguish (rG) from (rG + kG). The sender now constructs and returns two values, V0 and V1. Let’s work through what V0 and V1 will be based on which message the Receiver wants to recover:
Remember that the Receiver only has access to G, kG, and r, so he can only compute the unblinding value r(kG) by multiplying the random value r (which they selected) with the Sender public key kG. The blinding values in red cannot be computed by the Receiver, because the Receiver does not know k. Notice how the Receiver is able to successfully unblind the message Mb they selected by subtracting r(kG) from the corresponding Vb value. However, they cannot remove the blinding on V(1-b) as the Receiver doesn’t know the Sender’s private key k to compute k(rG - kG) or k(kG + rG). Thus, the Receiver recovers exactly the message they requested, while the Sender does not know which message they were able to recover!
Evaluator Steps (Bob)
Now that we've seen how Oblivious Transfer works, we're ready to finish our last post and complete the general solution for evaluating any function without any party having to reveal their input.
Once Alice has generated the garbled table, she sends her input key for Wire 1 and the Garbled Output column to Bob. To retrieve the input key for Wire 2 corresponding to Bob’s input bit b, he engages in an Oblivious Transfer protocol with Alice. This allows Bob to learn only the key corresponding to his input bit b, while Alice does not learn which input key Bob was able to recover. The garbled table is now in the following state:
Bob knows that the pair of input keys unlock exactly one of the garbled output entries, but since he doesn’t know which input bit Alice’s key corresponds to, he will have to attempt to decrypt all four entries. Only one of the decrypted entries will be in {0,1}, while the others will appear to be a random number. Bob now publishes the result, so that Alice and Bob both learn the result of the function while neither had to reveal their private input.
Applications of Garbled Circuits
The problem of computing a function with private inputs is known as Secure Multiparty Computation (MPC) or Secure Function Evaluation (SFE). Garbled circuits provide a solution to important problems across many different domains, including IP protection (evaluate a function without knowing what the function is), healthcare (analysis without disclosing medical records), biometrics (comparison without disclosing biometric measurements), private database-as-a-service (hosting and processing queries over customer data that is hidden to the processor), cloud-based machine learning (protecting a proprietary model from customers, and sensitive customer data from the processor) and more!