For simulation-based security proof in searchable encryption, there are two experiments running for the Real and the Ideal world respectively.

I can understand that the Real world experiment taking the real ciphertext and auxiliary information as the input, while the Ideal world experiment only taking the auxiliary information as the input.

However, it is a little bit difficult to understand the meaning of the output of these two experiments.

Normally, both Real and Ideal world experiment will output a bit. What't the meaning of this bit?

  • $\begingroup$ Could you provide a reference to the concrete security definition that you talk about? $\endgroup$
    – Cryptonaut
    Mar 18 '19 at 23:39

The question is rather abstract, so the answer will be rather abstract too. In general in simulation-based proofs you compare two worlds (ideal and real). Consider some protocol $\pi$ between two or more parties.

In the real world, the adversary corrupts some fraction of the parties and executes $\pi$ with the remaining honest parties that have some secret information. The honest parties follow the protocol description, whereas the corrupted parties may behave arbitrarily.

In the ideal world, the corrupted parties interact with a simulator that does not have the secret information of the honest parties, but still tries to somehow simulate the messages that the corrupted parties expect. To successfully accomplish this task, the simulator is usually given some sort of auxiliary information.

Now imagine that at the end of any interaction the adversary outputs a bit, which is its guess of whether it was in the real world or in the ideal world. If the adversary cannot do much better than guessing in which world it was, then it will output bit $b$ with roughly the same probability in both worlds. This in turn means that it cannot tell the difference between talking to real parties holding some secret information and a simulator that does not know the secret information, which in turn means that "nothing" about the secret information was leaked from the protocol execution in which the adversary participated. Usually "nothing" is a bit much to ask for and thus we at least hope that the adversary learns nothing beyond what we gave the simulator as auxiliary information.

You can find a great introduction to simulation-based proofs here. The concrete formulation, where the adversary outputs a single bit, which represents its guess regarding which world it was in, is common to security definitions in the Universal Composability model


Not the answer you're looking for? Browse other questions tagged or ask your own question.