Maurer, Ueli M; Pietrzak, Krzysztof ZISTA ; Renner, Renato
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.
130 - 149
CRYPTO: International Cryptology Conference
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. https://doi.org/10.1007/978-3-540-74143-5_8
Maurer, Ueli, Krzysztof Z Pietrzak, and Renato Renner. “Indistinguishability Amplification,” 4622:130–49. Springer, 2007. https://doi.org/10.1007/978-3-540-74143-5_8.
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.