Information Security and Cryptography Research Group

Computational Indistinguishability Amplification: Tight Product Theorems for System Composition

Ueli Maurer and Stefano Tessaro

Advances in Cryptology — CRYPTO 2009, Lecture Notes in Computer Science, Springer-Verlag, vol. 5677, pp. 350–368, Aug 2009.

Computational indistinguishability amplification is the problem of strengthening cryptographic primitives whose security is defined by bounding the distinguishing advantage of an efficient distinguisher. Examples include pseudorandom generators (PRGs), pseudorandom functions (PRFs), and pseudorandom permutations (PRPs).

The literature on computational indistinguishability amplification consists only of few isolated results. Yao's XOR-lemma implies, by a hybrid argument, that no efficient distinguisher has advantage better than (roughly) n2m1δm in distinguishing the XOR of m independent n-bit PRG outputs S1,,Sm from uniform randomness if no efficient distinguisher has advantage more than δ in distinguishing Si from a uniform n-bit string. The factor 2m1 allows for security amplification only if δ<12: For the case of PRFs, a random-offset XOR-construction of Myers was the first result to achieve strong security amplification, i.e., also for 12δ<1.

This paper proposes a systematic treatment of computational indistinguishability amplification. We generalize and improve the above product theorem for the XOR of PRGs along five axes. First, we prove the tight information-theoretic bound 2m1δm (without factor n) also for the computational setting. Second, we prove results for interactive systems (e.g. PRFs or PRPs). Third, we consider the general class of neutralizing combination constructions, not just XOR. As an application this yields the first indistinguishability amplification results for the cascade of PRPs (i.e., block ciphers) converting a weak PRP into an arbitrarily strong PRP, both for single-sided and two-sided queries. Fourth, strong security amplification is achieved for a subclass of neutralizing constructions which includes as a special case the construction of Myers. As an application we obtain highly practical optimal security amplification for block ciphers, simply by adding random offsets at the input and output of the cascade. Fifth, we show strong security amplification also for weakened assumptions like security against random-input (as opposed to chosen-input) attacks.

A key technique is a generalization of Yao's XOR-lemma to (interactive) systems, which is of independent interest.

BibTeX Citation

@inproceedings{MauTes09,
    author       = {Ueli Maurer and Stefano Tessaro},
    title        = {Computational Indistinguishability Amplification: Tight Product Theorems for System Composition},
    editor       = {Shai Halevi},
    booktitle    = {Advances in Cryptology --- CRYPTO 2009},
    pages        = {350--368},
    series       = {Lecture Notes in Computer Science},
    volume       = {5677},
    year         = {2009},
    month        = {8},
    publisher    = {Springer-Verlag},
}

Files and Links