# Conditional Equivalence of Random Systems and Indistinguishability Proofs

## Ueli Maurer

```
```A random system is the mathematical object capturing the
notion of a (probabilistic) interactive system that replies
to every input Xi(i = 1, 2, . . .) with an output Yi . A
distinguisher D for two systems S and T can adaptively
generate inputs, receives the corresponding outputs, and
after some number q of inputs guesses which system it is
talking to, S or T. Two systems are indistinguishable if for
all distinguishers (in a certain class) the distinguishing
advantage is very small.

Indistinguishability proofs are of great importance because
many security proofs in cryptography amount to the proof
that two appropriately defined systems (sometimes called a
real and an ideal system) are indistinguishable. In this
paper we provide a general technique for proving the
indistinguishability of two systems making use of the
concept of conditional equivalence of systems.