Alex Hoover: Plinko - Single-Server PIR with Efficient Updates via Invertible PRFs
Автор: CMU × LayerZero Crypto Seminar
Загружено: 2024-05-02
Просмотров: 253
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
Доступные форматы для скачивания:
Скачать видео mp4
-
Информация по загрузке:
