Special Topic Crypto Seminar

— 2:30pm

Location:
In Person and Virtual - ET - Reddy Conference Room, Gates Hillman 4405 and Zoom

Speaker:
WEI-KAI LIN and ETHAN MOOK , Wei-Kai: Postdoctoral Researcher, Ethan: Ph.D. Student, Khoury College of Computer Sciences, Northeastern University

Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring

Two talk about our guests new work.

      → Lunch provided between presentations

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).

This talk consists of an introductory and a technical part. In the introduction, we will present our results at a high level that shows the new feasibility and our key insights. In the technical part, we will summarize our solutions and continue to elaborate on the details such as our algorithms and the comparison to previous results.

Joint work with Daniel Wichs.

In Person and Zoom Participation

Event Website:
https://sites.google.com/view/crypto-seminar/home

Add event to Google
Add event to iCal