洗牌模型的循环复杂度
本文研究了本地差分隐私模型下敏感统计信息的收集,提出了一种算法,其隐私成本与用户值的更改数量的对数成正比。通过匿名化用户报告,基于用户报告的匿名性,我们还展示了当以中心式差分隐私模型来看待时,我们的LDP算法的隐私成本实际上会更低。通过新的隐私放大技术,我们证明了任何置换不变的算法,满足ε局部差分隐私的同时,也会满足(O(ε sqrt{log(1/δ)/n)},δ)中心差分隐私。作为实际的推论,我们的研究结果表明,几个基于LDP的工业部署的隐私成本会比它们宣传的ε值所表示的要低得多,至少是在报告经过匿名化的情况下。
Nov, 2018
该论文提出了一个在混淆模型下更高效的隐私安全的聚合协议,可以使得通信量和误差只呈对数级增长,并且采用了一个称为 '隐身斗篷'的新技术来实现此目的,该技术可以使得每个数据项与噪声几乎不可区分,同时对总和不会造成任何扭曲。
Jun, 2019
该论文研究了中心差分隐私算法、本地差分隐私算法和中间模型的全局隐私算法,分析了其对单次和多次干扰的影响,并通过分析样本复杂度,提供了纯全局隐私均匀性测试的近似最优算法。
Nov, 2019
介绍了 shuffle model 和 pan-private model,重点讨论了 robustly shuffle private protocols,并给出了计数和均匀性测试的隐私保证及下界。
Apr, 2020
该研究旨在探讨在差分隐私的情况下,通过使用moment-matching 方法,得出准确估计用户数量的各种协议,并提供了新型的支配协议,解决了多信息洗牌协议的开放性问题。我们的研究首次提供了全局敏感性与局部差分隐私中误差之间的第一个ω(√n) 分离,并提供了一个简单的构造,用于回答关于两方差分隐私的开放性问题。
Sep, 2020
随机洗牌可显著提高局部随机化数据的差分隐私保证,我们提出了一种基于新方法的差分隐私算法,其具有渐近最优的依赖性,应用于洗牌模型中的频率估计,是简单且近乎最优的算法。
Dec, 2020
我们研究了隐私洗牌模型下的私有向量均值估计问题,提出了一种新的多消息协议,每个用户使用Ο(nε²,d)个消息实现最优误差。此外,我们证明了实现最优误差的任何(无偏)协议都需要每个用户发送Ω(nε²/dlog(n))个消息,从而证明了我们的消息复杂度在对数因子上的最优性。此外,我们还研究了单消息设置,并设计了一个协议,实现均方误差Ο(dn^(d/(d+2))/ε^(4/(d+2)))。此外,我们证明了任何单消息协议必须产生均方误差Ω(dn^(d/(d+2))),从而证明了我们的协议在ε=Θ(1)的标准设置下是最优的。最后,我们研究了对恶意用户的鲁棒性,并显示恶意用户可以以单个洗牌者产生大的附加误差。
Apr, 2024
这项工作探讨了用于非统计计算的混洗隐私扩大的可行性,提出了一种新的混洗模型范例,并引入了统计上的随机标识,从而在保持隐私扩大同时实现关键的安全功能。实验结果表明,这种模型和机制在减少错误率、提高效用性能方面相对于非隐私设置快速并且实用。
Jun, 2024