SaTC: CORE: Small: Doubly Efficient PIR and Encrypted RAM Computation

Is it possible to download a video from a streaming service without revealing to the service which video is being downloaded? Is it possible to search the Internet without revealing the search terms to the search provider? Two advanced cryptographic tools called Private Information Retrieval and Fully Homomorphic Encryption enable secure computations over encrypted data, raising the potential of private services such as the ones above. However, these tools place a heavy computational burden on the server. For example, they would require the search engine to read the entire internet to answer each private search query. The PI’s recent work shows how to remove the above inefficiencies by constructing schemes, where the data is preprocessed once upfront, but afterwards each execution is efficient and avoids reading the entire data. This proposed research builds on the recent progress and addresses many remaining open problems. In addition, the project features graduate student mentoring, curricular development, and undergraduate inclusion in research. The aim of the project is to study Doubly Efficient Private Information Retrieval (DEPIR) and Fully Homomorphic Encryption for Random-Access Machines. The main goals fall into four categories: (1) Practical Efficiency: The existing results show theoretical feasibility, but are highly impractical. Can one get practically efficient constructions? Luckily, there is much potential for improvement/optimization. (2) Assumptions. The existing results are based on the Ring learning-with-errors assumption. Can one also get similar results from standard learning-with-errors, or other assumptions? (3) Beyond Fully Homomorphic Encryption: Can we have other “doubly efficient” cryptographic primitives that operate over huge data in the random-access machine model? Candidates include attribute-based/functional encryption, laconic function evaluation, commitments, succinct arguments and multi-party computation with active security. (4) Client-Specific Preprocessing: We also consider a variant of DEPIR with client-specific preprocessing, which is not known to imply standard private information retrieval or even one-way functions. We explore the possibility of vastly more efficient constructions and potentially even information-theoretic security. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.