Private data querying in the precomputation model
Boyang Li · OhioLink ETD Center (Ohio Library and Information Network) · 2011
Private data querying(PDQ) is about querying a database held by a server without: i) revealing any information about the query to the server, and ii) learning more information than the result of the query.Prior solutions to the PDQ problem require linear(in the size of the dataset) computation and communication, which is impractical for large datasets.In this thesis, we propose a new model for secure computation that separates PDQ protocols into two phases: a precomputation phase and a query phase.We introduce a scheme with sublinear computation and communication query cost under the assumption that the data owner can do a reasonable amount of computation at the precomputation phase.This assumption is reasonable in many environments when the data is known ahead of time and the queries are known at a later time.We introduce such protocols for the following database problems: existence problem, message lookup, the rank of query, one dimensional query, two dimensional range query, a small data change by the server.