Incremental Offline/Online PIR (Extended Version)

Summary

Generally, PIR schemes have an offline phase where a query-independent pre-processing is performed. Then a query-dependent online phase is used to perform PIR. The offline/online separation gives performance benefits.
Databases can mutate (add,remove,update) after the pre-processing phase which requires a fresh offline phase which is expensive.
This work presents a PIR protocol that allows incremental modifications to the database.
The idea seems to be to use sets. When adding a new element add it to sufficiently sets to ensure privacy. In-place edits/modification is easy by just changing the sets. In deletion also, remove the element from the sets.
Performance:
- For a database of over 1 M items they show for an update batch size of 10,000 items that get a 56x cheaper than preprocessing from scratch.
- They claim modest overheads.

Yiping Ma, Ke Zhong, Tal Rabin, and Sebastian Angel. 2021. “Incremental Offline/Online PIR (extended version).” https://eprint.iacr.org/2021/1438.