IACR News item: 19 May 2014
Craig Gentry, Shai Halevi, Charanjit Jutla, Mariana Raykova
ePrint ReportIn 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.
Additional news items may be found on the IACR news page.