Recent Progress in Private Information Retrieval
- Mingxun Zhou, Carnegie Mellon University
- Time: 2023-07-18 16:00
- Host: Turing Class Research Committee
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
Private Information Retrieval(PIR) is a cryptographic primitive that allows a client to access public data without leaking the access history. Researchers have achieved the theoretical optimal results in terms of reducing client computation and communication costs in the classical model. Unfortunately, the per-query server computation cost has been proven to be at least of the order of linearly scanning the whole database in this model. Recently, the Preprocessed PIR model has been proposed and the existence of sub-linear server-cost algorithms has been proved. Our theoretical work (Eurocrypt 2023) constructed a nearly-optimal algorithm in this model. However, without a stronger assumption such as the existence of multiple non-colluding servers, a truly practical sub-linear PIR algorithm is still unknown.
Until recently, we proposed the first truly practical single-server sub-linear PIR algorithm, Piano. Piano does not require any heavy-weight cryptographic primitives and is extremely easy to implement. It is sufficiently efficient for practical usage: given a 100GB database, a single query only takes less than 40ms computation time, which is 100x faster than previous single-server PIR schemes.
This talk will not assume any background on cryptography. It will be based on the speaker's two recent collaborative works with Andrew Park, Elaine Shi, Wenting Zheng, Yiannis Tselekounis and Wei-Kai Lin.
Biography
Mingxun Zhou is a PhD student in the Computer Science Department at Carnegie Mellon University, advised by Elaine Shi and Giulia Fanti. His research focuses on privacy-preserving algorithm design, including differential private algorithms and cryptography. He also has research work on Blockchain technology, P2P network.