Abstract: Private Information Retrieval (PIR) is a cryptographic primitive that allows a client to query for some element of a public database, held by a server, without revealing the element that the client is interested in. Recent developments in PIR have used client-side preprocessing to speed up online query times. In this model, a client can run offline to compute a hint which it later uses to issue online queries. Unfortunately, all proposed solutions in this model before this work suffer from two significant drawbacks: (1) updating an entry in the database requires some inefficient computation and (2) a client's query time is linear in their hint size.
In this work, we overcome both of these obstacles by proposing Plinko, a new PIR scheme in the client-side preprocessing model. As part of our construction, we provide a new primitive called an invertible pseudorandom function, which allows someone with the secret key to find the pre-image of some output efficiently. This primitive allows us to generically upgrade two previously proposed schemes to both: (1) update entries with nearly-constant time and communication and (2) avoid clients' linear pass through their hints, improving the asymptotic runtime for clients with large storage.
Bio: Alex Hoover recently defended for his PhD in Cryptography at the University of Chicago under his advisor, David Cash. His dissertation focuses on secure and efficient outsourced computation, exploring the limits of oblivious RAM, structured encryption, and private information retrieval. He is generally interested in understanding the limits of efficiency in secure computation, especially explored through new constructions and lower bounds. Outside of cryptography, he also has a broad range of interests and has previously worked on topics ranging from quantum systems to complexity of election manipulation.
