GPIR: Efficient Single‐Server Private Information Retrieval With Garbled Bloom Filters

Abstract

Private Information Retrieval (PIR) enables a client to retrieve a target record from a server‐held database without revealing the queried index. Existing single‐server PIR schemes still face difficulty in achieving both query privacy and practical efficiency, due to large query size, large storage overhead, or high server‐side computation. To address these limitations, this article proposes GPIR, an efficient PIR scheme based on Garbled Bloom Filters (GBFs) and BFV homomorphic encryption, together with a query‐compressed row‐revealing variant, wGPIR. In GPIR, the server arranges the database into a square matrix and encodes each row as an additive GBF. The client generates a row‐masked sparse query vector according to the target index and encrypts it before sending. The server then homomorphically evaluates the query over all row‐wise GBFs and returns one encrypted response per row. To further improve efficiency, the variant wGPIR explicitly reveals the target row and compresses the query into three ciphertexts corresponding to the three GBF positions, which are expanded by the server to form the encrypted query vector. Security analysis shows that GPIR protects the queried index, target row, and GBF positions, while wGPIR provides intra‐row query privacy under the IND‐CPA security of BFV. Experiments on a database with 220$$ {2}^{20} $$ records show that GPIR achieves 1.53 ×$$ \times $$ improvement in computation over APIR, and wGPIR further achieves 1180 ×$$ \times $$ , 768.20 ×$$ \times $$ improvements in communication over APIR and GPIR, respectively, along with 4.09 ×$$ \times $$ and 49.5 ×$$ \times $$ improvements in computation over APIR and GPIR, respectively, demonstrating its practicality for efficient private retrieval.