Welcome to the resource topic for 2023/466
Title:
Don’t be Dense: Efficient Keyword PIR for Sparse Databases
Authors: Sarvar Patel, Joon Young Seo, Kevin Yeo
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.
ePrint: https://eprint.iacr.org/2023/466
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .