{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T13:51:29Z","timestamp":1767793889306,"version":"3.49.0"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T00:00:00Z","timestamp":1767744000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T00:00:00Z","timestamp":1767744000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecurity"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Fully homomorphic encryption (FHE) enables arbitrary computations on encrypted data while preserving strong privacy guarantees. However, the high computational cost of homomorphic operations, particularly multiplication and comparisons, remains a significant bottleneck in practical applications. In this paper, we propose a novel algorithm that efficiently evaluates univariate polynomial functions under FHE, leveraging specific optimization techniques to minimize the number of required homomorphic operations. We rigorously analyze its theoretical performance and extend it to implement an optimized equality test. Our experimental results show that comparing two 32-bit values takes only 3.9 milliseconds, and for batch comparisons between 32,768 16-bit values and a single 16-bit value, the amortized overhead is reduced to 0.01 milliseconds per comparison. Furthermore, we apply this equality test to build a practical single-round keyword private information retrieval (PIR) protocol for the single-server setting. Compared to the Constant-Weight PIR (USENIX 2022), our method achieves a 4\u20136\u00d7 reduction in computational overhead during the server\u2019s response phase, making it a more practical solution for real-world deployments.<\/jats:p>","DOI":"10.1186\/s42400-025-00506-x","type":"journal-article","created":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T10:48:22Z","timestamp":1767782902000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["HET-PIR: practical Keyword PIR via a Novel homomorphic equality test Algorithm"],"prefix":"10.1186","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-1977-4828","authenticated-orcid":false,"given":"Peizhe","family":"Song","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingsheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,7]]},"reference":[{"issue":"4","key":"506_CR1","doi-asserted-by":"publisher","first-page":"643","DOI":"10.14778\/3574245.3574251","volume":"16","author":"I Ahmad","year":"2022","unstructured":"Ahmad I, Agrawal D, Abbadi AE, Gupta T (2022) Pantheon: private retrieval from public key-value store. Proc VLDB Endow 16(4):643\u2013656. https:\/\/doi.org\/10.14778\/3574245.3574251","journal-title":"Proc VLDB Endow"},{"key":"506_CR2","unstructured":"Ahmad I, Yang Y, Agrawal D, El\u00a0Abbadi A, Gupta T (2021) Addra: Metadata-private voice communication over fully untrusted infrastructure. In: 15th $$\\{$$USENIX$$\\}$$ symposium on operating systems design and implementation ($$\\{$$OSDI$$\\}$$ 21)"},{"key":"506_CR3","doi-asserted-by":"publisher","first-page":"80","DOI":"10.13154\/tches.v2019.i2.80-106","volume":"2","author":"A Akavia","year":"2019","unstructured":"Akavia A, Feldman D, Shaul H (2019) Secure data retrieval on the cloud: Homomorphic encryption meets coresets. IACR Trans Cryptogr Hardw Embed Syst 2:80\u2013106. https:\/\/doi.org\/10.13154\/tches.v2019.i2.80-106","journal-title":"IACR Trans Cryptogr Hardw Embed Syst"},{"key":"506_CR4","doi-asserted-by":"publisher","first-page":"87","DOI":"10.2478\/popets-2019-0033","volume":"3","author":"A Akavia","year":"2019","unstructured":"Akavia A, Gentry C, Halevi S, Leibovich M (2019) Setup-free secure search on encrypted data: Faster and post-processing free. Proc Privacy Enhanc Technol 3:87\u2013107. https:\/\/doi.org\/10.2478\/popets-2019-0033","journal-title":"Proc Privacy Enhanc Technol"},{"key":"506_CR5","doi-asserted-by":"crossref","unstructured":"Akavia A, Gentry C, Halevi S, Leibovich M (2018) Setup-free secure search on encrypted data: Faster and post-processing free. Cryptology ePrint Archive","DOI":"10.2478\/popets-2019-0038"},{"key":"506_CR6","unstructured":"Albrecht M, Chase M, Chen H, Ding J, Goldwasser S, Gorbunov S, Halevi S, Hoffstein J, Laine K, Lauter K, Lokam S, Micciancio D, Moody D, Morrison T, Sahai A, Vaikuntanathan V (2018) Homomorphic encryption security standard. Technical report, HomomorphicEncryption.org, Toronto, Canada"},{"key":"506_CR7","unstructured":"Ali A, Lepoint T, Patel S, Raykova M, Schoppmann P, Seth K, Yeo K (2021) Communication\u2013Computation trade-offs in PIR. Paper presented at the 30th USENIX security symposium (USENIX Security 21), pp 1811\u20131828"},{"key":"506_CR8","doi-asserted-by":"crossref","unstructured":"Ambainis A (1997) Upper bound on the communication complexity of private information retrieval. Paper presented at the international colloquium on automata, languages, and programming, Springer, pp 401\u2013407","DOI":"10.1007\/3-540-63165-8_196"},{"key":"506_CR9","doi-asserted-by":"crossref","unstructured":"Angel S, Chen H, Laine K, Setty S (2018) PIR with compressed queries and amortized query processing. Paper presented at the IEEE symposium on security and privacy (SP), pp 962\u2013979","DOI":"10.1109\/SP.2018.00062"},{"key":"506_CR10","doi-asserted-by":"crossref","unstructured":"Applebaum B, Cash D, Peikert C, Sahai A (2009) Fast cryptographic primitives and circular-secure encryption based on hard learning problems. Paper presented at the 29th annual international cryptology conference (CRYPTO 2009), Santa Barbara, CA, USA, Springer, pp 595\u2013618","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"506_CR11","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/s00037-006-0208-3","volume":"15","author":"R Beigel","year":"2006","unstructured":"Beigel R, Fortnow L, Gasarch W (2006) A tight lower bound for restricted pir protocols. Comput Complex 15:82\u201391","journal-title":"Comput Complex"},{"key":"506_CR12","doi-asserted-by":"crossref","unstructured":"Beimel A, Ishai Y (2001) Information-theoretic private information retrieval: a unified construction. Paper presented at the 28th international colloquium on automata, languages and programming, ICALP 2001, Crete, Greece, pp 912\u2013926, Springer","DOI":"10.1007\/3-540-48224-5_74"},{"key":"506_CR13","doi-asserted-by":"crossref","unstructured":"Beimel A, Ishai Y, Kushilevitz E, Orlov I (2012) Share conversion and private information retrieval. Paper presented at the 27th IEEE conference on computational complexity, IEEE, pp 258\u2013268","DOI":"10.1109\/CCC.2012.23"},{"key":"506_CR14","doi-asserted-by":"crossref","unstructured":"Bonte C, Iliashenko I (2020) Homomorphic string search with constant multiplicative depth. Paper presented at the 2020 ACM SIGSAC conference on cloud computing security workshop, pp 105\u2013117","DOI":"10.1145\/3411495.3421361"},{"issue":"3","key":"506_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2633600","volume":"6","author":"Z Brakerski","year":"2014","unstructured":"Brakerski Z, Gentry C, Vaikuntanathan V (2014) (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans Comput Theory 6(3):1\u201336","journal-title":"ACM Trans Comput Theory"},{"key":"506_CR16","doi-asserted-by":"crossref","unstructured":"Brakerski Z, Vaikuntanathan V (2011) Fully homomorphic encryption from ring-LWE and security for key dependent messages. Paper presented at the annual cryptology conference, pp 505\u2013524","DOI":"10.1007\/978-3-642-22792-9_29"},{"key":"506_CR17","doi-asserted-by":"publisher","unstructured":"Celi S, Davidson A (2024) Call me by my name: Simple, practical private information retrieval for keyword queries. In: Proceedings of the 2024 on ACM SIGSAC conference on computer and communications security. CCS\u201924, Association for Computing Machinery, New York, NY, USA, pp 4107\u20134121 https:\/\/doi.org\/10.1145\/3658644.3670271","DOI":"10.1145\/3658644.3670271"},{"key":"506_CR18","doi-asserted-by":"crossref","unstructured":"Chang Y-C (2004) Single database private information retrieval with logarithmic communication. Paper presented at the 9th Australasian conference on information security and privacy (ACISP 2004), Sydney, Australia, Springer, pp 50\u201361","DOI":"10.1007\/978-3-540-27800-9_5"},{"issue":"6","key":"506_CR19","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B Chor","year":"1998","unstructured":"Chor B, Kushilevitz E, Goldreich O, Sudan M (1998) Private information retrieval. JACM 45(6):965\u2013981","journal-title":"JACM"},{"key":"506_CR20","unstructured":"Chor B, Gilboa N, Naor M (1998) Private Information Retrieval by Keywords. Cryptology ePrint Archive, Report 1998\/003. https:\/\/eprint.iacr.org\/1998\/003"},{"key":"506_CR21","doi-asserted-by":"crossref","unstructured":"Corrigan-Gibbs H, Kogan D (2020) Private information retrieval with sublinear online time. Paper presented at the 39th annual international conference on the theory and applications of cryptographic techniques (EUROCRYPT 2020), Zagreb, Croatia, Springer, pp 44\u201375","DOI":"10.1007\/978-3-030-45721-1_3"},{"key":"506_CR22","doi-asserted-by":"crossref","unstructured":"Corrigan-Gibbs H, Henzinger A, Kogan D (2022) Single-server private information retrieval with sublinear amortized time. Paper presented at the annual international conference on the theory and applications of cryptographic techniques, Springer, pp 3\u201333","DOI":"10.1007\/978-3-031-07085-3_1"},{"key":"506_CR23","doi-asserted-by":"publisher","DOI":"10.56553\/popets-2023-0022","author":"A Davidson","year":"2023","unstructured":"Davidson A, Pestana G, Celi S (2023) Frodopir: simple, scalable, single-server private information retrieval. Proc Privacy Enhanc Technol. https:\/\/doi.org\/10.56553\/popets-2023-0022","journal-title":"Proc Privacy Enhanc Technol"},{"key":"506_CR24","doi-asserted-by":"publisher","unstructured":"Fan J, Vercauteren F (2012) Somewhat Practical fully homomorphic encryption. Paper presented at the 15th international conference on practice and theory in public key cryptography, Springer, Berlin, pp 1\u201316 https:\/\/doi.org\/10.1007\/978-3-642-30057-8_1","DOI":"10.1007\/978-3-642-30057-8_1"},{"key":"506_CR25","doi-asserted-by":"crossref","unstructured":"Freedman MJ, Ishai Y, Pinkas B, Reingold O (2005) Keyword search and oblivious pseudorandom functions. Paper presented at the second theory of cryptography conference (TCC 2005). MA, USA, Springer, Cambridge, pp 303\u2013324","DOI":"10.1007\/978-3-540-30576-7_17"},{"key":"506_CR26","doi-asserted-by":"crossref","unstructured":"Gentry C, Halevi S, Smart NP (2012) Homomorphic evaluation of the AES circuit. Paper presented at the annual cryptology conference, Springer, pp 850\u2013867","DOI":"10.1007\/978-3-642-32009-5_49"},{"key":"506_CR27","unstructured":"Halevi S, Shoup V (2020) Design and implementation of helib: a homomorphic encryption library. Cryptology ePrint Archive"},{"key":"506_CR28","unstructured":"Henzinger A, Hong MM, Corrigan-Gibbs H, Meiklejohn S, Vaikuntanathan V (2023) One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval. Paper presented at the 32nd USENIX security symposium (USENIX Security 23), pp 3889\u20133905"},{"key":"506_CR29","doi-asserted-by":"crossref","unstructured":"Ishai Y, Su H, Wu DJ (2021) Shorter and faster post-quantum designated-verifier zkSNARKs from lattices. Paper presented at the 2021 ACM SIGSAC conference on computer and communications security, pp 212\u2013234","DOI":"10.1145\/3460120.3484572"},{"key":"506_CR30","doi-asserted-by":"crossref","unstructured":"Kacsmar B, Khurram B, Lukas N, Norton A, Shafieinejad M, Shang Z, Baseri Y, Sepehri M, Oya S, Kerschbaum F (2020) Differentially private two-party set operations. Paper presented at the 2020 IEEE European symposium on security and privacy (EuroS &P), pp 390\u2013404","DOI":"10.1109\/EuroSP48549.2020.00032"},{"key":"506_CR31","doi-asserted-by":"crossref","unstructured":"Kacsmar B, Khurram B, Lukas N, Norton A, Shafieinejad M, Shang Z, Baseri Y, Sepehri M, Oya S, Kerschbaum F (2020) Differentially private two-party set operations. Paper presented at the 2020 IEEE European symposium on security and privacy (EuroS &P), IEEE, pp 390\u2013404","DOI":"10.1109\/EuroSP48549.2020.00032"},{"issue":"6","key":"506_CR32","doi-asserted-by":"publisher","first-page":"1767","DOI":"10.1137\/08073408X","volume":"40","author":"KS Kedlaya","year":"2011","unstructured":"Kedlaya KS, Umans C (2011) Fast polynomial factorization and modular composition. SIAM J Comput 40(6):1767\u20131802","journal-title":"SIAM J Comput"},{"key":"506_CR33","doi-asserted-by":"crossref","unstructured":"Kim A, Polyakov Y, Zucca V (2021) Revisiting homomorphic encryption schemes for finite fields. Paper presented at the 27th international conference on the theory and application of cryptology and information security (ASIACRYPT 2021), Singapore, pp 608\u2013639","DOI":"10.1007\/978-3-030-92078-4_21"},{"key":"506_CR34","doi-asserted-by":"crossref","unstructured":"Kushilevitz E, Ostrovsky R (1997) Replication is not needed: Single database, computationally-private information retrieval. Paper presented at the 38th annual symposium on foundations of computer science, IEEE, pp364\u2013373","DOI":"10.1109\/SFCS.1997.646125"},{"key":"506_CR35","doi-asserted-by":"crossref","unstructured":"Li B, Micciancio D, Raykova M, Schultz-Wu M (2024) Hintless single-server private information retrieval. Paper presented at the annual international cryptology conference, Springer, pp 183\u2013217","DOI":"10.1007\/978-3-031-68400-5_6"},{"key":"506_CR36","doi-asserted-by":"crossref","unstructured":"Lin W-K, Mook E, Wichs D (2023) Doubly efficient private information retrieval and fully homomorphic RAM computation from ring LWE. Paper presented at the 55th annual ACM symposium on theory of computing, pp 595\u2013608","DOI":"10.1145\/3564246.3585175"},{"key":"506_CR37","doi-asserted-by":"crossref","unstructured":"Liu J, Li J, Wu D, Ren K (2024) Pirana: Faster multi-query pir via constant-weight codes. In: 2024 IEEE symposium on security and privacy (SP), IEEE, pp 4315\u20134330","DOI":"10.1109\/SP54263.2024.00039"},{"issue":"1","key":"506_CR38","doi-asserted-by":"publisher","DOI":"10.3390\/cryptography9010013","volume":"9","author":"M Luo","year":"2025","unstructured":"Luo M, Wang M (2025) Faster spiral: low-communication, high-rate private information retrieval. Cryptography 9(1):13","journal-title":"Cryptography"},{"key":"506_CR39","doi-asserted-by":"crossref","unstructured":"Lyubashevsky V, Peikert C, Regev O (2010) On ideal lattices and learning with errors over rings. Paper presented at the 29th annual international conference on the theory and applications of cryptographic techniques (EUROCRYPT 2010), French Riviera, Springer, pp 1\u201323","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"506_CR40","unstructured":"Mahdavi RA, Kerschbaum F (2022) Constant-weight PIR: Single-round keyword PIR via constant-weight equality operators. Paper presented at the 31st USENIX security symposium (USENIX Security 22), pp 1723\u20131740"},{"key":"506_CR41","doi-asserted-by":"crossref","unstructured":"Melchor CA, Barrier J, Fousse L, Killijian M-O (2016) Xpir: Private information retrieval for everyone. In: Proceedings on privacy enhancing technologies, pp 155\u2013174","DOI":"10.1515\/popets-2016-0010"},{"key":"506_CR42","doi-asserted-by":"crossref","unstructured":"Menon SJ, Wu DJ (2022) Spiral: Fast, high-rate single-server PIR via FHE composition. Paper presented at the 2022 IEEE symposium on security and privacy (SP), IEEE, pp 930\u2013947","DOI":"10.1109\/SP46214.2022.9833700"},{"key":"506_CR43","doi-asserted-by":"crossref","unstructured":"Mono J, Marcolla C, Land G, G\u00fcneysu T, Aaraj N (2023) Finding and evaluating parameters for BGV. Paper presented at the international conference on cryptology in Africa, pp 370\u2013394","DOI":"10.1007\/978-3-031-37679-5_16"},{"key":"506_CR44","doi-asserted-by":"crossref","unstructured":"Mughees MH, Chen H, Ren L (2021) OnionPIR: response efficient single-server PIR. Paper presented at the 2021 ACM SIGSAC conference on computer and communications security, pp 2292\u20132306","DOI":"10.1145\/3460120.3485381"},{"key":"506_CR45","doi-asserted-by":"crossref","unstructured":"Okada H, Player R, Pohmann S, Weinert C (2025) Towards practical doubly-efficient private information retrieval. In: Clark J, Shi E (eds) Financial cryptography and data security. Springer, Cham, pp 264\u2013282","DOI":"10.1007\/978-3-031-78679-2_14"},{"key":"506_CR46","doi-asserted-by":"crossref","unstructured":"Park J, Tibouchi M (2020) SHECS-PIR: somewhat homomorphic encryption-based compact and scalable private information retrieval. Paper presented at the European symposium on research in computer security, Springer, pp 86\u2013106","DOI":"10.1007\/978-3-030-59013-0_5"},{"key":"506_CR47","unstructured":"Patel S, Seo JY, Yeo K (2023) Don\u2019t be Dense: Efficient Keyword PIR for Sparse Databases. Paper presented at the 32nd USENIX security symposium (USENIX Security 23), pp 3853\u20133870"},{"key":"506_CR48","doi-asserted-by":"crossref","unstructured":"Shi E, Aqeel W, Chandrasekaran B, Maggs B (2021) Puncturable pseudorandom sets and private information retrieval with near-optimal online bandwidth and time. Paper presented at the 41st annual international cryptology conference (CRYPTO 2021), Virtual Event, Springer, Berlin, pp 641\u2013669","DOI":"10.1007\/978-3-030-84259-8_22"},{"key":"506_CR49","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10623-012-9720-4","volume":"71","author":"NP Smart","year":"2014","unstructured":"Smart NP, Vercauteren F (2014) Fully homomorphic simd operations. Des Codes Cryptogr 71:57\u201381","journal-title":"Des Codes Cryptogr"},{"key":"506_CR50","doi-asserted-by":"crossref","unstructured":"Van\u00a0Dijk M, Gentry C, Halevi S, Vaikuntanathan V (2010) Fully homomorphic encryption over the integers. Paper presented at the 29th annual international conference on the theory and applications of cryptographic techniques, French Riviera, Springer, pp 24\u201343","DOI":"10.1007\/978-3-642-13190-5_2"},{"key":"506_CR51","doi-asserted-by":"crossref","unstructured":"Yasuda M, Shimoyama T, Kogure J, Yokoyama K, Koshiba T (2013) Secure pattern matching using somewhat homomorphic encryption. Paper presented at the 2013 ACM workshop on cloud computing security workshop, pp 65\u201376","DOI":"10.1145\/2517488.2517497"},{"key":"506_CR52","doi-asserted-by":"crossref","unstructured":"Zhou M, Park A, Zheng W, Shi E (2024) Piano: extremely simple, single-server PIR with sublinear server computation. Paper presented at the 2024 IEEE symposium on security and privacy (SP), IEEE, pp 4296\u20134314","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-00506-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-025-00506-x","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-025-00506-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T10:48:34Z","timestamp":1767782914000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/s42400-025-00506-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,7]]},"references-count":52,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,12]]}},"alternative-id":["506"],"URL":"https:\/\/doi.org\/10.1186\/s42400-025-00506-x","relation":{},"ISSN":["2523-3246"],"issn-type":[{"value":"2523-3246","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,7]]},"assertion":[{"value":"20 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 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":"None of the authors have any competing interests in the manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"95"}}