**
Efficient Consistency Proofs for Generalized Queries on a Committed Database
**

*
Rafail Ostrovsky, Charles Rackoff, Adam Smith
*

**
Abstract:
**
A * consistent query protocol * (CQP) allows a database owner to publish a
very short string c which * commits* her and everybody else to a
particular database D, so that any copy of the database can later be used
to answer queries and give short proofs that the answers are consistent with
the commitment c. Here commits means that there is at most one
database D that anybody can find (in polynomial time) which is consistent
with c.
(Unlike in some previous work, this strong guarantee holds even for owners
who try to cheat while creating c.) Efficient CQPs for membership and one-dimensional
range queries are known[4, 11, 16]: given a query pair a,b∈ R,
the server answers with all the keys in the database which lie in the
interval [a,b] and a proof that the answer is correct.

This paper explores CQPs for more general types of databases. We put
forward a general technique for constructing CQPs for any type of query,
assuming the existence of a data structure/algorithm with certain inherent
robustness properties that we define (called a *data robust algorithm*).
We illustrate our technique by constructing an efficient protocol for *
orthogonal range queries*, where the database keys are points in
R^{d} andand a query asks for all keys in a rectangle [a_{1},b_{1}]X...X [a_{ d}B_{d}].
Our data-robust algorithm is within a O(\log N)
factor of the best known standard data structure (a range tree, due to
Bentley[2]).

We modify our protocol so that it is also * private, * that is, the proofs
leak no information about the database beyond the query answers. We show a
generic modification to ensure privacy based on zero-knowledge proofs, and
also give a new, more efficient protocol tailored to hash trees.

** Keywords:** Zero-Knowledge Sets, general complexity assumptions, efficient
commitment protocols, interactive proofs, communication complexity.

**comment:**
To appear in
ICALP-2004.

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |