Paper 2024/092

Call Me By My Name: Simple, Practical Private Information Retrieval for Keyword Queries

Sofía Celi, Brave Software
Alex Davidson, Universidade NOVA de Lisboa, NOVA LINCS
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.