### 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).

Available format(s)
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2020
Keywords
random systemscouplingcoupling lemmainformation-theoretic indistinguishabilityindistinguishability amplification
Contact author(s)
landavid @ inf ethz ch
History
2021-06-14: revised
See all versions
Short URL
https://ia.cr/2020/1187

CC BY

BibTeX

@misc{cryptoeprint:2020/1187,
author = {David Lanzenberger and Ueli Maurer},
title = {Coupling of Random Systems},
howpublished = {Cryptology ePrint Archive, Paper 2020/1187},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1187}},
url = {https://eprint.iacr.org/2020/1187}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.