Paper 2025/1952

KPIR-C: Keyword PIR with Arbitrary Server-Side Computation

Abstract

Keyword Private Information Retrieval (KPIR) enables clients to retrieve database entries by keyword without revealing their query, with many efficient schemes relying on Fully Homomorphic Encryption (FHE). However, existing FHE-based KPIR schemes fix parameters to a bounded computation depth, which becomes a bottleneck in privacy-sensitive settings such as distributed ledger systems and private web search, where databases grow dynamically and clients are lightweight: exceeding this bound incurs significant overhead, forces larger parameters, and leaves any post-retrieval computation to the client or to communication-heavy interactive protocols. We introduce Keyword PIR with Computation (KPIR-C), a new paradigm that enables arbitrary, non-interactive server-side computation on query responses while preserving query privacy. Unlike prior designs, KPIR-C fixes parameters independently of database size or computation depth by leveraging bootstrapping via a co-design of Torus Fully Homomorphic Encryption (TFHE) and KPIR that keeps bootstrapping overhead practical. We further introduce Keyword PIR with Default (KPIR-D) to handle mismatched queries non-interactively. We instantiate KPIR-C with two constructions: one based on equality circuits and constant-weight codes, and one based on Learning With Errors (LWE)-based KPIR, offering complementary communication-runtime trade-offs. We demonstrate experimentally that both achieve competitive performance compared to state-of-the-art KPIR schemes that do not support arbitrary computation.