Private Information Retrieval with Sublinear Online Time
Event details
| Date | 10.12.2019 |
| Hour | 15:15 |
| Speaker | Dima Kogan, Stanford University |
| Location | |
| Category | Conferences - Seminars |
Abstract
We present the first protocols for private information retrieval that allow fast (sublinear-time) database lookups without increasing the server-side storage requirements. To achieve these efficiency goals, our protocols work in an offline/online model. In an offline phase, which takes place before the client has decided which database bit it wants to read, the client fetches a short string from the servers. In a subsequent online phase, the client can privately retrieve its desired bit of the database by making a second query to the servers. By pushing the bulk of the server-side computation into the offline phase (which is independent of the client's query), our protocols allow the online phase to complete very quickly—in time sublinear in the size of the database. Finally, we prove that our protocols are optimal in terms of the trade-off they achieve between communication and running time. Joint work with Henry Corrigan-Gibbs
Biography
Dmitry Kogan is a fourth-year PhD student at Stanford University working on cryptography and security with Dan Boneh and David Mazières. Dmitry holds an MSc in computer science from the Weizmann Institute, and a BSc in mathematics, physics, and computer science from the Hebrew University. He previously worked on data analytics and account security at Google. His research has received best young researcher awards at Eurocrypt and TCC.
We present the first protocols for private information retrieval that allow fast (sublinear-time) database lookups without increasing the server-side storage requirements. To achieve these efficiency goals, our protocols work in an offline/online model. In an offline phase, which takes place before the client has decided which database bit it wants to read, the client fetches a short string from the servers. In a subsequent online phase, the client can privately retrieve its desired bit of the database by making a second query to the servers. By pushing the bulk of the server-side computation into the offline phase (which is independent of the client's query), our protocols allow the online phase to complete very quickly—in time sublinear in the size of the database. Finally, we prove that our protocols are optimal in terms of the trade-off they achieve between communication and running time. Joint work with Henry Corrigan-Gibbs
Biography
Dmitry Kogan is a fourth-year PhD student at Stanford University working on cryptography and security with Dan Boneh and David Mazières. Dmitry holds an MSc in computer science from the Weizmann Institute, and a BSc in mathematics, physics, and computer science from the Hebrew University. He previously worked on data analytics and account security at Google. His research has received best young researcher awards at Eurocrypt and TCC.
Practical information
- General public
- Free
- This event is internal
Organizer
- Prof. Bryan Ford
Contact
- Sandra Genolet