This idea was developed by Andrew Yao in the 1980s,
and it gives a way to perform any function as a secure computation.
The idea is that any discrete, fixed-size function can be turned into logic gates,
and then if we can find a way to implement logic gates securely,
we can implement a whole function this way.
We can think of a logic gate as the truth table. Let's take for example the function AND.
AND takes 2 inputs and produces 1 output.
And we can describe that AND with the table of values.
We'll use 0 to represent false and 1 to represent true.
This is a regular AND gate.
If we evaluate the AND gate, we need to know the actual values of A and B.
Suppose the value of A is 1 and the value of B is 0,
then we would take this line from the truth table and know that output has the value 0.
Our goal is to encrypt the circuit in such a way that we can still evaluate it
without actually knowing what the inputs are and without learning what the output is
but still producing output that we can use as the input to the next circuit.
If we can evaluate each gate this way, keeping the inputs and outputs encrypted,
we can evaluate the whole circuit.
At the end, we can map the final result to a meaningful value.
Our first step to creating an encrypted circuit is to replace the inputs with encrypted values.
That means we need some way to represent a 0 on this wire and some way to represent a 1.
Same for this wire. We're going to place this 0 and 1 in the table with encrypted values.
We'll just look at those as randomized.
We're going to pick some random value to represent 0 on this wire. Let's call that A0.
We'll pick some random value to represent 1. We'll call that A1.
And we'll do the same thing for the other wire.
And we'll do the same thing for the output.
Here's our new truth table.
Well, if we keep things in the same order, we haven't hidden anything.
Let's randomly permute it, and now suppose we got a table like this.
That means that A0 is either 0010 or 1010.
Now the question is can you determine what is the value of B0.
If you could, that would mean you know the semantic value of B.
You can tell if it's equal to B0 or not and that would mean you're evaluating the circuit
and you're learning the values in the circuit,
so you don't have the secured computation you wanted to.
Can you determine the value of the 0 knowing this garbled table?
