Welcome to the resource topic for 2024/092
Title:
Call Me By My Name: Simple, Practical Private Information Retrieval for Keyword Queries
Authors: Sofía Celi, Alex Davidson
Abstract: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\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 additionally reduced or remain competitive, depending on the configuration. Finally, we believe that our application of Binary Fuse filters in the cryptography setting may bring immediate independent value towards developing efficient variants of other related primitives that benefit from using such filters.
ePrint: https://eprint.iacr.org/2024/092
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 .