{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T16:56:21Z","timestamp":1770310581046,"version":"3.49.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T00:00:00Z","timestamp":1770249600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T00:00:00Z","timestamp":1770249600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["No.12441101"],"award-info":[{"award-number":["No.12441101"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecurity"],"abstract":"Abstract<\/jats:title>\n \n 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\n \n \n $$\\textsf{GCTObvDecomperss}$$<\/jats:tex-math>\n \n GCTObvDecomperss<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n 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\n \n \n $$\\times$$<\/jats:tex-math>\n \n \u00d7<\/mml:mo>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n 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\n \n \n $$\\times$$<\/jats:tex-math>\n \n \u00d7<\/mml:mo>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n speedup in the first-dimensional processing phase compared to serial execution, and reducing the total computation cost by 3.9\n \n \n $$\\times$$<\/jats:tex-math>\n \n \u00d7<\/mml:mo>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . 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\n \n \n $$2^{18}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n 18<\/mml:mn>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n compared to the original protocol, indicating that our construction can provide a more effective and practical method in related scenarios.\n <\/jats:p>","DOI":"10.1186\/s42400-025-00418-w","type":"journal-article","created":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T02:02:46Z","timestamp":1770256966000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["GPU-accelerated Batch Private Information Retrieval with lower communication overheads"],"prefix":"10.1186","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8992-651X","authenticated-orcid":false,"given":"Ying","family":"Gao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bowen","family":"Zheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,5]]},"reference":[{"key":"418_CR1","first-page":"551","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)","author":"S Angel","year":"2016","unstructured":"Angel S, Setty S (2016) Unobservable communication over fully untrusted infrastructure. 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). USENIX Association, Savannah, GA, pp 551\u2013569"},{"key":"418_CR2","doi-asserted-by":"publisher","unstructured":"Angel S, Chen H, Laine K, et\u00a0al (2018) Pir with compressed queries and amortized query processing. In: 2018 IEEE Symposium on Security and Privacy (SP), pp 962\u2013979, https:\/\/doi.org\/10.1109\/SP.2018.00062","DOI":"10.1109\/SP.2018.00062"},{"key":"418_CR3","doi-asserted-by":"publisher","unstructured":"Arbitman Y, Naor M, Segev G (2010) Backyard cuckoo hashing: Constant worst-case operations with a succinct representation. In: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp 787\u2013796, https:\/\/doi.org\/10.1109\/FOCS.2010.80","DOI":"10.1109\/FOCS.2010.80"},{"key":"418_CR4","unstructured":"Bienstock A, Patel S, Seo YJ, et\u00a0al (2024) Batch PIR and labeled PSI with oblivious ciphertext compression. In: Balzarotti D, Xu W (eds) Proceedings of the 33rd USENIX Conference on Security Symposium. USENIX Association, Philadelphia, PA, USA"},{"key":"418_CR5","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1515\/popets-2015-0008","volume":"2015","author":"N Borisov","year":"2015","unstructured":"Borisov N, Danezis G, Goldberg I (2015) Dp5: a private presence service. Proceed Privacy Enhan Technol 2015:4\u201324. https:\/\/doi.org\/10.1515\/popets-2015-0008","journal-title":"Proceed Privacy Enhan Technol"},{"issue":"1","key":"418_CR6","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.is.2012.06.002","volume":"38","author":"FC Botelho","year":"2013","unstructured":"Botelho FC, Pagh R, Ziviani N (2013) Practical perfect hashing in nearly optimal space. Inf Syst 38(1):108\u2013131. https:\/\/doi.org\/10.1016\/j.is.2012.06.002","journal-title":"Inf Syst"},{"key":"418_CR7","doi-asserted-by":"publisher","unstructured":"Brakerski Z, Vaikuntanathan V (2011) Fully homomorphic encryption from ring-lwe and security for key dependent messages. In: Proceedings of the 31st Annual Conference on Advances in Cryptology. Springer-Verlag, Berlin, Heidelberg, p 505\u2013524, https:\/\/doi.org\/10.1007\/978-3-642-22792-9_29","DOI":"10.1007\/978-3-642-22792-9_29"},{"key":"418_CR8","doi-asserted-by":"crossref","unstructured":"Cachin C, Micali S, Stadler M (1999) Computationally private information retrieval with polylogarithmic communication. In: Proceedings of the 17th International Conference on Theory and Application of Cryptographic Techniques. Springer-Verlag, Berlin, Heidelberg, pp 402\u2013414","DOI":"10.1007\/3-540-48910-X_28"},{"key":"418_CR9","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-540-27800-9_5","volume-title":"Information Security and Privacy","author":"YC Chang","year":"2004","unstructured":"Chang YC (2004) Single database private information retrieval with logarithmic communication. In: Wang HX, Josef P, Vijay V (eds) Information Security and Privacy. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 50\u201361. https:\/\/doi.org\/10.1007\/978-3-540-27800-9_5"},{"key":"418_CR10","doi-asserted-by":"publisher","unstructured":"Cheng R, Scott W, Masserova E et\u00a0al (2020) Talek: Private group messaging with hidden access patterns. In: Proceedings of the 36th Annual Computer Security Applications Conference. Association for Computing Machinery, New York, NY, USA, pp 84\u201399, https:\/\/doi.org\/10.1145\/3427228.3427231","DOI":"10.1145\/3427228.3427231"},{"key":"418_CR11","doi-asserted-by":"publisher","unstructured":"Chor B, Gilboa N (1997) Computationally private information retrieval. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, New York, NY, USA, pp 304\u2013313, https:\/\/doi.org\/10.1145\/258533.258609","DOI":"10.1145\/258533.258609"},{"key":"418_CR12","doi-asserted-by":"publisher","unstructured":"Chor B, Kushilevitz E, Goldreich O et\u00a0al (1995) Private information retrieval. Proceedings of IEEE 36th Annual Foundations of Computer Science pp 41\u201350. https:\/\/doi.org\/10.1109\/SFCS.1995.492461","DOI":"10.1109\/SFCS.1995.492461"},{"key":"418_CR13","doi-asserted-by":"publisher","unstructured":"Dai W, Dor\u00f6z Y, Sunar B (2015) Accelerating swhe based pirs using gpus. In: IACR Cryptology ePrint Archive, https:\/\/doi.org\/10.1007\/978-3-662-48051-9_12","DOI":"10.1007\/978-3-662-48051-9_12"},{"key":"418_CR14","doi-asserted-by":"publisher","unstructured":"Dong C, Chen L (2014) A fast single server private information retrieval protocol with low communication cost. In: Computer Security - ESORICS 2014. Springer-Verlag, Berlin, Heidelberg, p 380\u2013399, https:\/\/doi.org\/10.1007\/978-3-319-11203-9_22","DOI":"10.1007\/978-3-319-11203-9_22"},{"key":"418_CR15","doi-asserted-by":"publisher","unstructured":"Garimella G, Pinkas B, Rosulek M et\u00a0al (2021) Oblivious key-value stores and amplification for private set intersection. In: Advances in Cryptology \u2013 CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16\u201320, 2021, Proceedings, Part II. Springer-Verlag, Berlin, Heidelberg, pp 395\u2013425, https:\/\/doi.org\/10.1007\/978-3-030-84245-1_14","DOI":"10.1007\/978-3-030-84245-1_14"},{"key":"418_CR16","doi-asserted-by":"publisher","unstructured":"Gentry C, Sahai A, Waters B (2013) Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti R, Garay JA (eds) Advances in Cryptology \u2013 CRYPTO 2013. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 75\u201392, https:\/\/doi.org\/10.1007\/978-3-642-40041-4_5","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"418_CR17","doi-asserted-by":"publisher","unstructured":"Green M, Ladd W, Miers I (2016) A protocol for privately reporting ad impressions at scale. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, New York, NY, USA, pp 1591\u20131601, https:\/\/doi.org\/10.1145\/2976749.2978407","DOI":"10.1145\/2976749.2978407"},{"key":"418_CR18","first-page":"1759","volume-title":"31st USENIX Security Symposium (USENIX Security 22)","author":"D G\u00fcnther","year":"2022","unstructured":"G\u00fcnther D, Heymann M, Pinkas B et al (2022) Gpu-accelerated pir with client-independent preprocessing for large-scale applications. 31st USENIX Security Symposium (USENIX Security 22). USENIX Association, Boston, MA, pp 1759\u20131776"},{"key":"418_CR19","unstructured":"Gupta T, Crooks N, Mulhern W et\u00a0al (2016) Scalable and private media consumption with popcorn. In: Proceedings of the 13th Usenix Conference on Networked Systems Design and Implementation. USENIX Association, USA, pp 91\u2013107"},{"key":"418_CR20","doi-asserted-by":"publisher","unstructured":"Hsu HC, Liu ZY, Tso R et\u00a0al (2020) Multi-value private information retrieval using homomorphic encryption. In: 2020 15th Asia Joint Conference on Information Security (AsiaJCIS), pp 82\u201388, https:\/\/doi.org\/10.1109\/AsiaJCIS50894.2020.00024","DOI":"10.1109\/AsiaJCIS50894.2020.00024"},{"key":"418_CR21","doi-asserted-by":"publisher","unstructured":"Ishai Y, Kushilevitz E, Ostrovsky R et\u00a0al (2004) Batch codes and their applications. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, New York, NY, USA, p 262\u2013271, https:\/\/doi.org\/10.1145\/1007352.1007396","DOI":"10.1145\/1007352.1007396"},{"key":"418_CR22","doi-asserted-by":"publisher","unstructured":"Kushilevitz E, Ostrovsky R (1997) Replication is not needed: Single database, computationally private information retrieval. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, USA, p 364, https:\/\/doi.org\/10.1109\/SFCS.1997.646125","DOI":"10.1109\/SFCS.1997.646125"},{"key":"418_CR23","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1515\/popets-2016-0008","volume":"2016","author":"A Kwon","year":"2016","unstructured":"Kwon A, Lazar D, Devadas S et al (2016) Riffle: an efficient communication system with strong anonymity. Proceed Privacy Enhan Technol 2016:115\u2013134. https:\/\/doi.org\/10.1515\/popets-2016-0008","journal-title":"Proceed Privacy Enhan Technol"},{"key":"418_CR24","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/978-3-662-47854-7_10","volume-title":"Financial Cryptography and Data Security","author":"W Lueks","year":"2015","unstructured":"Lueks W, Goldberg I (2015) Sublinear scaling for multi-client private information retrieval. In: Rainer B, Tatsuaki O (eds) Financial Cryptography and Data Security. Springer, Berlin Heidelberg, pp 168\u2013186. https:\/\/doi.org\/10.1007\/978-3-662-47854-7_10"},{"key":"418_CR25","doi-asserted-by":"publisher","unstructured":"Maruseac M, Ghinita G, Ouyang M et\u00a0al (2015) Hardware acceleration of private information retrieval protocols using gpus. In: 2015 IEEE 26th International Conference on Application-specific Systems, Architectures and Processors (ASAP), pp 120\u2013127, https:\/\/doi.org\/10.1109\/ASAP.2015.7245719","DOI":"10.1109\/ASAP.2015.7245719"},{"key":"418_CR26","first-page":"155","volume":"2016","author":"CA Melchor","year":"2016","unstructured":"Melchor CA, Barrier J, Fousse L et al (2016) Xpir: private information retrieval for everyone. Proceed Privacy Enhan Technol 2016:155\u2013174","journal-title":"Proceed Privacy Enhan Technol"},{"key":"418_CR27","doi-asserted-by":"crossref","unstructured":"Menon SJ, Wu DJ (2022) Spiral: Fast, high-rate single-server pir via fhe composition. Cryptology ePrint Archive, Paper 2022\/368","DOI":"10.1109\/SP46214.2022.9833700"},{"key":"418_CR28","unstructured":"Mittal P, Olumofin F, Troncoso C et\u00a0al (2011) Pir-tor: Scalable anonymous communication using private information retrieval. In: 20th USENIX Security Symposium (USENIX Security 11). USENIX Association, San Francisco, CA"},{"key":"418_CR29","unstructured":"Molloy M (2004) The pure literal rule threshold and cores in random hypergraphs. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, USA, SODA \u201904, pp 672\u2013681"},{"key":"418_CR30","doi-asserted-by":"publisher","unstructured":"Mughees MH, Ren L (2023) Vectorized batch private information retrieval. 2023 IEEE Symposium on Security and Privacy (SP) pp 437\u2013452. https:\/\/doi.org\/10.1109\/SP46215.2023.10179329","DOI":"10.1109\/SP46215.2023.10179329"},{"key":"418_CR31","unstructured":"NVIDIA Corporation. (2017) NVIDIA CUDA C++ programming guide. http:\/\/docs.nvidia.com\/cuda\/cuda-c-programming-guide. Accessed 20 March 2017"},{"issue":"2","key":"418_CR32","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R Pagh","year":"2004","unstructured":"Pagh R, Rodler FF (2004) Cuckoo hashing. J Algorithms 51(2):122\u2013144. https:\/\/doi.org\/10.1016\/j.jalgor.2003.12.002","journal-title":"J Algorithms"},{"key":"418_CR33","unstructured":"Paterson MB, Stinson DR, Wei R (2008) Combinatorial batch codes. Cryptology ePrint Archive, Paper 2008\/306"},{"issue":"6","key":"418_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1568318.1568324","volume":"56","author":"O Regev","year":"2009","unstructured":"Regev O (2009) On lattices, learning with errors, random linear codes, and cryptography. J ACM 56(6):1\u201340. https:\/\/doi.org\/10.1145\/1568318.1568324","journal-title":"J ACM"},{"key":"418_CR35","doi-asserted-by":"publisher","unstructured":"Ren L, Mughees MH, Sun I (2024) Simple and practical amortized sublinear private information retrieval using dummy subsets. In: Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, New York, NY, USA, pp 1420\u20131433, https:\/\/doi.org\/10.1145\/3658644.3690266","DOI":"10.1145\/3658644.3690266"},{"key":"418_CR36","unstructured":"Statista (2025) Median mobile and fixed broadband download and upload speeds worldwide as of March 2025. https:\/\/www.statista.com\/statistics\/896779\/average-mobile-fixed-broadband-download-upload-speeds\/. Accessed 21 March 2025"},{"key":"418_CR37","doi-asserted-by":"publisher","unstructured":"Zhou M, Park A, Zheng W et\u00a0al (2024) Piano: Extremely simple, single-server pir with sublinear server computation. In: 2024 IEEE Symposium on Security and Privacy (SP), pp 4296\u20134314, https:\/\/doi.org\/10.1109\/SP54263.2024.00055","DOI":"10.1109\/SP54263.2024.00055"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-025-00418-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-025-00418-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-025-00418-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T02:02:50Z","timestamp":1770256970000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/s42400-025-00418-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,5]]},"references-count":37,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,12]]}},"alternative-id":["418"],"URL":"https:\/\/doi.org\/10.1186\/s42400-025-00418-w","relation":{},"ISSN":["2523-3246"],"issn-type":[{"value":"2523-3246","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,5]]},"assertion":[{"value":"13 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This article does not contain any studies with human participants or animals performed by any authors.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"The authors declare that they do not have any competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"25"}}