Doctoral Thesis Oral Defense - Mingxun Zhou

— 3:00pm

Location:
In Person and Virtual - ET - Traffic21 Classroom, Gates Hillman 6501 and Zoom

Speaker:
MINGXUN ZHOU , Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
https://wuwuz.github.io/

Practical Private Information Retrieval and Searching with Sublinear Cost

In this thesis, we investigate Private Information Retrieval (PIR), a cryptographic protocol that enables clients to access information from a database without revealing their queries to the server. As a fundamental building block for privacy-preserving applications, PIR has been extensively studied in both theory and practice for decades. 

However, practical implementations have been limited to small-scale use cases due to the linear computation barrier of PIR, which requires the server to process the entire database for each query. The seminal works of Beimel, Ishai, and Malkin (Crypto 2000) and Corrigan-Gibbs and Kogan (Eurocrypt 2022) introduced Preprocessing PIR to overcome this barrier. While theoretically efficient, previous constructions remained impractical due to their reliance on expensive cryptographic operations. 

To address this limitation, we propose two new PIR schemes: Piano and Quarter-PIR. Both achieve sublinear server computation and communication while remaining efficient in practice. These constructions transform the practical PIR landscape by providing near real-time responses for databases with billions of entries, while maintaining reasonable communication and storage requirements. 

Furthermore, we demonstrate the practical utility of our PIR schemes through an important application – private information searching. We develop Pacmann, a new private approximate nearest neighbor search algorithm that delivers both high search quality and fast response times for databases with hundreds of millions of records. 

Our work makes a significant step toward bridging the gap between theory and practice in PIR research. These contributions not only advance the state of the art in PIR designs, but also open new avenues for developing privacy-preserving applications in real-world and large-scale settings.

Thesis Committee

Elaine Shi (Co-Chair)
Giulia Fanti (Co-Chair)
Bryan Parno
David J. Wu (University of Texas at Austin)

In Person and Zoom Participation.  See announcement.

Add event to Google
Add event to iCal