Don’t be Dense: Efficient Keyword PIR for Sparse Databases


Sarvar Patel and Joon Young Seo, Google; Kevin Yeo, Google and Columbia University

Distinguished Paper Award Winner


In this paper, we introduce SparsePIR, a single-server keyword private information retrieval (PIR) construction that enables querying over sparse databases. At its core, SparsePIR is based on a novel encoding algorithm that encodes sparse database entries as linear combinations while being compatible with important PIR optimizations including recursion. SparsePIR achieves response overhead that is half of state-of-the art keyword PIR schemes without requiring long-term client storage of linear-sized mappings. We also introduce two variants, SparsePIRg and SparsePIRc, that further reduces the size of the serving database at the cost of increased encoding time and small additional client storage, respectively. Our frameworks enable performing keyword PIR with, essentially, the same costs as standard PIR. Finally, we also show that SparsePIR may be used to build batch keyword PIR with halved response overhead without any client mappings.

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.

@inproceedings {287318,
author = {Sarvar Patel and Joon Young Seo and Kevin Yeo},
title = {{Don{\textquoteright}t} be Dense: Efficient Keyword {PIR} for Sparse Databases},
booktitle = {32nd USENIX Security Symposium (USENIX Security 23)},
year = {2023},
isbn = {978-1-939133-37-3},
address = {Anaheim, CA},
pages = {3853--3870},
url = {},
publisher = {USENIX Association},
month = aug

Presentation Video