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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>GCTObvDecomperss</mml:mi> </mml:math> 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 computationally oblivious. In the implementation, our scheme reduces the additional communication cost in Batch PIR by 27% while achieving a 7.9 $$\times$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>×</mml:mo> </mml:math> improvement in efficiency compared to existing solutions. Moreover, to enhance computational performance, we analyze the computational bottleneck of Spiral PIR and optimize it using GPU technology, achieving a 267 $$\times$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>×</mml:mo> </mml:math> speedup in the first-dimensional processing phase compared to serial execution, and reducing the total computation cost by 3.9 $$\times$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>×</mml:mo> </mml:math> . Furthermore, we conduct comprehensive evaluations of our Batch PIR protocol, demonstrating its superior performance in both computational efficiency and communication overhead, as well as its capability to support efficient retrieval in databases of large entries. Finally, we use our Batch PIR in an anonymous messaging protocol Pung, and evaluate the performance of this real-world application. By using our Batch PIR, the latency can be reduced by 18.8% when the number of records reached $$2^{18}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>18</mml:mn> </mml:msup> </mml:math> compared to the original protocol, indicating that our construction can provide a more effective and practical method in related scenarios.