Computer Science Speaking Skills Talk
— 2:00pm
Location:
In Person
-
Gates Hillman 9115
Speaker:
MINGXUN ZHOU
,
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://wuwuz.github.io/
Simple, Single-Server Private Information Retrieval with Sublinear Online Computation
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.
—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.