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 potential solution to this problem, but would require Google to run a huge computation that is linear in the size of the entire internet to answer each encrypted search query. Can Google to preprocess the internet content into a special data structure that would then allow it to answer each encrypted search query very efficiently by only accessing a 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 (DEPIR)” and “fully homomorphic encryption in the RAM model (RAM-FHE)” 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.