SaTC: CORE: Small: Practical Private Information Retrieval

Private information retrieval (PIR) is one of the most fundamental cryptographic primitives to protect user privacy online. It has many applications including anonymous communication, privacy-preserving media streaming, and private look-ups for safe browsing. PIR is also closely related to other important privacy-preserving cryptographic tools, such as private set intersection, which has been used in password monitoring and harmful content discovery. After decades of research, single-server PIR schemes still have performance limitations. The main bottlenecks include high communication costs, heavy computation, and large server storage. The performance further worsens if the database has many entries but each individual entry is small -- a common scenario in real-world applications. Unfortunately, many of these obstacles are fundamental in the standard setting of PIR. This project presents new paradigms for single-server PIR, including homomorphic encryption composition, vectorized batch PIR, and stateful PIR. The goal is to substantially improve single-server PIR in all aspects: communication, computation, storage, and range of supported database parameters, to eventually make it practical for a wide range of real-world applications. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.