Paper 2026/2881

RRHL: A Relational Logic for Rényi Differential Privacy of Private Learning

Gilles Barthe, Max Planck Institute for Security and Privacy (MPI-SP), IMDEA Software Institute
Davide Davoli, Max Planck Institute for Security and Privacy (MPI-SP)
Abstract

Differential privacy is the standard framework for defining privacy-preserving computation and is adopted in large-scale production systems, including industrial-level private learning. The underlying algorithms are based on complex privacy-enhancing mechanisms such as privacy amplification by subsampling and correlated noising. Proving their privacy requires advanced reasoning techniques such as the moments accountant and shifted composition; no existing approach to formal verification supports all of them. In this work, we introduce RRHL: a relational program logic for proving Rényi differential privacy of imperative programs with continuous sampling instructions. Its judgments express bounds on the privacy budgets of instructions as functions of the program states, and its composition of budgets is sharp. We use RRHL to prove differential privacy of the algorithms widely implemented and deployed. These include several variants of DP-SGD and DP-FTRL, and gradient descent with per-record Rényi filters. In several cases the bounds match the best known Rényi differential privacy analyses. The logic, its soundness proof and the case studies are formalized in Lean. To the best of our knowledge, this is the first formal privacy analysis, via a relational program logic, of private learning algorithms with state-of-the-art Rényi differential privacy bounds.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
relational Hoare logicRényi differential privacyDP-SGDshifted compositionformal verificationLean
Contact author(s)
gilles barthe @ mpi-sp org
davide davoli @ mpi-sp org
History
2026-11-16: approved
2026-11-12: received
See all versions
Short URL
https://ia.cr/2026/2881
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2881,
      author = {Gilles Barthe and Davide Davoli},
      title = {{RRHL}: A Relational Logic for Rényi Differential Privacy of Private Learning},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2881},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2881}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.