Contributions to the Theory of Probabilistic Discrete Systems
David Lanzenberger
A probabilistic discrete system (PDS) is an abstract object operating in rounds. In every round, an environment (which is a complex object like a PDS) can input a value and the system responds with an output value. A PDS may be probabilistic and each round may depend on the previous rounds. Many cryptographic systems (which can be modeled as probabilistic discrete systems) have security definitions based on an environment interacting with the system, essentially modeling the adversary. For example, a system is defined to be secure if it is indistinguishable from a certain ideal system for any environment, leading to the notion of a distinguisher.
Recently, Maurer proposed a novel paradigm called environment-less, in which properties of systems are expressed as intrinsic properties of the systems as objects themselves, free of the notion of an environment or an adversary. The paradigm gives new insight into the very essence of the properties and enables more minimal and abstract reasoning about systems.
This work makes the first steps towards an environment-less (cryptographic) systems theory. We show that two key properties of cryptographic systems, namely the indistinguishability of two systems and the optimal winning probability of a game, can be stated equivalently and naturally within the environment-less paradigm. Our treatment is abstract: we merely assume that an object of a set A is observable by one function (or projection) of a set F. As a consequence, our results are applicable to a broad class of system types and beyond.
Furthermore, we present a new variant of Maurers theory of discrete systems. In contrast to Maurers representation, we define discrete systems as inductive objects. We show how this new representation allows to prove elementary statements about systems in a rigorous and formalizable manner.
Finally, we use environment-less indistinguishability to prove a new indistinguishability amplification theorem in an elementary fashion, generalizing previous results. This demonstrates that the environment-less paradigm is not only of conceptual interest but a powerful technical tool as well.
BibTeX Citation
@mastersthesis{Lanzen19,
author = {David Lanzenberger},
title = {Contributions to the Theory of Probabilistic Discrete Systems},
year = 2019,
month = 8,
address = {Institute for Theoretical Computer Science},
school = {ETH Zurich},
}