A Theory of Composition for Differential Obliviousness
A Theory of Composition for Differential Obliviousness
复制标题
DOI：
10.1007/978-3-031-30620-4_1
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Mingxun Zhou;E. Shi;T-H. Hubert Chan;S. Maimon
中科院分区：
文献类型：
--
作者：
Mingxun Zhou;E. Shi;T-H. Hubert Chan;S. Maimon
差分遗忘（DO）是一个隐私概念，它保证程序的访问模式满足差分隐私。差别遗忘在最近的一系列作品中被研究为完全遗忘的放松。早期的工作表明，DO不仅允许我们绕过完全遗忘算法的开销障碍，在许多情况下，它还允许我们实现多项式加速完全遗忘，因为它避免了“填充到最坏情况”的行为完全遗忘algorithm.Despite差分遗忘（DO）的承诺，一个重大的障碍，阻碍其广泛应用是缺乏可组合性。特别是，当我们将一个DO算法应用于另一个DO算法的输出时，组合算法可能不再是DO（具有合理的参数）。具体来说，两个相邻的输入上的第一个DO算法的输出可能不再是相邻的，因此，我们不能直接受益于DO保证的第二algorithm.In这项工作中，我们是第一个探索的理论组成差分遗忘算法。我们提出了一个细化的DO概念称为邻居的邻居，隐藏DO，或NPDO的短，我们证明了我们的新概念确实提供了很好的成分保证。通过这种方式，算法设计者可以很容易地跟踪多个DO算法组合时的隐私损失。我们给出了几个示例应用程序来展示我们的新NPDO概念的力量和表现力。其中一个例子是独立兴趣的结果：我们使用组合框架来证明差分不经意洗牌模型的最佳隐私放大定理。换句话说，我们表明，一类分布式差分隐私机制的洗牌模型，可以取代完全安全的洗牌机与DO洗牌机，但享受几乎相同的隐私放大洗牌机启用。
Differential obliviousness (DO) is a privacy notion which guarantees that the access patterns of a program satisfies differential privacy. Differential obliviousness was studied in a sequence of recent works as a relaxation of full obliviousness. Earlier works showed that DO not only allows us to circumvent the logarithmic-overhead barrier of fully oblivious algorithms, in many cases, it also allows us to achieve polynomial speedup over full obliviousness, since it avoids “padding to the worst-case” behavior of fully oblivious algorithms.Despite the promises of differential obliviousness (DO), a significant barrier that hinders its broad application is the lack of composability. In particular, when we apply one DO algorithm to the output of another DO algorithm, the composed algorithm may no longer be DO (with reasonable parameters). Specifically, the outputs of the first DO algorithm on two neighboring inputs may no longer be neighboring, and thus we cannot directly benefit from the DO guarantee of the second algorithm.In this work, we are the first to explore a theory of composition for differentially oblivious algorithms. We propose a refinement of the DO notion called-neighbor-preserving-DO, or-NPDO for short, and we prove that our new notion indeed provides nice compositional guarantees. In this way, the algorithm designer can easily track the privacy loss when composing multiple DO algorithms.We give several example applications to showcase the power and expressiveness of our new NPDO notion. One of these examples is a result of independent interest: we use the compositional framework to prove an optimal privacy amplification theorem for the differentially oblivious shuffle model. In other words, we show that for a class of distributed differentially private mechanisms in the shuffle-model, one can replace the perfectly secure shuffler with a DO shuffler, and nonetheless enjoy almost the same privacy amplification enabled by a shuffler.