Cryptology ePrint Archive: Report 2021/1438

Incremental Offline/Online PIR (extended version)

Yiping Ma and Ke Zhong and Tal Rabin and 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.

Category / Keywords: cryptographic protocols / PIR, multi-server PIR, incremental cryptography, pseudorandom sets

Original Publication (with major differences): USENIX Security 2022

Date: received 26 Oct 2021

Contact author: sebastian angel at cis upenn edu

Available format(s): PDF | BibTeX Citation

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.

Version: 20211026:070358 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]