Incremental Offline/Online PIR (extended version)

Yiping Ma; Ke Zhong; Tal Rabin; Sebastian Angel

Paper 2021/1438

Incremental Offline/Online PIR (extended version)

Yiping Ma

Ke Zhong

Tal Rabin

Sebastian Angel

Abstract

Recent private information retrieval (PIR) schemes preprocess the database with a query-independent offline phase in order to achieve sublinear computation during a query-specific online phase. These offline/online protocols expand the set of applications that can profitably use PIR, but they make a critical assumption: that the database is immutable. In the presence of changes such as additions, deletions, or updates, existing schemes must preprocess the database from scratch, wasting prior effort. To address this, we introduce incremental preprocessing for offline/online PIR schemes, allowing the original preprocessing to continue to be used after database changes, while incurring an update cost proportional to the number of changes rather than the size of the database. We adapt two offline/online PIR schemes to use incremental preprocessing and show how it significantly improves the throughput and reduces the latency of applications where the database changes over time.

Note: Extended version of the paper "Incremental Offline/Online PIR" which appears at USENIX Security 2022. This version includes an additional PIR protocol and more evaluation results.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. USENIX Security 2022
Keywords: PIR multi-server PIR incremental cryptography pseudorandom sets
Contact author(s): sebastian angel @ cis upenn edu
History: 2023-11-17: last of 2 revisions; 2021-10-26: received; See all versions
Short URL: https://ia.cr/2021/1438
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1438,
      author = {Yiping Ma and Ke Zhong and Tal Rabin and Sebastian Angel},
      title = {Incremental Offline/Online {PIR} (extended version)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1438},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1438}
}