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

This paper introduces practical schemes for keyword Private Information Retrieval (keyword PIR), enabling private queries on public databases using keywords. Unlike standard indexbased 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 stateof-the-art keyword PIR, ChalametPIR (CCS'24), i.e., a 15 ∼ 178× reduction in communication and 1.1 ∼ 2.4× 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. Our Contributions This paper presents three concretely efficient keyword PIR constructions based on different key-to-index mapping strate- USENIX Association 34th USENIX Security Symposium 3397 gies. Our contributions are summarized as follows. Keyword PIR from Sparse Key-Value Store. Our first construction KPIR kvs introduces a novel key-value store (KVS) termed sparse KVS. Using this sparse KVS, we achieve keyword PIR by encoding the key-value database into a vector of comparable size to the original database and then performing a constant number of standard PIR operations on this vector. Keyword PIR from Hashing-to-Bins. Our second construction KPIR hash employs hashing-to-bins techniques, similar to MulPIR [5], to retrieve an entire bin based on the query key. To this end, we utilize the row retrieval capability of Kushilevitz-Ostrovsky PIR (KOPIR) [24] , where the database is represented as a matrix and a row of this matrix is privately retrieved. We abstract PIR with this property as Row-KOPIR and instantiate it from pre-processing-based SimplePIR [23] . KPIR hash requires a single invocation of Row-KOPIR on a slightly expanded encoded database.