Doctoral Thesis Proposal - Mingxun Zhou

— 4:00pm

Location:
In Person and Virtual - ET - Reddy Conference Room, Gates Hillman 4405 and Zoom

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

Practical Private Information Retrieval and Searching with Sublinear Cost

Private Information Retrieval (PIR) is a long-studied cryptographic primitive that allows a user to retrieve information from a public database without revealing the query to the service provider. Classically, PIR was studied in a setting without any preprocessing, and this setting is known to have inherent limitations that the total computation cost per query must be linear in the size of the database to achieve privacy. This limitation is the fundamental barrier for scaling PIR to large databases and building practical product systems based on PIR. Pioneered by Beimel, Ishai and Malkin (Crypto 2000) and Corrigan-Gibbs and Kogan (Eurocrypt 2020), the preprocessing PIR paradigm has been shown to overcome the linear computation cost barrier. Nonetheless, prior works on preprocessing PIR remain mostly in the theoretical space due to their use of heavy cryptographic primitives and/or convoluted algorithmic constructions.

Achieved Results: We proposed a practical single-server PIR construction in the preprocessing setting, named Piano (S P 2023), that achieved sublinear query cost based on lightweight cryptographic primitives. Piano achieved $\tilde O(\sqrt{n})$ amortized communication and computation per query given a database of size n , and only required $\tilde O(\sqrt{n})$ client storage. Notably, it is also concretely efficient – for a 100GB database of 1.6 billion entries, Piano takes only 12ms online computation time on a single CPU-core. Subsequently, we improved the construction and obtained a new practical PIR scheme, QuarterPIR (Eurocrypt 2024), that reduced the online communication cost to $\tilde O(n^{1/4})$ per query, while maintaining competitive practical performances. Proposed Direction: Nearly all existing PIR constructions are designed for point accesses in an array-type database, while many practical information retrieval systems like search engines do need more advanced access algorithms to support semantic and similarity queries. We propose to construct a private search algorithm that can handle semantic/similarity queries with sublinear communication and computation query costs based on our practical PIR constructions and graph-based Nearest Neighbor Search (NNS) algorithms. This construction will be the first private search algorithm that achieves sublinear query cost, and it has the potential to support multi-modal search queries including text, image, voice and video search.

Thesis Committee: 

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

Additional Information

In Person and Zoom Participation. See announcement.

Event Website:
https://csd.cmu.edu/calendar/doctoral-thesis-proposal-mingxun-zhou

Add event to Google
Add event to iCal