Connecting Robust Shuffle Privacy and Pan-Privacy
Victor Balcer Harvard University, Supported by NSF grant CNS-1565387 Albert Cheu Northeastern University, Supported by NSF grants CCF-1718088, CCF- 1750640, and CNS-1816028. Matthew Joseph Google New York, Part of this work done while a graduate student at the University of Pennsylvania Jieming Mao Google New York,
Abstract
In the shuffle model of differential privacy, data-holding users send randomized messages to a secure shuffler, the shuffler permutes the messages, and the resulting collection of messages must be differentially private with regard to user data. In the pan-private model, an algorithm processes a stream of data while maintaining an internal state that is differentially private with regard to the stream data. We give evidence connecting these two apparently different models.
中文速览
差分隐私（differential privacy）领域存在两种看似无关的隐私模型——"洗牌隐私"（shuffle privacy，用户把随机化消息发给一个安全的混洗器，混洗后的结果需满足隐私要求）和"泛隐私"（pan-privacy，算法在流式处理数据时，其内部状态也必须满足隐私要求）——本文致力于揭示二者之间的深层联系。作者聚焦于"鲁棒洗牌隐私"协议（即即便存在少量恶意用户，隐私保证也不会崩溃），针对"计数不同元素"和"均匀性检验"两个经典问题，同时给出了上界协议与下界证明：前者的加性误差在两个模型中均为 Θ(√k)，后者的样本复杂度依赖则为 Õ(k^{2/3})，且纯鲁棒洗牌隐私下 Ω(k^{2/3}) 的下界也得以确立。关键创新在于作者直接将泛隐私的下界技术"移植"到洗牌隐私的下界证明中，并反向将近期洗牌隐私的直方图算法改造为泛隐私版本，从而在两个方向上都证明了这一连接的实用价值，也为理解分布式隐私计算的本质极限提供了新视角。
原文 arXiv:2004.09481;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2004.09481v4