[Resource Topic] 2014/345: Private Database Access With HE-over-ORAM Architecture

Welcome to the resource topic for 2014/345

Title:
Private Database Access With HE-over-ORAM Architecture

Authors: Craig Gentry, Shai Halevi, Charanjit Jutla, Mariana Raykova

Abstract:

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.

ePrint: https://eprint.iacr.org/2014/345

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .