From Indifferentiability to Constructive Cryptography (and Back)

Ueli Maurer and Renato Renner

Theory of Cryptography, Lecture Notes in Computer Science, Springer Berlin Heidelberg, vol. 9985, pp. 1–22, Nov 2016.

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},
}