Longshot: Indexing Growing Databases using MPC and Differential Privacy

Summary: Longshot fuses MPC and differential privacy to maintain searchable synopses/indexes on growing outsourced data, leveraging bounded leakage to reduce costly cryptographic work. A time-hierarchical update tree yields logarithmic error growth and a tunable privacy–accuracy–efficiency tradeoff; shows practical gains (5× update speed, ~10^3× query speed after 20 updates). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13055
Venue: VLDB
Year: 2023
Pagerank: 4.8036487e-05
Overall Rank: 7,196 | 49.94%
DOI: 10.14778/3594512.3594529

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,484	Femur: A Flexible Framework for Fast and Secure Querying from Public Key-Value Store	2025	SIGMOD	4.1945683e-05
10,531	SPECIAL: Synopsis Assisted Secure Collaborative Analytics	2025	VLDB	4.1945683e-05
10,664	Calibrating Noise for Group Privacy in Subsampled Mechanisms	2025	VLDB	4.1945683e-05
10,759	PrivAGM: Secure Construction of Differentially Private Directed Attributed Graph Models on Decentralized Social Graphs	2025	VLDB	4.1945683e-05
11,032	SWAT: A System-Wide Approach to Tunable Leakage Mitigation in Encrypted Data Stores	2024	VLDB	4.1945683e-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
136	Revealing Information while Preserving Privacy	2003	PODS	0.0004241101
178	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00037697111
324	Order Preserving Encryption for Numeric Data	2004	SIGMOD	0.00027444645
719	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00017626484
1,307	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.0001266709
1,738	PrivateSQL: A Differentially Private SQL Query Engine	2019	VLDB	0.00010720057
1,859	The Tao of Inference in Privacy-Protected Databases	2018	VLDB	0.0001029011
2,082	Differentially Private Event Sequences over Infinite Streams	2014	VLDB	9.5834599e-05
2,434	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	8.8278955e-05
2,673	Shrinkwrap: Efficient SQL Query Processing in Differentially Private Data Federations	2019	VLDB	8.3333418e-05
2,806	CryptEpsilon: Crypto-Assisted Differential Privacy on Untrusted Servers	2020	SIGMOD	8.0911177e-05
5,519	IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential Privacy	2022	SIGMOD	5.4619886e-05
9,497	DP-Sync: Hiding Update Patterns in Secure Outsourced Databases with Differential Privacy	2021	SIGMOD	4.3341665e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,502	When Query Authentication Meets Fine-Grained Access Control: A Zero-Knowledge Approach	2018	SIGMOD	5.4741324e-05
10,312	A Workload-Aware Encrypted Index for Efficient Privacy-Preserving Range Queries	2026	VLDB	4.1945683e-05
5,367	Fast Range Query Processing with Strong Privacy Protection for Cloud Computing	2014	VLDB	5.5457837e-05
4,799	Practical Private Range Search Revisited	2016	SIGMOD	5.9119553e-05
6,424	Range Search over Encrypted Multi-Attribute Data	2023	VLDB	5.0670573e-05
1,935	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010032967
395	Dynamic Authenticated Index Structures for Outsourced Databases	2006	SIGMOD	0.00024433049
5,519	IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential Privacy	2022	SIGMOD	5.4619886e-05
9,497	DP-Sync: Hiding Update Patterns in Secure Outsourced Databases with Differential Privacy	2021	SIGMOD	4.3341665e-05
1,386	A Privacy-Preserving Index for Range Queries	2004	VLDB	0.00012261809