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.
翻译:不同的私人噪声机制通常使用对称噪音分布法。 这对于实现差异隐私定义和对节点答案的公正期望都是有吸引力的。 但是,在有些情况下,如果答案是保守的, 即有已知的签名错误, 也就是我们称之为附加的错误, 杂音回答才有用。 似乎用单向错误来满足DP定义是自相矛盾的, 但我们展示了将悖论埋入DP的近似 delta 参数的可能性。 我们为单向倾斜机制开发了几个机制,这些机制总是提供保守的答案,但仍能达到近似差异的隐私。 我们展示了这些机制如何在少数选定的领域应用, 包括将设定的交叉点和私自设区间协议中披露的联盟的基点区分私人和多党计算协议, 以其精确大小使差异成为私人差异而非完全模糊的更昂贵计算方法的稀少数据进行计算。