Private information retrieval protocols and applications

• Grant number: 24/23608-9
• Support Opportunities: Scholarships in Brazil - Master
• Start date: March 01, 2025
• End date: February 28, 2027
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Hilder Vitor Lima Pereira
• Grantee: Alex Luiz Domingues Cassinelli
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 23/12755-8 - Homomorphic encryption and computation on encrypted data, AP.JP

Abstract

Private information retrieval (PIR) protocols allow a user to retrieve an item from a database stored on a server without revealing what the item is. In more detail, imagine a server that has a database D in clear and a client that wants to download the i-th item from D. The client can encrypt i in some way, generating a ciphertext c, which is then sent to the server. The server then uses c to retrieve the i-th item, but also encrypted in some ciphertext C. The client then downloads C and decrypts it, finally retrieving the desired item. At the end of the protocol, the client only knows the requested item and the server has no information about i. PIR protocols have several possible applications, such as using streaming systems, like Netflix and YouTube, without the server knowing which videos are being watched.The state of the art involves protocols that are asymptotically optimal but slow in practice, and suboptimal protocols that are, however, the most efficient for many scenarios. Ideally, protocols that are optimal in theory should have performance at least close to that of protocols used in practice, which would give us PIR with reduced communication costs and acceptable execution times. Therefore, this project aims to reduce the gap between the performance of PIR protocols with optimal communication costs and suboptimal protocols, making theory meet practice.