Paper 2025/817

Relating Definitions of Computational Differential Privacy in Wider Parameter Regimes

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 $$.