Query Execution Assurance for Outsourced Databases

Summary: Proposes query execution proofs for outsourced databases, delivering cryptographic proof that actual execution occurred over the entire data set for arbitrary queries. Experimental validation in real-world data mining shows feasibility, with under 25% overhead achieving over 95% assurance and preliminary support for updates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hb1118fe8895c61ee
Venue: VLDB
Year: 2005
Pagerank: 8.5176046e-05
Overall Rank: 2,400 | 83.88%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Radu Sion (State University of New York at Stony Brook)

BibTeX Citation

@article{sion_vldb05,
        title = {{Query Execution Assurance for Outsourced Databases}},
        author = {Sion, Radu},
        journal = {PVLDB},
        series = {{VLDB} '05},
        volume = {31},
        pages = {601--612},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
449	Dynamic Authenticated Index Structures for Outsourced Databases	2006	SIGMOD	0.00018113248
899	Orthogonal Security With Cipherbase	2013	CIDR	0.00013183669
1,835	Authenticated Join Processing in Outsourced Databases	2009	SIGMOD	9.53331e-05
4,476	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.580752e-05
4,847	Integrity Auditing of Outsourced Data	2007	VLDB	6.379751e-05
5,975	Secure Outsourced Aggregation via One-way Chains	2009	SIGMOD	5.927715e-05
12,843	An Audit Environment for Outsourcing of Frequent Itemset Mining	2009	VLDB	4.9769913e-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
69	Privacy-Preserving Data Mining	2000	SIGMOD	0.00037940729
115	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD	0.00031727517
412	Hippocratic Databases	2002	VLDB	0.00018691177
568	Extending Query Rewriting Techniques for Fine-Grained Access Control	2004	SIGMOD	0.00016254878
2,178	Two Can Keep a Secret: A Distributed Architecture for Secure Database Services	2005	CIDR	8.9117503e-05
4,283	A Unified Framework for Enforcing Multiple Access Control Policies	1997	SIGMOD	6.6861926e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,564	TrustedDB: A Trusted Hardware based Outsourced Database Engine	2011	VLDB
2	9,345	OBSCURE: Information-Theoretic Oblivious and Verifiable Aggregation Queries	2019	VLDB
3	5,124	Secure Query Processing with Data Interoperability in a Cloud Database Environment	2014	SIGMOD
4	115	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD
5	1,835	Authenticated Join Processing in Outsourced Databases	2009	SIGMOD
6	5,441	When Query Authentication Meets Fine-Grained Access Control: A Zero-Knowledge Approach	2018	SIGMOD
7	1,723	CorrectDB: SQL Engine with Practical Query Authentication	2013	VLDB
8	4,988	Scalable Verification for Outsourced Dynamic Databases	2009	VLDB
9	449	Dynamic Authenticated Index Structures for Outsourced Databases	2006	SIGMOD
10	4,847	Integrity Auditing of Outsourced Data	2007	VLDB