Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation

Abstract. Can we design a private variant of "Google search" that would enable users to search the Internet privately without revealing their queries to Google? Fully homomorphic encryption gives a solution to this problem, where users would send their search queries to Google encrypted in a way that allows Google to compute the encrypted search results, without learning anything about the query itself. However, this solution would require Google to run a huge computation that touches the entire content of the Internet to answer each encrypted search query, making it realistically infeasible! Is there a way for Google to preprocess the Internet content into a special data structure that would allow it to answer any encrypted query efficiently by only accessing some small number of locations in the data structure? We give a solution to this problem as a special case of our work.

Concretely, we construct the first schemes for "doubly efficient private information retrieval" and "fully homomorphic encryption in the RAM model" under standard cryptographic hardness assumptions (Ring Learning with Errors). Previously we only had heuristic candidate constructions that only satisfied relaxed variants of these primitives. Our new solutions combine tools from cryptography together with data structures for fast polynomial evaluation (Kedlaya and Umans '08).

Joint work with Wei-Kai Lin and Ethan Mook.