Mingxun Zhoun
January 31, 2024 at 11:00 AM on Zoom / Soda Hall
Efficient Pre-processing PIR Without Public-Key Cryptography
Abstract: In a series of research works, we constructed several sublinear-time single-server pre-processing Private Information Retrieval (PIR) schemes with optimal client storage and server computation (up to poly-logarithmic factors). The first scheme, Piano (S&P 24), achieves amortized $\tilde{O}(\sqrt{n})$ online server computation and client computation and $O(\sqrt{n})$ online communication per query, and requires $\tilde{O}_{\lambda}(n)$ client storage. For a 100GB database of 1.6 billion entries, the experiments show that our scheme has less than 12ms online computation time on a single core. More recently, we propose a new scheme that improves online communication to $O_\lambda(n^{1/4})$, which takes less than 6KB and 10-50x less online communication compared to Piano in our experiments.
Bio: 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 and P2P networks.