You have been shipwrecked on a remote island and need to escape. One of the other survivors discovers an abandoned air strip with a small airplane that appears to still be in working condition. Unfortunately, the combined weight of you and the other survivors may exceed the airplane’s maximum takeoff weight WMAX. To decide whether attempting takeoff means a chance at survival or certain death, you need to know the combined weight of all of the survivors.

Although this is an emergency, you would prefer not to require anyone to reveal their weight to anyone – not even to yourself. How would you determine the total weight of the survivors, while ensuring that no one learns anyone else’s weight?

Pause for a moment and consider how the survivors could solve the problem. Remember that no one can learn anyone else’s weight. We’ll cover one candidate solution shortly.

This is an example of a broader class of problems: how can a group of participants compute the output of a function when their inputs to the function must remain private?

One straightforward solution is to give all of the private inputs to some trusted third party (TTP), who will then compute the function and distribute the output to the participants. Unfortunately, TTPs tend to be just as rare in the real world as they are for our survivors (who have never met before) in math world. For example, medical research could be accelerated if patient records were shared and aggregated at some centralized authority, but HIPAA privacy protections mandate that the records remain private. 

If the inputs to the weight-threshold function were not required to remain private, we could easily solve the problem with a piece of scratch paper. If the survivors escape, they could go on to build a circuit that would implement the weight-threshold function: on input a set weights and a threshold, output whether or not the combined weight exceeds the threshold. This blog will introduce garbled circuits, the general solution for the case where the inputs must remain private.

But first, let’s return to the survivors – they need a simple solution that works on a remote island, and fast.

With minimal supplies available to them, the survivors come up with the following protocol:

  • Each survivor is given a blank piece of paper, and everyone stands in a circle.
  • You begin by writing down a random number R that is clearly much larger than everyone’s combined weight, and add your weight to R. You tear off the portion of paper with only the sum, passing it to the survivor on your left.
  • Each survivor adds their weight Wi to the number they receive and passes only the result of adding their weight to the number to the next survivor.
  • When you receive the final number from the survivor on your right, you subtract the random number R you chose originally to recover the combined weight WTOT of all of the survivors.

Thankfully for the survivors, WTOT < WMAX and everyone was able to escape the island! While this simple protocol solved the survivors’ problem, it unfortunately does not provide a general solution to this class of problems. Find out how to solve the problem of evaluating a function without revealing its inputs in Part 2 of our #garbledcircuits blog series!

Anonymous