Cryptology ePrint Archive: Report 2006/456
Indistinguishability Amplification
Ueli Maurer and Krzysztof Pietrzak and Renato Renner
Abstract: A random system is the abstraction of the input-output behavior of
any kind of discrete system, in particular cryptographic systems. Many
aspects of cryptographic security analyses and proofs can be seen as
the proof that a certain random 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 distinguishing advantage of a combined system,
assuming upper bounds of various types on the component systems. For
a general type of combination operation of systems (including the
combination of functions or the cascade of permutations), we prove
two amplification theorems.
The first is a direct-product theorem, similar in spirit to the
XOR-Lemma: The distinguishing advantage (or security) of the
combination of two (possibly stateful) systems is twice the product
of the individual distinguishing advantages, which 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 attacks. As a corollary we obtain tight bounds on the
adaptive security of the cascade and parallel composition of
non-adaptively (or only random-query) secure component systems.
A key technical tool of the paper is
to show a tight two-way correspondence, previously only
known to hold in one direction, between the distinguishing
advantage of two systems and the probability of provoking an
appropriately defined event on one of the systems.
Category / Keywords: foundations / informatin theory, random systems, direct product
Date: received 1 Dec 2006
Contact author: pietrzak at di ens fr
Available format(s): PDF | BibTeX Citation
Version: 20061204:103357 (All versions of this report)
Short URL: ia.cr/2006/456
[ Cryptology ePrint archive ]