Profile Reconstruction from Private Sketches

Given a multiset of n items from D, the profile reconstruction problem is to estimate, for t = 0, 1, . . . , n, the fraction f [t] of items in D that appear exactly t times. We consider differentially private profile estimation in a distributed, space-constrained setting where we wish to maintain an updatable, private sketch of the multiset that allows us to compute an approximation of Using a histogram privatized using discrete Laplace noise, we show how to "reverse" the noise, using an approach of Dwork et al. (ITCS '10). We show how to speed up their LP-based technique from polynomial time to O(d + n log n), where d = |D|, and analyze the achievable error in the ℓ 1 , ℓ 2 and ℓ ∞ norms. In all cases the dependency of the error on d is O(1/ √ d) -we give an informationtheoretic lower bound showing that this dependence on d is asymptotically optimal among all private, updatable sketches for the profile reconstruction problem with a high-probability error guarantee. Profile Reconstruction from Private Sketches 3. Preliminaries Definition 3.1 (Circulant Matrix). Let p ∈ N + and c = c 0 , c 1 , • • • , c p-1 ∈ C p be a row vector. Define the (right) circular shift operator σ : C p → C p by σ( c) = c p-1 , c 0 , • • • , c p-2 . The circulant matrix circ circ circ( c) is a matrix whose rows c, σ( c), . . . , σ p-1 ( c) are generated by iteratively applying the operator σ on c.