Practical Keyword Private Information Retrieval from Key-to-Index Mappings

Meng Hao, Weiran Liu, Liqiang Peng, Cong Zhang, Pengfei Wu, Lei Zhang, Hongwei Li, Robert H. DengIACR ePrint 2025 · OpenReview

TL;DR

This paper introduces three practical and efficient schemes for Keyword Private Information Retrieval (keyword PIR), enabling users to privately search public databases using keywords. By developing novel key-to-index mappings, they reduce the complex keyword PIR problem to standard PIR, achieving significant improvements in communication and runtime compared to existing methods.

What Problem Does This Paper Address?

Traditional Private Information Retrieval (PIR) allows a client to retrieve data from a server without revealing which specific item they are requesting. However, standard PIR assumes the client knows the exact index of the desired data. In real-world scenarios, data is often organized by keywords, and the client only knows the keyword they are searching for, not its precise location within the database. This is the "keyword PIR" problem. Existing keyword PIR solutions face challenges due to the vastness of keyword domains and the unknown position of the query keyword. Previous approaches either incur prohibitively high communication costs (linear in database size) or involve complex cryptographic operations leading to substantial computational overhead. This paper aims to bridge this gap by offering practical keyword PIR solutions with significantly reduced communication and computation costs.

Methods

The core idea behind the proposed solutions is to transform the keyword PIR problem into a standard PIR problem by creating an efficient "key-to-index mapping." This mapping links keywords to their positions within a specially encoded version of the database. The authors propose three distinct constructions, each employing different strategies for this mapping and encoding:

  1. KPIRkvs (Sparse Key-Value Store): This method encodes the key-value database into a vector that is comparable in size to the original database. It then uses a novel "a-sparse Key-Value Store" (a-sparse KVS) concept, where the decoding process only accesses a small, constant number of elements. This allows for standard PIR operations on the encoded database.
  2. KPIRhash (Hashing-to-Bins): This construction utilizes hashing to distribute database entries into "bins." It then leverages the row retrieval capabilities of Kushilevitz-Ostrovsky PIR (KOPIR) to privately retrieve an entire bin corresponding to the query keyword. This approach reduces the number of standard PIR invocations to one.
  3. KPIRindex (Approximate Key-to-Index Mapping): This is presented as the most efficient method. It introduces an "approximate key-to-index mapping" that allows for a small error (ɛ). This mapping is then combined with a repetition-based matrix encoding and KOPIR to retrieve a small window of entries around the approximate position. This construction also achieves a single invocation of KOPIR.

All three constructions build upon existing PIR primitives like SimplePIR and KOPIR, adapting them for the keyword PIR context.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and experimental evaluation using synthetic databases of varying sizes and entry lengths.

Key Insights and Ideas

  • Reducing Keyword PIR to Standard PIR: The central insight is that by constructing an efficient key-to-index mapping, the complex keyword PIR problem can be effectively reduced to the more manageable standard PIR problem. This is a significant simplification that unlocks efficiency gains.
  • The Power of Approximate Mappings: The KPIRindex construction highlights that an "approximate" key-to-index mapping, with a controlled error bound, can be sufficient and highly beneficial. This allows for more compact mappings and simpler encoding schemes.
  • Leveraging Row Retrieval: The use of Row-KOPIR (a variant of KOPIR that retrieves entire rows of a matrix) is crucial for KPIRhash and KPIRindex, enabling them to achieve single PIR invocations.
  • Practical Efficiency is Achievable: The paper demonstrates that keyword PIR can be made practical, achieving substantial improvements in communication and runtime, making it viable for real-world applications.

Key Results

The authors implemented their three constructions (KPIRkvs, KPIRhash, KPIRindex) and compared them against the state-of-the-art ChalametPIR. The results show significant improvements:

  • Communication: A 15x to 178x reduction in online communication compared to ChalametPIR.
  • Runtime: A 1.1x to 2.4x improvement in online runtime.
  • Practicality: Keyword PIR can be executed in as little as 47 ms for a database of 1 million 32-byte entries.
  • KPIRindex is generally the most efficient, especially in terms of communication, due to its single PIR invocation and efficient encoding.

Limitations and Future Work

  • Database Updates: The current constructions do not efficiently support database updates. While some methods can handle value changes, modifying keys or the entire database requires re-executing the setup phase. This is identified as a key area for future work.
  • Authenticated Variants: Extending the keyword PIR framework to support authentication (e.g., verifying the integrity of the retrieved data) is another promising direction. This would involve ensuring consistency between the committed database and the encoded data used in PIR.
  • Setup Communication: While the online communication is significantly reduced, the setup phase communication (sending hints) can be substantial. However, this cost is amortized over multiple queries.
  • Client Memory: While the key-to-index mappings are generally small, they do add some client-side memory overhead, which varies depending on the construction and parameters.

Summary updated

Abstract

This paper introduces practical schemes for keyword Private Information Retrieval (keyword PIR), enabling private queries on public databases using keywords. Unlike standard index-based PIR, keyword PIR presents greater challenges, since the query's position within the database is unknown and the domain of keywords is vast. Our key insight is to construct an efficient and compact key-to-index mapping, thereby reducing the keyword PIR problem to standard PIR. To achieve this, we propose three constructions incorporating several new techniques. The high-level approach involves (1) encoding the server's key-value database into an indexable database with a key-to-index mapping and (2) invoking standard PIR on the encoded database to retrieve specific positions based on the mapping. We conduct comprehensive experiments, with results showing substantial improvements over the state-of-the-art keyword PIR, ChalametPIR (CCS'24), i.e., a $15\sim178 \times$ reduction in communication and $1.1 \sim 2.4 \times$ runtime improvement, depending on database size and entry length. Our constructions are practical, executing keyword PIR in just 47 ms for a database containing 1 million 32-byte entries.
BibTeX
@article{hao2025practical,
  author = {Meng Hao and Weiran Liu and Liqiang Peng and Cong Zhang and Pengfei Wu and Lei Zhang and Hongwei Li and Robert H. Deng},
  title = {{Practical Keyword Private Information Retrieval from Key-to-Index Mappings}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
  url = {https://openreview.net/forum?id=LLSbCrRpvF},
}
Figure