Two-Party Computation Model for Privacy-Preserving Queries over Distributed Databases

Many existing privacy-preserving techniques for querying distributed databases of sensitive information do not scale for large databases due to the use of heavyweight cryptographic techniques. In addition, many of these protocols require several rounds of interactions between the participants which may be impractical in wide-area settings. At the other extreme, a trusted party based approach does provide scalability but it forces the individual databases to reveal private information to the central party. This paper shows how to perform various privacy-preserving operations in a scalable manner under the honest-but-curious model. Our system provides the same level of scalability as a trusted central party based solution while providing privacy guarantees without the need for heavyweight cryptography. The key idea is to develop an alternative system model using a Two-Party Query Computation Model comprising of a randomizer and a computing engine which do not reveal any information between themselves. We also show how one can replace the randomizer by a lightweight key-agreement protocol. We formally prove the privacy-preserving properties of our protocols and demonstrate the scalability and practicality of our system using a real-world implementation.