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

We introduce $\mathsf{ChalametPIR}$: a single-server Private Information Retrieval (PIR) scheme supporting fast, low-bandwidth 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 the Learning With Errors problem) 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 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$-$11\times$ and $3.75$-$11.4\times$ more efficient, respectively, than state-of-the-art keyword PIR approaches, for varying database configurations. Bandwidth costs are additionally 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: Correcting an incorrect section reference introduced in the previous revision

Available format(s)
Cryptographic protocols
Publication info
Private Information Retrieval
Contact author(s)
cherenkov @ riseup net
a davidson @ fct unl pt
2024-02-08: last of 2 revisions
2024-01-20: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.