Cryptology ePrint Archive: Report 2020/1187
Coupling of Random Systems
David Lanzenberger and Ueli Maurer
Abstract: This paper makes three contributions. First, we present a simple theory of
random systems. The main idea is to think of a probabilistic system as an
equivalence class of distributions over deterministic systems. Second, we
demonstrate how in this new theory, the optimal
information-theoretic distinguishing advantage between two systems can be
characterized merely in terms of the statistical distance of probability
distributions, providing a more elementary understanding of the distance of
systems. In particular, two systems that are $\epsilon$-close in terms of the
best distinguishing advantage can be understood as being equal with
probability 1-$\epsilon$, a property that holds statically, without even
considering a distinguisher, let alone its interaction with the systems.
Finally, we exploit this new characterization of the distinguishing advantage
to prove that any threshold combiner is an amplifier for indistinguishability
in the information-theoretic setting, generalizing and simplifying results
from Maurer, Pietrzak, and Renner (CRYPTO 2007).
Category / Keywords: foundations / random systems, coupling, coupling lemma, information-theoretic indistinguishability, indistinguishability amplification
Original Publication (with minor differences): IACR-TCC-2020
Date: received 28 Sep 2020
Contact author: landavid at inf ethz ch
Available format(s): PDF | BibTeX Citation
Version: 20200930:074824 (All versions of this report)
Short URL: ia.cr/2020/1187
[ Cryptology ePrint archive ]