From Indifferentiability to Constructive Cryptography (and Back)
Ueli Maurer and Renato Renner
The concept of indifferentiability of systems, a generalized form of indistinguishability, was proposed in 2004 to provide a simplified and generalized explanation of impossibility results like the non-instantiability of random oracles by hash functions due to Canetti, Goldreich, and Halevi (STOC 1998). But indifferentiability is actually a constructive notion, leading to possibility results. For example, Coron et al. (Crypto 2005) argued that the soundness of the construction $C(f)$ of a hash function from a compression function $f$ can be demonstrated by proving that $C(R)$ is indifferentiable from a random oracle if $R$ is an ideal random compression function.
The purpose of this short paper is to describe how the indifferentiability notion was a precursor to the theory of constructive cryptography and thereby to provide a simplified and generalized treatment of indifferentiability as a special type of constructive statement.
BibTeX Citation
@inproceedings{MauRen16,
author = {Ueli Maurer and Renato Renner},
title = {From Indifferentiability to Constructive Cryptography (and Back)},
editor = {M. Hirt and A. Smith},
booktitle = {Theory of Cryptography},
pages = {1--22},
series = {Lecture Notes in Computer Science},
volume = {9985},
year = {2016},
month = {11},
publisher = {Springer Berlin Heidelberg},
}