Privacy via pseudorandom sketches

By Nina Mishra, Mark Sandler. 2006

88 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Privacy & Security

Citations in the corpus

Private Aggregation from Fewer Anonymous Messages (2019, methodology): “We refer to [20,26,27] for examples and further discussion.”
Local, Private, Efficient Protocols for Succinct Histograms (2015, methodology): “Our first protocol efficiently recovers a heavy hitter from the input, given a promise (2)Mishra and Sandler [21] state error bounds for a single query to the frequency oracle, assuming the query is determined before the protocol is executed.”
RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response (2014, neutral): “The work most similar to ours is by Mishra and San-dler [24].”
Heavy Hitters and the Structure of Local Privacy (2017, background): “The heavy hitters problem is perhaps the most well-studied problem in local differential privacy [2, 3, 14, 18, 21].”
Privacy via the Johnson-Lindenstrauss Transform (2012, background): “The proof [26,32] follows by considering two candidate vectors x and x ′ that diﬀer in only one bit position, and showing that the ratio of the probability that ˆ x is published given x to the probability that ˆ x is published given x ′ is at most 1 − .”
Is Interaction Necessary for Distributed Private Learning? (2017, background): “Two of the most widely studied problems in local differential privacy are the problem of finding heavy hitters [6, 19, 23, 32] and private local learning [26].”
Lossless Compression of Efficient Private Local Randomizers (2021, methodology): “A special case of this approach is implicit in the work of Mishra & Sandler (2006) (albeit with a weaker analysis).”
Locally Differentially Private Heavy Hitter Identification (2017, background): “[26] also provide efficient protocols for heavy hitters, but the error bound is proved higher than MCM, proposed by Bassily and Smith [6].”
Privacy at Scale: Local Differential Privacy in Practice (2018, background): “[18] provide efficient protocols for heavy hitters, but the error bound”
Locally Differentially Private Protocols for Frequency Estimation (2017, methodology): “These protocols use ideas from earlier work [20, 9].”
Locally Differentially Private Frequent Itemset Mining (2018, methodology): “The problem of finding heavy hitters in a very large domain was exhaustively investigated [21], [27], [20], [5], [33], [6], [37], [10].”
Private coresets (2009, background): “2 Related Work Several papers give non-interactive differentially private sanitizations [20, 38, 5, 8].”
When Random Sampling Preserves Privacy (2006, methodology): “An input perturbation technique based on pseudorandom sketches was given in [10].”
Pan-Private Streaming Algorithms (2010, methodology): “Finally, we place pan-private streaming algorithms in context, separating them from randomized response [20] and private sketching [17].”
Bounds on the sample complexity for private learning and private data release (2010, methodology): “We use a simple compression using pseudorandom functions (akin to Mishra and Sandler (2006)) to make the algorithm efficient.”