Paper 2026/2881
RRHL: A Relational Logic for Rényi Differential Privacy of Private Learning
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
-
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}
}