Yiping Ma and Ke Zhong, University of Pennsylvania; Tal Rabin, University of Pennsylvania and Algorand Foundation; Sebastian Angel, University of Pennsylvania and Microsoft Research
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, this paper introduces incremental preprocessing for offline/online PIR schemes, allowing the original preprocessing to continue to be used after database changes, while paying an update cost proportional to the number of changes rather than linear in the size of the database. We adapt two offline/online PIR schemes to use incremental preprocessing and show that our approach significantly improves throughput and reduces the latency of applications where the database changes over time.
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
author = {Yiping Ma and Ke Zhong and Tal Rabin and Sebastian Angel},
title = {Incremental {Offline/Online} {PIR}},
booktitle = {31st USENIX Security Symposium (USENIX Security 22)},
year = {2022},
isbn = {978-1-939133-31-1},
address = {Boston, MA},
pages = {1741--1758},
url = {https://www.usenix.org/conference/usenixsecurity22/presentation/ma},
publisher = {USENIX Association},
month = aug
}
