Skip to Main content Skip to Navigation
Conference papers

Universal equivalence and majority of probabilistic programs over finite fields

Abstract : We study decidability problems for equivalence of probabilis-tic 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 F , while the second one, which we call universal equivalence, verifies equivalence over all extensions F of F. 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 for any. 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 algo-rithmic 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.
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/hal-02961583
Contributor : Steve Kremer <>
Submitted on : Thursday, October 8, 2020 - 3:27:50 PM
Last modification on : Saturday, October 10, 2020 - 3:25:43 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

Citation

Gilles Barthe, Charlie Jacomme, Steve Kremer. Universal equivalence and majority of probabilistic programs over finite fields. ACM/IEEE LICS 2020 - 35th Annual Symposium on Logic in Computer Science, Jul 2020, Saarbrücken / Virtual, Germany. pp.155-166, ⟨10.1145/3373718.3394746⟩. ⟨hal-02961583⟩

Share

Metrics

Record views

20

Files downloads

41