Suppose you have a black box with some buttons and some lights. When you push the buttons, the lights go on and off. You wonder what's inside, but you cannot open the box. The only way to figure out what's inside is by pushing buttons and observing the lights.
Now suppose you have two black boxes. You wonder if they are the same on the inside. Again, you cannot open the boxes, so you cannot decide by inspection. You are reduced to pushing buttons, observing lights and comparing. If a sequence of button pushes usually causes a light on one box to turn on, while the corresponding light on the other box usually stays off, you know the insides are different (probably).
Note that if you have two exactly identical black boxes and push the buttons in exactly the same way on both boxes, their lights may still behave differently. That's because inside the box, there is a source of randomness, and each box may produce different randomness.
Now suppose the insides of the black boxes really are different, but if you press the buttons in the same way, the lights always seem to go on and off in the same fashion. For you, the black boxes are effectively identical, because you now have no way of distinguishing one box from another.
If you push different buttons on the two black boxes, they will probably respond in different ways. But that doesn't allow you to distinguish them.
That was easy. The tricky part is the interpretation.
Protocol input and adversarial tampering correspond to button pushing. Flashing lights correspond to protocol output and whatever the adversary can observe during protocol runs.
On the inside of the first black box, we have the real protocol's honest users and whatever infrastructure they use.
In the second box, we have two things. One thing (often called the ideal functionality) gathers up the honest users' inputs and computes the outputs in the required way. The second thing (the simulator) gets certain information about the inputs and outputs (the specified allowed leakage) from the first thing. It simulates observations for the adversary to enjoy.
Now we observe two things about the second box:
- It will always do the computation correctly.
- The adversarial observations are computed using only the allowed leakage, so nothing more than the allowed leakage will leak.
If the first box cannot be distinguished from the second box, it follows logically that this must also apply to the first box. Which means that we have established that our protocol is secure.
