Meng Hao, School of Computing & Information Systems, Singapore Management University; Weiran Liu and 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
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∼178 x reduction in communication and 1.1 ∼ 2.4 x 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.
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
