Longshot: Indexing Growing Databases using MPC and Differential Privacy

Summary: Longshot combines MPC and differential privacy to maintain query-accelerating indexes and synopses for growing outsourced databases. A time-ordered hierarchy exploits bounded leakage for logarithmic error and tunable privacy–accuracy–efficiency, delivering 5× faster updates and ~10³× faster queries. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13243
Venue: VLDB
Year: 2023
Pagerank: 5.9513399e-05
Overall Rank: 6,171 | 57.67%
DOI: 10.14778/3594512.3594529

Incoming Non-self Citations Over Time

Authors

1. Yanping Zhang (Duke University)
2. Johes Bater (Tufts University)
3. Kartik Nayak (Duke University)
4. Ashwin Machanavajjhala (Duke University)

BibTeX Citation

@article{zhang_vldb23,
        title = {{Longshot: Indexing Growing Databases using MPC and Differential Privacy}},
        author = {Zhang, Yanping and Bater, Johes and Nayak, Kartik and Machanavajjhala, Ashwin},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {8},
        pages = {2005--2018},
        doi = {10.14778/3594512.3594529},
        url = {https://doi.org/10.14778/3594512.3594529},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,249	Femur: A Flexible Framework for Fast and Secure Querying from Public Key-Value Store	2025	SIGMOD	5.4574671e-05
10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD	5.093636e-05
10,803	SPECIAL: SynoPsis AssistEd Secure CollaboratIve AnaLytics	2025	VLDB	5.093636e-05
10,914	Calibrating Noise for Group Privacy in Subsampled Mechanisms	2025	VLDB	5.093636e-05
10,992	PrivAGM: Secure Construction of Differentially Private Directed Attributed Graph Models on Decentralized Social Graphs	2025	VLDB	5.093636e-05
11,242	SWAT: A System-Wide Approach to Tunable Leakage Mitigation in Encrypted Data Stores	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
121	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00031639377
123	Revealing Information while Preserving Privacy	2003	PODS	0.00031082693
310	Order Preserving Encryption for Numeric Data	2004	SIGMOD	0.00021766789
567	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00016420715
1,144	PrivateSQL: A Differentially Private SQL Query Engine	2019	VLDB	0.00011999046
1,459	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.00010717725
1,674	The Tao of Inference in Privacy-Protected Databases	2018	VLDB	0.00010037562
1,984	Shrinkwrap: Efficient SQL Query Processing in Differentially Private Data Federations	2019	VLDB	9.3540912e-05
2,074	Differentially Private Event Sequences over Infinite Streams	2014	VLDB	9.2192882e-05
2,167	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	9.047803e-05
2,818	CryptEpsilon: Crypto-Assisted Differential Privacy on Untrusted Servers	2020	SIGMOD	8.0932359e-05
4,930	IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential Privacy	2022	SIGMOD	6.4402718e-05
8,311	DP-Sync: Hiding Update Patterns in Secure Outsourced Databases with Differential Privacy	2021	SIGMOD	5.4556836e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,610	A Workload-Aware Encrypted Index for Efficient Privacy-Preserving Range Queries	2026	VLDB
2	10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
3	5,102	Fast Range Query Processing with Strong Privacy Protection for Cloud Computing	2014	VLDB
4	4,625	Practical Private Range Search Revisited	2016	SIGMOD
5	6,537	Range Search over Encrypted Multi-Attribute Data	2023	VLDB
6	437	Dynamic Authenticated Index Structures for Outsourced Databases	2006	SIGMOD
7	1,504	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
8	4,930	IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential Privacy	2022	SIGMOD
9	8,311	DP-Sync: Hiding Update Patterns in Secure Outsourced Databases with Differential Privacy	2021	SIGMOD
10	1,310	A Privacy-Preserving Index for Range Queries	2004	VLDB