MPC, or multi-party computation, is about how multiple parties can do shared computations on private inputs without revealing those private inputs.

Suppose you and your friend want to compare who's richer, but without revealing your net worths.

MPC allows us to accomplish this, by computing the function (x > y), where x and y are private inputs.

In general, MPC can be used to build all kinds of useful protocols, like threshold cryptography, dark pools, and private auctions (for sugar beets)!

For example, MPC can be used to jointly encrypt a message with AES, with the key split up among many different parties.

But what's the difference versus key splitting, like Shamir's Secret Sharing?

In secret sharing, the key has to get reassembled. At some point, some trusted party is going to have the entire key available to them. Trusted party could get compromised.

With MPC, the whole operation is done in MPC, meaning there's no point where the combined key could be extracted.

The MPC protocol we'll be building is Yao's Garbled Circuit protocol.

The idea behind garbled circuits is to encode the computation into a boolean circuit made of logic gates, then evaluate each of the logic gates in a MPC-like way.

To do this, we'll first need a primitive known as Oblivious Transfer. OT is MPC-complete, meaning it can be used to accomplish any MPC! But what is oblivious transfer?

Imagine I have two messages. I want to let you pick one of the messages, without seeing the other one. You also don't want to reveal which one you picked. Oblivious transfer accomplishes this.