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.4895798e-05
Overall Rank: 2,411 | 83.85%
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
451	Dynamic Authenticated Index Structures for Outsourced Databases	2006	SIGMOD	0.00018054106
903	Orthogonal Security With Cipherbase	2013	CIDR	0.00013141357
1,848	Authenticated Join Processing in Outsourced Databases	2009	SIGMOD	9.5022605e-05
4,498	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.5590284e-05
4,870	Integrity Auditing of Outsourced Data	2007	VLDB	6.358695e-05
5,987	Secure Outsourced Aggregation via One-way Chains	2009	SIGMOD	5.9081794e-05
12,886	An Audit Environment for Outsourcing of Frequent Itemset Mining	2009	VLDB	4.9605343e-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.00037815735
115	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD	0.00031623329
414	Hippocratic Databases	2002	VLDB	0.00018629709
570	Extending Query Rewriting Techniques for Fine-Grained Access Control	2004	SIGMOD	0.00016201674
2,194	Two Can Keep a Secret: A Distributed Architecture for Secure Database Services	2005	CIDR	8.8822913e-05
4,297	A Unified Framework for Enforcing Multiple Access Control Policies	1997	SIGMOD	6.6640927e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,582	TrustedDB: A Trusted Hardware based Outsourced Database Engine	2011	VLDB
2	9,371	OBSCURE: Information-Theoretic Oblivious and Verifiable Aggregation Queries	2019	VLDB
3	5,144	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,848	Authenticated Join Processing in Outsourced Databases	2009	SIGMOD
6	5,452	When Query Authentication Meets Fine-Grained Access Control: A Zero-Knowledge Approach	2018	SIGMOD
7	1,730	CorrectDB: SQL Engine with Practical Query Authentication	2013	VLDB
8	5,012	Scalable Verification for Outsourced Dynamic Databases	2009	VLDB
9	451	Dynamic Authenticated Index Structures for Outsourced Databases	2006	SIGMOD
10	4,870	Integrity Auditing of Outsourced Data	2007	VLDB