Paper 2023/466

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

Abstract

In this paper, we introduce $\mathsf{SparsePIR}$, a single-server keyword private information retrieval (PIR) construction that enables querying over sparse databases. At its core, $\mathsf{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. $\mathsf{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, $\mathsf{SparsePIR}^g$ and $\mathsf{SparsePIR}^c$, 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 $\mathsf{SparsePIR}$ may be used to build batch keyword PIR with halved response overhead without any client mappings.