{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T14:21:27Z","timestamp":1773325287074,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":37,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819570713","type":"print"},{"value":"9789819570720","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-981-95-7072-0_30","type":"book-chapter","created":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:09:51Z","timestamp":1773274191000},"page":"443-458","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["NewtonPIR: Communication Efficient Single-Server PIR"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-0716-6027","authenticated-orcid":false,"given":"Pengfei","family":"Lu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guoyan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,1]]},"reference":[{"key":"30_CR1","unstructured":"Ahmad, I., Yang, Y., Agrawal, D., El\u00a0Abbadi, A., Gupta, T.: Addra: metadata-private voice communication over fully untrusted infrastructure. In: USENIX Symposium on Operating Systems Design and Implementation (2021)"},{"key":"30_CR2","unstructured":"Ali, A., et al.: Communication\u2013computation trade-offs in PIR. In: USENIX Security Symposium, pp. 1811\u20131828 (2021)"},{"key":"30_CR3","unstructured":"Amazon: Amazon EC2 On-Demand Pricing (2021). https:\/\/aws.amazon.com\/ec2\/pricing\/on-demand\/. Accessed 15 May 2024"},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"Angel, S., Chen, H., Laine, K., Setty, S.: PIR with compressed queries and amortized query processing. In: IEEE Symposium on Security and Privacy, pp. 962\u2013979. IEEE (2018)","DOI":"10.1109\/SP.2018.00062"},{"key":"30_CR5","unstructured":"Angel, S., Setty, S.: Unobservable communication over fully untrusted infrastructure. In: USENIX Symposium on Operating Systems Design and Implementation, pp. 551\u2013569 (2016)"},{"key":"30_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-44598-6_4","volume-title":"Advances in Cryptology \u2014 CRYPTO 2000","author":"A Beimel","year":"2000","unstructured":"Beimel, A., Ishai, Y., Malkin, T.: Reducing the servers computation in private information retrieval: PIR with preprocessing. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 55\u201373. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44598-6_4"},{"issue":"1","key":"30_CR7","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/s00145-014-9192-y","volume":"29","author":"DR Brown","year":"2016","unstructured":"Brown, D.R.: Breaking RSA may be as difficult as factoring. J. Cryptol. 29(1), 220\u2013241 (2016)","journal-title":"J. Cryptol."},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 41\u201350. IEEE (1995)","DOI":"10.1109\/SFCS.1995.492461"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Chor, B., Gilboa, N.: Computationally private information retrieval. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 304\u2013313 (1997)","DOI":"10.1145\/258533.258609"},{"key":"30_CR10","unstructured":"Colombo, S., Nikitin, K., Corrigan-Gibbs, H., Wu, D.J., Ford, B.: Authenticated private information retrieval. In: USENIX Security Symposium, pp. 3835\u20133851 (2023)"},{"key":"30_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-031-07085-3_1","volume-title":"Advances in Cryptology - EUROCRYPT 2022","author":"H Corrigan-Gibbs","year":"2022","unstructured":"Corrigan-Gibbs, H., Henzinger, A., Kogan, D.: Single-server private information retrieval with sublinear amortized time. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13276, pp. 3\u201333. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-07085-3_1"},{"key":"30_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-030-45721-1_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"H Corrigan-Gibbs","year":"2020","unstructured":"Corrigan-Gibbs, H., Kogan, D.: Private information retrieval with sublinear online time. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 44\u201375. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45721-1_3"},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"Davidson, A., Pestana, G., Celi, S.: FrodoPIR: simple, scalable, single-server private information retrieval. In: Proceedings on Privacy Enhancing Technologies (2023)","DOI":"10.56553\/popets-2023-0022"},{"key":"30_CR14","unstructured":"Epperson, J.F.: An Introduction to Numerical Methods and Analysis. Wiley, Cham (2013)"},{"key":"30_CR15","unstructured":"Faires, J.D., Burden, R.L.: Numerical Methods, 4th edn. Cengage Learning (2012)"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"Gaur, M., Gunaratna, K., Srinivasan, V., Jin, H.: ISEEQ: information seeking question generation using dynamic meta-information retrieval and knowledge graphs. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp. 10672\u201310680 (2022)","DOI":"10.1609\/aaai.v36i10.21312"},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 169\u2013178 (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"30_CR18","unstructured":"Gupta, T., Crooks, N., Mulhern, W., Setty, S., Alvisi, L., Walfish, M.: Scalable and private media consumption with popcorn. In: USENIX Symposium on Networked Systems Design and Implementation, pp. 91\u2013107 (2016)"},{"key":"30_CR19","unstructured":"Henzinger, A., Hong, M.M., Corrigan-Gibbs, H., Meiklejohn, S., Vaikuntanathan, V.: One server for the price of two: simple and fast single-server private information retrieval. In: USENIX Security Symposium, pp. 3889\u20133905 (2023)"},{"key":"30_CR20","unstructured":"Howarth, J.: Alarming data privacy statistics for 2024 (2024). https:\/\/explodingtopics.com\/blog\/data-privacy-stats"},{"key":"30_CR21","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Batch codes and their applications. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 262\u2013271 (2004)","DOI":"10.1145\/1007352.1007396"},{"key":"30_CR22","unstructured":"Kales, D., Rechberger, C., Schneider, T., Senker, M., Weinert, C.: Mobile private contact discovery at scale. In: USENIX Security Symposium, pp. 1447\u20131464 (2019)"},{"key":"30_CR23","doi-asserted-by":"crossref","unstructured":"Liu, J., Li, J., Wu, D., Ren, K.: Pirana: faster multi-query PIR via constant-weight codes. In: IEEE Symposium on Security and Privacy, pp. 4315\u20134330. IEEE (2024)","DOI":"10.1109\/SP54263.2024.00039"},{"key":"30_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-13190-5_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"V Lyubashevsky","year":"2010","unstructured":"Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1\u201323. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13190-5_1"},{"key":"30_CR25","unstructured":"Ma, Y., Zhong, K., Rabin, T., Angel, S.: Incremental offline\/online PIR. In: USENIX Security Symposium, pp. 1741\u20131758 (2022)"},{"key":"30_CR26","doi-asserted-by":"crossref","unstructured":"Melchor, C.A., Barrier, J., Fousse, L., Killijian, M.O.: XPIR: private information retrieval for everyone. In: Proceedings on Privacy Enhancing Technologies, pp. 155\u2013174 (2016)","DOI":"10.1515\/popets-2016-0010"},{"key":"30_CR27","doi-asserted-by":"crossref","unstructured":"Menon, S.J., Wu, D.J.: Spiral: fast, high-rate single-server PIR via FHE composition. In: IEEE Symposium on Security and Privacy, pp. 930\u2013947. IEEE (2022)","DOI":"10.1109\/SP46214.2022.9833700"},{"key":"30_CR28","unstructured":"Menon, S.J., Wu, D.J.: YPIR: high-throughput single-server PIR with silent preprocessing. In: USENIX Security Symposium, pp. 5985\u20136002 (2024)"},{"key":"30_CR29","doi-asserted-by":"crossref","unstructured":"Mughees, M.H., Chen, H., Ren, L.: OnionPIR: response efficient single-server PIR. In: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 2292\u20132306 (2021)","DOI":"10.1145\/3460120.3485381"},{"key":"30_CR30","doi-asserted-by":"crossref","unstructured":"Mughees, M.H., Ren, L.: Vectorized batch private information retrieval. In: IEEE Symposium on Security and Privacy, pp. 437\u2013452. IEEE (2023)","DOI":"10.1109\/SP46215.2023.10179329"},{"key":"30_CR31","unstructured":"Smart, N.P., et\u00a0al.: Cryptography: An Introduction, vol.\u00a03. McGraw-Hill, New York (2003)"},{"key":"30_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/978-3-319-56614-6_5","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"A Takayasu","year":"2017","unstructured":"Takayasu, A., Lu, Y., Peng, L.: Small CRT-exponent RSA revisited. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 130\u2013159. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56614-6_5"},{"key":"30_CR33","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-1-4842-9563-2_13","volume-title":"Beginning C++ Compilers: An Introductory Guide to Microsoft C\/C++ and MinGW Compilers","author":"BI Tuleuov","year":"2024","unstructured":"Tuleuov, B.I., Ospanova, A.B.: Crypto++. In: Tuleuov, B.I., Ospanova, A.B. (eds.) Beginning C++ Compilers: An Introductory Guide to Microsoft C\/C++ and MinGW Compilers, pp. 149\u2013156. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-1-4842-9563-2_13"},{"key":"30_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-13190-5_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"M Van Dijk","year":"2010","unstructured":"Van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24\u201343. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13190-5_2"},{"key":"30_CR35","first-page":"1","volume":"2021","author":"W Xu","year":"2021","unstructured":"Xu, W., Wang, B., Lu, R., Qu, Q., Chen, Y., Hu, Y.: Efficient private information retrieval protocol with homomorphically computing univariate polynomials. Secur. Commun. Netw. 2021, 1\u201314 (2021)","journal-title":"Secur. Commun. Netw."},{"issue":"5","key":"30_CR36","doi-asserted-by":"publisher","first-page":"1125","DOI":"10.1109\/TKDE.2012.90","volume":"25","author":"X Yi","year":"2012","unstructured":"Yi, X., Kaosar, M.G., Paulet, R., Bertino, E.: Single-database private information retrieval from fully homomorphic encryption. IEEE Trans. Knowl. Data Eng. 25(5), 1125\u20131134 (2012)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"30_CR37","doi-asserted-by":"crossref","unstructured":"Zhou, M., Park, A., Zheng, W., Shi, E.: Piano: extremely simple, single-server PIR with sublinear server computation. In: IEEE Symposium on Security and Privacy, pp. 4296\u20134314. IEEE (2024)","DOI":"10.1109\/SP54263.2024.00055"}],"container-title":["Lecture Notes in Computer Science","PRICAI 2025: Trends in Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-7072-0_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:09:54Z","timestamp":1773274194000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-7072-0_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9789819570713","9789819570720"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-7072-0_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"1 April 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PRICAI","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Pacific Rim International Conference on Artificial Intelligence","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Wellington","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"New Zealand","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 November 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 November 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pricai2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.pricai.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}