Universal equivalence and majority of probabilistic programs over finite fields
Résumé
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 a fixed finite field, while the second one,
which we call universal equivalence, verifies equivalence over all
extensions of a finite field. The universal variant typically arises
in provable cryptography when one wishes to prove equivalence for
any length of bitstrings, i.e., elements of extensions of the boolean field.
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. Finally we study several variants of the equivalence
problem, including a problem we call majority, motivated by
differential privacy.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...