Private Information Retrieval and Searching with Sublinear Costs

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.