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

Sherman S.M. Chow, Jie Han Lee, Lakshminarayanan Subramanian

Research output: Contribution to conferencePaperpeer-review


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.

Original languageEnglish (US)
StatePublished - 2009
Event16th Symposium on Network and Distributed System Security, NDSS 2009 - San Diego, United States
Duration: Feb 8 2009Feb 11 2009


Conference16th Symposium on Network and Distributed System Security, NDSS 2009
Country/TerritoryUnited States
CitySan Diego

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Systems Engineering
  • Safety, Risk, Reliability and Quality


Dive into the research topics of 'Two-Party Computation Model for Privacy-Preserving Queries over Distributed Databases'. Together they form a unique fingerprint.

Cite this