The Privacy-preserving Padding Problem: Non-negative Mechanisms for Conservative Answers with Differential Privacy
This work addresses the need for privacy-preserving mechanisms that ensure conservative answers in specific domains like secure computation, though it is incremental as it builds on existing approximate DP frameworks.
The paper tackles the problem of generating conservative (one-sided error) noisy answers under differential privacy, which is paradoxical due to DP's symmetry requirement, by embedding the paradox into the delta parameter of approximate DP. It develops mechanisms for one-sided padding and demonstrates applications in Private Set Intersection and multiparty computation, showing how to make set cardinalities and sizes differentially private.
Differentially private noise mechanisms commonly use symmetric noise distributions. This is attractive both for achieving the differential privacy definition, and for unbiased expectations in the noised answers. However, there are contexts in which a noisy answer only has utility if it is conservative, that is, has known-signed error, which we call a padded answer. Seemingly, it is paradoxical to satisfy the DP definition with one-sided error, but we show how it is possible to bury the paradox into approximate DP's delta parameter. We develop a few mechanisms for one-sided padding mechanisms that always give conservative answers, but still achieve approximate differential privacy. We show how these mechanisms can be applied in a few select areas including making the cardinalities of set intersections and unions revealed in Private Set Intersection protocols differential private and enabling multiparty computation protocols to compute on sparse data which has its exact sizes made differential private rather than performing a fully oblivious more expensive computation.