Paper 2024/092
Call Me By My Name: Simple, Practical Private Information Retrieval for Keyword Queries
Abstract
We introduce $\mathsf{ChalametPIR}$: a single-server Private Information Retrieval (PIR) scheme supporting fast, low-bandwidth \emph{keyword} queries, with a conceptually very simple design. In particular, we develop a generic framework for converting PIR schemes for index queries over flat arrays (based on Learning With Errors) into keyword PIR. This involves representing a key-value map using any probabilistic filter that permits reconstruction of elements from inclusion queries (e.g. Cuckoo filters). In particular, we make use of recently developed \emph{Binary Fuse filters} to construct $\mathsf{ChalametPIR}$, with minimal efficiency blow-up compared with state-of-the-art index-based schemes (all costs bounded by a factor of $\leq 1.08$). Furthermore, we show that $\mathsf{ChalametPIR}$ achieves runtimes and financial costs that are factors of between $6\times$-$11\times$ and $3.75\times$-$11.4\times$ more efficient, respectively, than state-of-the-art keyword PIR approaches, for varying database configurations. Bandwidth costs are reduced or remain competitive, depending on the configuration. Finally, we believe that our application of Binary Fuse filters can have independent value towards developing efficient variants of related cryptographic primitives (e.g. private set intersection), that already benefit from using less efficient filter constructions.
Note: Full version
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. ACM CCS 2024
- DOI
- 10.1145/3658644.3670271
- Keywords
- Private Information Retrieval
- Contact author(s)
-
cherenkov @ riseup net
a davidson @ fct unl pt - History
- 2024-10-02: last of 3 revisions
- 2024-01-20: received
- See all versions
- Short URL
- https://ia.cr/2024/092
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/092, author = {Sofía Celi and Alex Davidson}, title = {Call Me By My Name: Simple, Practical Private Information Retrieval for Keyword Queries}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/092}, year = {2024}, doi = {10.1145/3658644.3670271}, url = {https://eprint.iacr.org/2024/092} }