Paper 2025/817

Relating Definitions of Computational Differential Privacy in Wider Parameter Regimes

Fredrik Meisingseth, Graz University of Technology
Christian Rechberger, Graz University of Technology
Abstract

The literature on computational differential privacy (CDP) has focused almost exclusively on definitions that are computational analogs of `pure' -DP. We initiate the formal study of computational versions of approximate DP, i.e. -DP with non-negligible . We focus on IND-CDP and SIM-CDP and show that the hierarchy between them when potentially differs substantially from when . In one direction, we show that for , any mechanism which is -SIM-CDP also is -IND-CDP, but only if is logarithmic in the security parameter. As a special case, this proves that the existing implication from -SIM-CDP to -IND-CDP does not hold for arbitrary , as previously claimed. Furthermore, we prove that when the parameters are the same in IND-CDP and SIM-CDP and is superlogarithmic, there exists a natural task that can be solved whilst satisfying SIM-CDP but which no IND-CDP mechanism can solve. This is the first separation in the CDP literature which is not due to using a task contrived specifically in order to give rise to the separation. In the other direction, we show that the techniques for establishing an implication from -IND-CDP to -SIM-CDP extend only to that a mechanism being -IND-CDP implies it is also -SIM-CDP with . Finally, we show that the Groce-Katz-Yerukhimovich barrier results against separations between CDP and statistical DP hold also in the setting of non-negligible .

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Computational Differential Privacy
Contact author(s)
fredrik meisingseth @ tugraz at
christian rechberger @ tugraz at
History
2025-05-09: approved
2025-05-08: received
See all versions
Short URL
https://ia.cr/2025/817
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/817,
      author = {Fredrik Meisingseth and Christian Rechberger},
      title = {Relating Definitions of Computational Differential Privacy in Wider Parameter Regimes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/817},
      year = {2025},
      url = {https://eprint.iacr.org/2025/817}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.