Paper 2013/422

Private Database Queries Using Somewhat Homomorphic Encryption

Dan Boneh, Craig Gentry, Shai Halevi, Frank Wang, and David J. Wu


In a private database query system, a client issues queries to a database and obtains the results without learning anything else about the database and without the server learning the query. While previous work has yielded systems that can efficiently support disjunction queries, performing conjunction queries privately remains an open problem. In this work, we show that using a polynomial encoding of the database enables efficient implementations of conjunction queries using somewhat homomorphic encryption. We describe a three-party protocol that supports efficient evaluation of conjunction queries. Then, we present two implementations of our protocol using Paillier's additively homomorphic system as well as Brakerski's somewhat homomorphic cryptosystem. Finally, we show that the additional homomorphic properties of the Brakerski cryptosystem allow us to handle queries involving several thousand elements over a million-record database in just a few minutes, far outperforming the implementation using the additively homomorphic system.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Full version of ACNS 2013 paper
private database queriessomewhat homomorphic encryption
Contact author(s)
dwu4 @ cs stanford edu
2013-07-02: received
Short URL
Creative Commons Attribution


      author = {Dan Boneh and Craig Gentry and Shai Halevi and Frank Wang and David J.  Wu},
      title = {Private Database Queries Using Somewhat Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2013/422},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.