EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Quantitative Probabilistic Relational Hoare Logic

Martin Avanzini, Gilles Barthe, Davide Davoli, Benjamin Grégoire

Proceedings of the ACM on Programming Languages · 07.01.2025 · 9 (POPL) · 1167-1195

DOI: 10.1145/3704876 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 09.01.2025. Verfasst von Martin Avanzini und 3 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 54 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: ANR.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We introduce eRHL , a program logic for reasoning about relational expectation properties of pairs of probabilistic programs. eRHL is quantitative, i.e., its pre- and post-conditions take values in the extended non-negative reals. Thanks to its quantitative assertions, eRHL overcomes randomness alignment restrictions from prior logics, including pRHL , a popular relational program logic used to reason about security of cryptographic constructions, and apRHL , a variant of pRHL for differential privacy. As a result, eRHL is the first relational probabilistic program logic to be supported by non-trivial soundness and completeness results for all almost surely terminating programs. We show that eRHL is sound and complete with respect to program equivalence, statistical distance, and differential privacy. We also show that every pRHL judgment is valid iff it is provable in eRHL . We showcase the practical benefits of eRHL with examples that are beyond reach of pRHL and apRHL .

Förderung

  • ANR

Zitieren

APA

Avanzini, M., Barthe, G., Davoli, D., & Grégoire, B. (2025). A Quantitative Probabilistic Relational Hoare Logic. Proceedings of the ACM on Programming Languages, 9(POPL), 1167-1195. https://doi.org/10.1145/3704876

Vancouver

Avanzini M, Barthe G, Davoli D, Grégoire B. A Quantitative Probabilistic Relational Hoare Logic. Proceedings of the ACM on Programming Languages. 2025;9(POPL):1167-1195. doi:10.1145/3704876

BibTeX
@article{Avanzini2025,
  author = {Avanzini, Martin and Barthe, Gilles and Davoli, Davide and Grégoire, Benjamin},
  title = {A Quantitative Probabilistic Relational Hoare Logic},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2025},
  volume = {9},
  number = {POPL},
  pages = {1167--1195},
  doi = {10.1145/3704876}
}
Kostenlos starten →