Private Information Retrieval with Subpolynomial Communication

Abstract

Private information retrieval (PIR) allows a user to retrieve a database entry without revealing the index of the requested entry to a server by querying multiple non-colluding servers. We survey recent advancements in PIR protocols, focusing on those with subpolynomial communication complexity and their construction using matching vector families. We also discuss and apply transformations to recent protocols to establish robust PIR protocols that are tolerant of server failures and malicious responses.