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: 9530
Venue: VLDB
Year: 2005
Pagerank: 8.7114376e-05
Overall Rank: 2,350 | 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
437	Dynamic Authenticated Index Structures for Outsourced Databases	2006	SIGMOD	0.00018489863
876	Orthogonal Security With Cipherbase	2013	CIDR	0.00013467554
1,804	Authenticated Join Processing in Outsourced Databases	2009	SIGMOD	9.7171985e-05
4,381	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.7333392e-05
4,760	Integrity Auditing of Outsourced Data	2007	VLDB	6.5206581e-05
5,853	Secure Outsourced Aggregation via One-way Chains	2009	SIGMOD	6.0655523e-05
12,547	An Audit Environment for Outsourcing of Frequent Itemset Mining	2009	VLDB	5.093636e-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
70	Privacy-Preserving Data Mining	2000	SIGMOD	0.0003804755
114	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD	0.00032363776
404	Hippocratic Databases	2002	VLDB	0.00019065022
552	Extending Query Rewriting Techniques for Fine-Grained Access Control	2004	SIGMOD	0.00016630306
2,133	Two Can Keep a Secret: A Distributed Architecture for Secure Database Services	2005	CIDR	9.1164075e-05
4,195	A Unified Framework for Enforcing Multiple Access Control Policies	1997	SIGMOD	6.8425335e-05

Semantically Similar Papers

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