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

Описание: 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.

Link: https://eprint.iacr.org/2024/318