The Flajolet-Martin Sketch Itself Preserves Differential Privacy: Private Counting with Minimal Space
The Flajolet-Martin Sketch Itself Preserves Differential Privacy: Private Counting with Minimal Space
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Adam D. Smith;Shuang Song;Abhradeep Thakurta
中科院分区：
文献类型：
--
作者：
Adam D. Smith;Shuang Song;Abhradeep Thakurta
我们重新考虑在一个域[u]上计算数据流D中不同元素f0 (D)的个数的问题。我们提出了一种(ε, δ) -差分私有算法，该算法在因子（1±γ）范围内逼近f0 (D)，并具有O (（cid:112) ln(1 /δ) /ε）的附加误差，使用空间O （ln(ln(u) /γ) /γ 2）。在空间误差和加性误差方面，我们对之前的工作进行了改进，至少是二次的，甚至是指数的。我们的加性误差保证是最优的，可达O (（cid:112) ln(1 /δ)）的因子，空间界是最优的，可达O (cid:16) min (cid:110) ln(cid:16) ln(u) γ (cid:17), 1 γ 2 (cid:111)（cid:17）的因子。我们假设存在一个理想的均匀随机哈希函数，并且忽略存储它所需的空间。稍后，我们通过假设伪随机函数并使用差分隐私的计算变体SIM-CDP来放宽这一要求。我们的算法是建立在著名的Flajolet-Martin （FM）草图之上的。我们证明，只要数据集中存在≈(cid:112) ln(1 /δ) / (εγ)不同的元素，FM-sketch就是差分私有的。在此过程中，我们证明了一个结构结果，该结果表明，只要k = Ω （cid:0） 1 ε (cid:1)， k iid个随机变量的最大值与来自同一分布的（k + 1） iid个样本的最大值在统计上接近（在ε -微分隐私意义上）。最后，实验表明我们的算法引入了误差
We revisit the problem of counting the number of distinct elements F 0 ( D ) in a data stream D , over a domain [ u ] . We propose an ( ε, δ ) -differentially private algorithm that approximates F 0 ( D ) within a factor of (1 ± γ ) , and with additive error of O ( (cid:112) ln(1 /δ ) /ε ) , using space O (ln(ln( u ) /γ ) /γ 2 ) . We improve on the prior work at least quadratically and up to exponentially, in terms of both space and additive error. Our additive error guarantee is optimal up to a factor of O ( (cid:112) ln(1 /δ )) , and the space bound is optimal up to a factor of O (cid:16) min (cid:110) ln (cid:16) ln( u ) γ (cid:17) , 1 γ 2 (cid:111)(cid:17) . We assume the existence of an ideal uniform random hash function, and ignore the space required to store it. We later relax this requirement by assuming pseudo-random functions and appealing to a computational variant of differential privacy, SIM-CDP. Our algorithm is built on top of the celebrated Flajolet-Martin (FM) sketch. We show that FM-sketch is differentially private as is, as long as there are ≈ (cid:112) ln(1 /δ ) / ( εγ ) distinct elements in the data set. Along the way, we prove a structural result showing that the maximum of k i.i.d. random variables is statistically close (in the sense of ε -differential privacy) to the maximum of ( k + 1) i.i.d. samples from the same distribution, as long as k = Ω (cid:0) 1 ε (cid:1) . Finally, experiments show that our algorithms introduces error within