In general, the role of the simulator in simulation-based proofs is to show that the real protocol behaves like some idealized one. Actually, simulation goes back to the original definition of semantic security for encryption and is also the way zero knowledge is defined. In these settings, the aim of the simulator is to show that nothing is revealed (in encryption, nothing beyond the length of the plaintext; in zero knowledge, nothing beyond the validity of the claim). For concreteness, consider zero knowledge for a moment. In this setting, we construct a simulator who outputs a view of the verifier that is indistinguishable from its view in a real proof execution. Now, if the verifier can learn something from the proof itself, then we can run it also on the view generated by the simulator (or it itself can run the simulator on itself) and it will learn the same thing (up to computational indistinguishability). However, the simulator does not know the witness and it only knows the public statement being proved. Thus, this proves that the only thing that the verifier can learn is what can be learned from the public statement and a single bit that the statement is in the language.
When we consider the more general setting of secure computation, the adversary is allowed to learn the inputs and outputs of all corrupted parties. Thus, the role of the simulator here is to simulate the view of all corrupted parties, given their inputs and outputs. The problem that arises first is that the corrupted parties may change their inputs and so this is not something which is well defined. Thus, we consider an IDEAL MODEL with a trusted third party who receives the parties inputs and provides their outputs. The simulator works in this ideal model, and the requirement is that the output distribution of the honest parties and the simulator in an ideal execution is computationally indistinguishable from the output of the honest parties and adversary in a real execution. Once again, this shows that anything that a real adversary can do, can also be achieved in the ideal model. However, trivially, the only thing the simulator can do in the ideal model is to chose the corrupted parties' inputs. Observe that the simulator (who we also call an ideal-model adversary) actually has two types of interaction:
- The simulator externally interacts with the trusted party, sending it the corrupted parties' inputs and receiving back their outputs. This is real interaction with an external party.
- The simulator internally interacts with the real adversary and generates a view that is indistinguishable from its view in a real execution. This is not required by definition per se, but is really the only way to work. Note also that this is not real interaction, but the simulator runs the real adversary internally. It is necessary to do this in order to make sure that the output distribution is like in a real execution. Thus, the inputs used by the corrupted parties are effectively extracted by the simulator, and other events (like if a corrupted party aborts) are also detected. In the standard definition of secure computation, the simulator runs the adversary internally and so it can rewind it and do other tricks. The input extraction is necessary since the simulator needs to send the corrupted parties' inputs to the ideal trusted party (as in the previous item). Thus, it needs to be able to extract the effective input used by the real adversary. This shows that protocols that are secure under this definition have the property that all inputs are fully defined!
When it comes to universal composability, things become more complex since there is another entity called the environment. This is an external entity and the real and ideal adversaries interact with it (as real external interaction). The aim of the environment is to try to distinguish if it is interacting with a real adversary running a real protocol with honest parties, or if it is interacting with an ideal adversary/simulator and a trusted party computing the ideal functionality. In this case, we have the following interaction:
- The ideal adversary interacts with the environment and hands it messages that it expects to see from the real adversary; this is real external interaction. In general, if the simulator generates a view for the real adversary that is indistinguishable, then whatever the internally simulated real adversary wants to send to the environment is just forwarded by the simulator to the environment (and whatever is sent back is forwarded to the internally simulated real adversary).
- External interaction with the trusted party, as above
- Internal interaction with the real adversary, as above. Note that a real adversary can forward every message it receives immediately to the environment and can get back some response (and in fact, it could be the environment who decides on all actions by the real adversary). This actually prevents the simulator from rewinding the real adversary since essentially it is the external environment who runs the adversary, and this is external interaction with the simulator and so cannot be rewound.
I know that this is all very complicated, but with some considerable effort, it makes sense in the end...
