Universal equivalence and majority on probabilistic programs over finite fields
Gilles Barthe, Charlie Jacomme, and Steve Kremer. Universal equivalence and majority on probabilistic programs over finite fields. ACM Transactions on Computational Logic, 23(1):1–42, January 2022.
doi:10.1145/3487063
Download
Abstract
We study decidability problems for equivalence of probabilistic programs, for a core probabilistic programming language over finite fields of fixed characteristic. The programming language supports uniform sampling, addition, multiplication and conditionals and thus is sufficiently expressive to encode boolean and arithmetic circuits. We consider two variants of equivalence: the first one considers an interpretation over the finite field $\Fq$, while the second one, which we call universal equivalence, verifies equivalence over all extensions $\Fqk$ of $\Fq$. The universal variant typically arises in provable cryptography when one wishes to prove equivalence for any length of bitstrings, i.e., elements of $\F_2^k$ for any $k$. While the first problem is obviously decidable, we establish its exact complexity which lies in the counting hierarchy. To show decidability, and a doubly exponential upper bound, of the universal variant we rely on results from algorithmic number theory and the possibility to compare local zeta functions associated to given polynomials. We then devise a general way to draw links between the universal probabilistic problems and widely studied problems on linear recurrence sequences. Finally we study several variants of the equivalence problem, including a problem we call majority, motivated by differential privacy. We also define and provide some insights about program indistinguishability, proving that it is decidable for programs always returning 0 or 1.
BibTeX
@Article{BJK-tocl22,
author = {Barthe, Gilles and Jacomme, Charlie and Kremer,
Steve},
abstract = { We study decidability problems for equivalence of
probabilistic programs, for a core probabilistic
programming language over finite fields of fixed
characteristic. The programming language supports
uniform sampling, addition, multiplication and
conditionals and thus is sufficiently expressive to
encode boolean and arithmetic circuits. We consider
two variants of equivalence: the first one considers
an interpretation over the finite field $\Fq$, while
the second one, which we call universal equivalence,
verifies equivalence over all extensions $\Fqk$ of
$\Fq$. The universal variant typically arises in
provable cryptography when one wishes to prove
equivalence for any length of bitstrings, i.e.,
elements of $\F_{2^k}$ for any $k$. While the first
problem is obviously decidable, we establish its
exact complexity which lies in the counting
hierarchy. To show decidability, and a doubly
exponential upper bound, of the universal variant we
rely on results from algorithmic number theory and
the possibility to compare local zeta functions
associated to given polynomials. We then devise a
general way to draw links between the universal
probabilistic problems and widely studied problems
on linear recurrence sequences. Finally we study
several variants of the equivalence problem,
including a problem we call majority, motivated by
differential privacy. We also define and provide
some insights about program indistinguishability,
proving that it is decidable for programs always
returning 0 or 1. },
title = {Universal equivalence and majority on probabilistic
programs over finite fields},
journal = {ACM Transactions on Computational Logic},
year = 2022,
month = jan,
volume = 23,
number = 1,
articleno = 5,
pages = {1--42},
doi = {10.1145/3487063},
url = {https://dl.acm.org/doi/pdf/10.1145/3487063},
}