Paper 2021/1438

Incremental Offline/Online PIR (extended version)

Yiping Ma
Ke Zhong
Tal Rabin
Sebastian Angel

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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. USENIX Security 2022
PIRmulti-server PIRincremental cryptographypseudorandom sets
Contact author(s)
sebastian angel @ cis upenn edu
2023-11-17: last of 2 revisions
2021-10-26: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.