Pirouette: Query Efficient Single-Server PIR
Authors: Jiayi Kang (COSIC, KU Leuven), Leonard Schild (COSIC, KU Leuven)
Volume: 2026
Issue: 2
Pages: 215–241
DOI: https://doi.org/10.56553/popets-2026-0045
Abstract: Private information retrieval (PIR) allows a client to query a public database privately and serves as a key building block for privacy-enhancing applications. Minimizing query size is particularly important in many use cases, for example, when clients operate on bandwidth-constrained devices. However, existing PIR protocols exhibit large query sizes: to query 225 records, the smallest query size of 14.8 KB is reported in Respire [Burton et al., CCS24]. Respire is based on fully homomorphic encryption (FHE), where a common approach to lower the client-to-server communication cost is transciphering. When combining the state-of-the-art transciphering [Bon et al., CHES24] with Respire, the resulting protocol (which we refer to as T-Respire) has a 336 B query size, while incurring a 16.2x times higher server computation cost than Respire. Our work introduces a novel alternative to transciphering for reducing the client-to-server communication: the client transmits only one component of a high-precision LWE ciphertext, from which we design a modular procedure to extract the inputs for the subsequent homomorphic computation. The efficiency of this approach is demonstrated by our Pirouette protocol, which achieves a query size of just 36 B. This represents a 9.3x reduction compared to T-Respire and a 420x reduction to Respire. For queries over 225 records, the single-core server computation in Pirouette is only 2x slower than Respire and 8.1x faster than T-Respire, and the server computation is highly parallelizable. Furthermore, Pirouette requires no database-specific hint for clients, and its variant PirouetteH enables additional tradeoffs among query size, throughput, and offline communication, demonstrating the flexibility of our design
Keywords: Fully Homomorphic Encryption, Private Information Retrieval
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
