Efficient Consistency Proofs for Generalized Queries on a Committed Database

摘要: A consistent query protocol (cqp) allows a database owner to publish very short string c which commits her and everybody else particular D, so that any copy of the can later be used answer queries give proofs answers are with commitment c. Here means there is at most one D anybody find (in polynomial time) (Unlike in some previous work, this strong guarantee holds even for owners who try cheat while creating c.) Efficient cqps membership one-dimensional range known [4,11,16]: given pair a,b ∈ ℝ, server all keys lie interval [a,b] proof correct. This paper explores more general types databases. We put forward technique constructing type query, assuming existence data structure/algorithm certain inherent robustness properties we define (called robust algorithm). illustrate our by an efficient orthogonal queries, where points ℝ d asks rectangle [a 1,b 1]×...×[a ,b ]. Our data-robust algorithm within O(log N) factor best standard structure (a tree, due Bentley [2]).