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.5216365e-05
Overall Rank: 2,399 | 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.00018121827
898	Orthogonal Security With Cipherbase	2013	CIDR	0.00013189879
1,834	Authenticated Join Processing in Outsourced Databases	2009	SIGMOD	9.537823e-05
4,474	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.5838686e-05
4,845	Integrity Auditing of Outsourced Data	2007	VLDB	6.3827725e-05
5,975	Secure Outsourced Aggregation via One-way Chains	2009	SIGMOD	5.9305225e-05
12,837	An Audit Environment for Outsourcing of Frequent Itemset Mining	2009	VLDB	4.9793485e-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
68	Privacy-Preserving Data Mining	2000	SIGMOD	0.00037958605
115	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD	0.00031742473
411	Hippocratic Databases	2002	VLDB	0.00018699914
568	Extending Query Rewriting Techniques for Fine-Grained Access Control	2004	SIGMOD	0.00016262553
2,175	Two Can Keep a Secret: A Distributed Architecture for Secure Database Services	2005	CIDR	8.9159708e-05
4,281	A Unified Framework for Enforcing Multiple Access Control Policies	1997	SIGMOD	6.6893592e-05

Semantically Similar Papers

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