The basic two-party query computation model describes the types of privacy preserving protocols.
Figure 1 illustrates the basic two-party query computation model comprising of four different
entities: the randomizer, the computing engine, the query front end engine and the individual
databases. The two primary query computation entities in the system are the randomizer and the
computing engine. The query front end engine which receives queries from different users
forwards each query to the randomizer and an encoded version of the query (which contains the
type of the query) to the computing engine which in turn coordinate with the individual
databases to compute the query result. Our model assumes that all entities in the system
require strong privacy guarantees but act in an honest but curious manner. In other words, every
participating entity acts in an “honest” fashion and follows the protocol specification, but is
“curious” to infer the entries of other participating databases.
Figure 1 : The system model
Given this model, the basic steps in our query computation process are illustrated in Figure 1.
The randomizer upon receiving a query, forwards the query to each individual database along with
a set of randomization parameters. The randomizer also provides an essential set of the
derandomization parameters to the query front end (which the querier may use to encode the query
in case the selection predicate is based on a certain computation of the distributed data, and
should be protected). Every database independently computes the local query response for the
query and then obfuscates the query response using the randomization parameters. According to the
query type, the computing engine performs the query computation by “combining” the individual
obfuscated responses from the individual databases and produces an obfuscated response to the
query. The query front end then makes use of the derandomization parameters to deobfuscate the
query response from the computing engine.
We make a simplifying assumption that all the databases share the same schema which is also known
to the querier; in practice, even if the individual schemas differ, the query processing engine at
the individual databases can convert their individual results to a common schema.