Paper 2025/210

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

Meng Hao, School of Computing & Information Systems, Singapore Management University
Weiran Liu, Alibaba Group
Liqiang Peng, Alibaba Group
Cong Zhang, Institute for Advanced Study, BNRist, Tsinghua University
Pengfei Wu, School of Computing & Information Systems, Singapore Management University
Lei Zhang, Alibaba Group
Hongwei Li, Peng Cheng Laboratory
Robert H. Deng, School of Computing & Information Systems, Singapore Management University
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 reduction in communication and 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. USENIX Security 2025
Keywords
keyword PIR
Contact author(s)
menghao303 @ gmail com
weiran lwr @ alibaba-inc com
plq270998 @ alibaba-inc com
zhangcong @ mail tsinghua edu cn
pfwu @ smu edu sg
zongchao zl @ taobao com
hongweili @ uestc edu cn
robertdeng @ smu edu sg
History
2025-02-12: approved
2025-02-12: received
See all versions
Short URL
https://ia.cr/2025/210
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/210,
      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},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/210},
      year = {2025},
      url = {https://eprint.iacr.org/2025/210}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.