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

Ali Arastehfard, Weiran Liu, Qixian Zhou, Zinan Shen, Liqiang Peng, Lin Qu, Shuya Feng, Yuan HongIACR ePrint 2025

Abstract

Keyword Private Information Retrieval (KPIR) typically restricts clients to simple data retrieval, requiring expensive local computation or multi-round protocols for further data processing. We present KPIR-C, a novel framework leveraging Torus Fully Homomorphic Encryption (TFHE) to enable arbitrary server-side computation on retrieved records without compromising privacy. By introducing a "one-hot" bootstrapping strategy and a mechanism for handling keyword mismatches, KPIR-C achieves sub-second query times on million-entry databases with minimal communication overhead.

Introduction

Private Information Retrieval (PIR) is a cornerstone of privacy-preserving technology, allowing users to fetch records from a server without revealing their access patterns. Keyword PIR (KPIR) extends this by allowing queries based on strings rather than indices. However, a significant gap remains: existing KPIR solutions are optimized for retrieval only. If a client needs to perform analytics on the retrieved data—such as checking a balance threshold or aggregating multiple values—they must either download large encrypted payloads for local processing or engage in complex secure multi-party computation (MPC).

Moving Beyond Simple Retrieval

The primary obstacle to "KPIR with Computation" is the Mismatch Problem. In standard KPIR, if a keyword is not found, the server often returns random noise or an undefined value. This "pollution" makes subsequent server-side computation impossible, as any logic applied to noise will yield garbage results.

Table 1: Comparison of KPIR schemes highlighting the unique ability of KPIR-C to return agreed-upon values on mismatch.

As shown in the comparison above, KPIR-C introduces a "Return on Mismatch" feature. By ensuring the server returns a pre-agreed default value ($\delta$) when a keyword is missing, the system allows for stable, continuous computation on the server side without breaking the underlying logic.

System Architecture and Innovations

KPIR-C utilizes Torus Fully Homomorphic Encryption (TFHE) as its core engine. Unlike traditional leveled FHE schemes (like BFV), TFHE supports "programmable bootstrapping," which refreshes ciphertext noise in milliseconds, enabling circuits of arbitrary depth.

Figure 1: The KPIR-C workflow, illustrating the 5-step process from client-side encoding to server-side selection and recovery.

The framework operates through a five-step process:

  1. CWEncode: The client encodes and encrypts the keyword.
  2. CWEq: The server generates a selection vector (SV) by comparing the query against the database keys.
  3. Select: The server uses the SV to pick the corresponding encrypted values.
  4. Multiplexer: A critical step where the system handles mismatches by selecting between the retrieved ciphertext and a default value $\delta$.
  5. Recover: The client decrypts the final result.

To optimize performance, the authors developed a KPIR-Specific Bootstrapping Strategy (KBS). Recognizing that the selection vector is "one-hot" (containing only one '1'), they can aggregate up to $2^{20}$ entries before requiring a bootstrap, drastically reducing the computational overhead typically associated with FHE.

Key Results and Performance

KPIR-C demonstrates significant improvements over state-of-the-art BFV-based schemes:

  • Communication Efficiency: The TCWKPIR variant achieves a 9.7x reduction in communication for a $2^{16}$ entry database. Responses are consistently small (3–9 KB), regardless of the database size.
  • Latency: The client-aided TCAKPIR+ variant achieves sub-second online latency (approx. 0.45s to 0.82s) for databases with over 1 million entries.
  • Scalability: While competing schemes often encounter memory limits at large scales, KPIR-C remains stable and performant at $2^{20}$ entries.

Conclusion

KPIR-C represents a shift from simple private retrieval to private server-side analytics. By solving the mismatch problem and optimizing TFHE for the one-hot nature of PIR, the framework enables complex applications like "Fuzzy PIR" (e.g., finding the $k$-closest GPS coordinates) with minimal latency and bandwidth. Future work will focus on enhancing server-side privacy to protect the database from malicious clients while maintaining these performance gains.

Summary updated

BibTeX
@article{arastehfard2025kpir,
  author = {Ali Arastehfard and Weiran Liu and Qixian Zhou and Zinan Shen and Liqiang Peng and Lin Qu and Shuya Feng and Yuan Hong},
  title = {{KPIR-C: Keyword PIR with Arbitrary Server-side Computation}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
}
Figure