Paper 2014/345

Private Database Access With HE-over-ORAM Architecture

Craig Gentry, Shai Halevi, Charanjit Jutla, and Mariana Raykova


Enabling private database queries is an important and challenging research problem with many real-world applications. The goal is for the client to obtain the results of its queries without learning anything else about the database, while the outsourced server learns nothing about the queries or data, including access patterns. The secure-computation-over-ORAM architecture offers a promising approach to this problem, permitting sub-linear time processing of the queries (after pre-processing) without compromising security. In this work we examine the feasibility of this approach, focusing specifically on secure-computation protocols based on somewhat-homomorphic encryption (SWHE). We devised and implemented secure two-party protocols in the semi-honest model for the path-ORAM protocol of Stefanov et al. This provides access by index or keyword, which we extend (via pre-processing) to limited conjunction queries and range queries. Some of our sub-protocols may be interesting in their own right, such as our new protocols for encrypted comparisons and blinded permutations. We implemented our protocols on top of the HElib homomorphic encryption library. Our basic single-threaded implementation takes about 30 minutes to process a query on a database with $2^{22}$ records and 120-bit long keywords, providing a cause for optimism about the viability of this direction, and we expect a better optimized implementation to be much faster.

Available format(s)
Publication info
Preprint. MINOR revision.
Comparison ProtocolsHomomorphic EncryptionORAMPIRPrivate QueriesSecure Computation
Contact author(s)
shaih @ alum mit edu
2014-05-19: received
Short URL
Creative Commons Attribution


      author = {Craig Gentry and Shai Halevi and Charanjit Jutla and Mariana Raykova},
      title = {Private Database Access With HE-over-ORAM Architecture},
      howpublished = {Cryptology ePrint Archive, Paper 2014/345},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.