Privacy via Pseudorandom Sketches

Summary: Per-user pseudorandom sketches yield information-theoretic privacy against unbounded adversaries with arbitrary priors. Tiny O(log log M)-bit sketches aggregate to estimate conjunction frequencies (including negations) with error independent of attribute count and depending only on user count; they compose for complex queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h11a42af7b99dd550
Venue: PODS
Year: 2006
Pagerank: 7.8121754e-05
Overall Rank: 2,945 | 80.27%
DOI: 10.1145/1142351.1142373

Incoming Non-self Citations Over Time

Authors

1. Nina Mishra (University of Virginia)
2. Mark Sandler (Cornell University)

BibTeX Citation

@inproceedings{mishra_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Privacy via Pseudorandom Sketches}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142373},
        doi = {10.1145/1142351.1142373},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Mishra, Nina and Sandler, Mark},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,726	Heavy Hitters and the Structure of Local Privacy	2018	PODS	9.7702364e-05
1,792	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB	9.6159131e-05
2,595	Privacy at Scale: Local Differential Privacy in Practice	2018	SIGMOD	8.2260539e-05
3,370	Towards Robustness in Query Auditing	2006	VLDB	7.3503641e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
123	Revealing Information while Preserving Privacy	2003	PODS	0.00030654879
227	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS	0.00023895095
525	Practical Privacy: The SuLQ Framework	2005	PODS	0.00016875512
1,101	Privacy Preserving OLAP	2005	SIGMOD	0.00011995659
2,457	Simulatable Auditing	2005	PODS	8.4172033e-05
7,228	Vision Paper: Enabling Privacy for the Paranoids	2004	VLDB	5.5637938e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,626	Privacy Amplification by Sampling under User-level Differential Privacy	2024	SIGMOD
2	4,441	Towards an Axiomatization of Statistical Privacy and Utility	2010	PODS
3	10,578	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
4	11,160	Private Synthetic Data Generation in Bounded Memory	2025	PODS
5	4,819	Optimal Random Perturbation at Multiple Privacy Levels	2009	VLDB
6	3,089	Plausible Deniability for Privacy-Preserving Data Synthesis	2017	VLDB
7	3,064	Pan-private Algorithms Via Statistics on Sketches	2011	PODS
8	227	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS
9	11,567	An LDP Compatible Sketch for Securely Approximating Set Intersection Cardinalities	2024	SIGMOD
10	123	Revealing Information while Preserving Privacy	2003	PODS