GPU-accelerated Batch Private Information Retrieval with lower communication overheads

Abstract Private Information Retrieval (PIR) is a critical component in many privacy-preserving systems, and Batch PIR schemes constructed by Probabilistic Batch Code have garnered widespread attention in both academia and industry due to their relatively low average computational cost. However, existing Batch PIR still face challenges in balancing computational and communication efficiency, while some also exhibit poor adaptability to databases of large entries. In this paper, building upon the state-of-the-art Batch PIR schemes, we employ two approaches to enhance their overall performance. To reduce the communication cost of Batch PIR, we propose a novel Oblivious Ciphertext Decompression scheme $$\textsf{GCTObvDecomperss}$$ GCTObvDecomperss based on the 3-Hash Garbled Cuckoo Table algorithm. We use the hypergraph peeling algorithm to construct this scheme and give a formal security definition and proof of this scheme to ensure it is co