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.
BibTeX Citation
@inproceedings{Maurer13b,
author = {Ueli Maurer},
title = {Conditional Equivalence of Random Systems and Indistinguishability Proofs},
booktitle = {2013 IEEE International Symposium on Information Theory Proceedings (ISIT)},
pages = {3150--3154},
year = {2013},
month = {7},
}