Grainger College of Engineering, All Events

View Full Calendar

Alex Hoover "Plinko: Single-Server PIR with Efficient Updates via Invertible PRFs"

Event Type
Department of Computer Science
Thomas M. Siebel Center for Computer Science SC 4102
Apr 30, 2024   4:00 pm  
Alex Hoover, University of Chicago
Kalen Mc Gowan
Originating Calendar
Computer Science Speakers Calendar

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.

link for robots only