Computational Indistinguishability Amplification: Tight Product Theorems for System Composition
Ueli Maurer and Stefano Tessaro
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)
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
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}, }