Welcome to the resource topic for 2025/817
Title:
Relating Definitions of Computational Differential Privacy in Wider Parameter Regimes
Authors: Fredrik Meisingseth, Christian Rechberger
Abstract:The literature on computational differential privacy (CDP) has focused almost exclusively on definitions that are computational analogs of `pure’ (\epsilon,0)-DP. We initiate the formal study of computational versions of approximate DP, i.e. (\epsilon, \delta)-DP with non-negligible \delta. We focus on IND-CDP and SIM${\forall\exists}-CDP and show that the hierarchy between them when \delta > 0$ potentially differs substantially from when \delta = 0. In one direction, we show that for \delta < 1, any mechanism which is (\epsilon,\delta)-SIM${\forall\exists}-CDP also is (\epsilon,\delta)-IND-CDP, but only if \epsilon$ is logarithmic in the security parameter. As a special case, this proves that the existing implication from (\epsilon,0)-SIM${\forall\exists}-CDP to (\epsilon,0)-IND-CDP does not hold for arbitrary \epsilon$, as previously claimed. Furthermore, we prove that when the parameters are the same in IND-CDP and SIM${\forall\exists}-CDP and \epsilon$ is superlogarithmic, there exists a natural task that can be solved whilst satisfying SIM${\forall\exists}-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 (\epsilon,0)-IND-CDP to (\epsilon,0)-SIM{\forall\exists}-CDP extend only to that a mechanism being (\epsilon,\delta)-IND-CDP implies it is also (\epsilon,\delta’)-SIM_{\forall\exists}-CDP with \delta’ > \delta$. 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 \delta.
ePrint: https://eprint.iacr.org/2025/817
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .