Proving uniformity and independence by self-composition and coupling
arXiv preprint arXiv:1701.06477, 2017•arxiv.org
Proof by coupling is a classical proof technique for establishing probabilistic properties of
two probabilistic processes, like stochastic dominance and rapid mixing of Markov chains.
More recently, couplings have been investigated as a useful abstraction for formal reasoning
about relational properties of probabilistic programs, in particular for modeling reduction-
based cryptographic proofs and for verifying differential privacy. In this paper, we
demonstrate that probabilistic couplings can be used for verifying non-relational probabilistic …
two probabilistic processes, like stochastic dominance and rapid mixing of Markov chains.
More recently, couplings have been investigated as a useful abstraction for formal reasoning
about relational properties of probabilistic programs, in particular for modeling reduction-
based cryptographic proofs and for verifying differential privacy. In this paper, we
demonstrate that probabilistic couplings can be used for verifying non-relational probabilistic …
Proof by coupling is a classical proof technique for establishing probabilistic properties of two probabilistic processes, like stochastic dominance and rapid mixing of Markov chains. More recently, couplings have been investigated as a useful abstraction for formal reasoning about relational properties of probabilistic programs, in particular for modeling reduction-based cryptographic proofs and for verifying differential privacy. In this paper, we demonstrate that probabilistic couplings can be used for verifying non-relational probabilistic properties. Specifically, we show that the program logic pRHL---whose proofs are formal versions of proofs by coupling---can be used for formalizing uniformity and probabilistic independence. We formally verify our main examples using the EasyCrypt proof assistant.
arxiv.org