Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

8-2025

Abstract

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.

Discipline

Information Security

Research Areas

Information Systems and Management

Areas of Excellence

Digital transformation

Publication

SEC '25: Proceedings of the 34th USENIX Conference on Security Symposium, Seattle, USA, August 13-15

First Page

3397

Last Page

3416

Identifier

10.5555/3766078.3766253

Publisher

ACM

City or Country

New York

Additional URL

https://doi.org/10.5555/3766078.3766253

Download

Share

COinS