Indistinguishability amplification

U. Maurer, K.Z. Pietrzak, R. Renner, in:, Springer, 2007, pp. 130–149.

No fulltext has been uploaded. References only!

Conference Paper | Published
; ;
Series Title
Many aspects of cryptographic security proofs can be seen as the proof that a certain system (e.g. a block cipher) is indistinguishable from an ideal system (e.g. a random permutation), for different types of distinguishers. This paper presents a new generic approach to proving upper bounds on the information-theoretic distinguishing advantage (from an ideal system) for a combined system, assuming upper bounds of certain types for the component systems. For a general type of combination operation of systems, including the XOR of functions or the cascade of permutations, we prove two amplification theorems. The first is a product theorem, in the spirit of XOR-lemmas: The distinguishing advantage of the combination of two systems is at most twice the product of the individual distinguishing advantages. This bound is optimal. The second theorem states that the combination of systems is secure against some strong class of distinguishers, assuming only that the components are secure against some weaker class of distinguishers. A key technical tool of the paper is the proof of a tight two-way correspondence, previously only known to hold in one direction, between the distinguishing advantage of two systems and the probability of winning an appropriately defined game. © International Association for Cryptologic Research 2007.
Publishing Year
Date Published
130 - 149
CRYPTO: International Cryptology Conference

Cite this

Maurer U, Pietrzak KZ, Renner R. Indistinguishability amplification. In: Vol 4622. Springer; 2007:130-149. doi:10.1007/978-3-540-74143-5_8
Maurer, U., Pietrzak, K. Z., & Renner, R. (2007). Indistinguishability amplification (Vol. 4622, pp. 130–149). Presented at the CRYPTO: International Cryptology Conference, Springer.
Maurer, Ueli, Krzysztof Z Pietrzak, and Renato Renner. “Indistinguishability Amplification,” 4622:130–49. Springer, 2007.
U. Maurer, K. Z. Pietrzak, and R. Renner, “Indistinguishability amplification,” presented at the CRYPTO: International Cryptology Conference, 2007, vol. 4622, pp. 130–149.
Maurer U, Pietrzak KZ, Renner R. 2007. Indistinguishability amplification. CRYPTO: International Cryptology Conference, LNCS, vol. 4622. 130–149.
Maurer, Ueli, et al. Indistinguishability Amplification. Vol. 4622, Springer, 2007, pp. 130–49, doi:10.1007/978-3-540-74143-5_8.


Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar