The Role of Interactivity in Local Differential Privacy
The Role of Interactivity in Local Differential Privacy
复制标题
DOI：
10.1109/focs.2019.00015
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Matthew Joseph;Jieming Mao;Seth Neel;Aaron Roth
中科院分区：
文献类型：
--
作者：
Matthew Joseph;Jieming Mao;Seth Neel;Aaron Roth
我们研究了局部差分隐私中交互性的力量。首先，我们将重点讨论完全交互协议和顺序交互协议之间的区别。顺序交互协议可以自适应地按顺序查询用户，但不能返回到先前查询的用户。现有的绝大多数局部差分隐私下限仅适用于顺序交互协议，在本文之前，人们并不知道完全交互协议是否更强大。我们解决了这个问题。首先，我们根据组合性对局部私有协议进行分类，组合性是指协议的单轮隐私参数之和超过其整体隐私保证的乘法因子。然后，我们展示了如何有效地将任何完全交互的组合协议转换为等效的顺序交互协议，该协议在这种组合性中具有爆炸性的样本复杂度线性。接下来，我们通过展示一系列问题来证明我们的简化是紧密的，这样任何顺序交互协议都需要比完全交互组合协议更大的样本复杂性。然后我们将注意力转向假设检验问题。我们证明了对于一大类复合假设检验问题——其中包括作为特例的所有简单假设检验问题——一个简单的非交互检验在所有（可能是完全交互的）检验中是最优的。
We study the power of interactivity in local differential privacy. First, we focus on the difference between fully interactive and sequentially interactive protocols. Sequentially interactive protocols may query users adaptively in sequence, but they cannot return to previously queried users. The vast majority of existing lower bounds for local differential privacy apply only to sequentially interactive protocols, and before this paper it was not known whether fully interactive protocols were more powerful. We resolve this question. First, we classify locally private protocols by their compositionality, the multiplicative factor by which the sum of a protocol's single-round privacy parameters exceeds its overall privacy guarantee. We then show how to efficiently transform any fully interactive compositional protocol into an equivalent sequentially interactive protocol with a blowup in sample complexity linear in this compositionality. Next, we show that our reduction is tight by exhibiting a family of problems such that any sequentially interactive protocol requires this blowup in sample complexity over a fully interactive compositional protocol. We then turn our attention to hypothesis testing problems. We show that for a large class of compound hypothesis testing problems --- which include all simple hypothesis testing problems as a special case --- a simple noninteractive test is optimal among the class of all (possibly fully interactive) tests.