SoK: Computational and Distributed Differential Privacy for MPC
Authors: Fredrik Meisingseth (Graz University of Technology), Christian Rechberger (Graz University of Technology)
Volume: 2025
Issue: 1
Pages: 420–439
DOI: https://doi.org/10.56553/popets-2025-0023
Abstract: In the last fifteen years, there has been a steady stream of works combining differential privacy with various other cryptographic disciplines, particularly that of multi-party computation, yielding both practical and theoretical unification. As a part of that unification, due to the rich definitional nature of both fields, there have been many proposed definitions of differential privacy adapted to the given use cases and cryptographic tools at hand, resulting in computational and/or distributed versions of differential privacy. In this work, we offer a systemisation of such definitions, with a focus on definitions that are both computational and tailored for a multi-party setting. We order the definitions according to the distribution model and computational perspective and propose a viewpoint on when given definitions should be seen as instantiations of the same generalised notion. The ordering highlights a clear, and sometimes strict, hierarchy between the definitions, where utility (accuracy) can be traded for stronger privacy guarantees or lesser trust assumptions. Further, we survey theoretical results relating the definitions and extend some of them. We also discuss the state of well-known open questions and suggest new open problems to study. Finally, we consider aspects of the practical use of the different notions, hopefully giving guidance also to future applied work.
Keywords: Differential Privacy, Multi-party Computation, Systematization of Knowledge
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
