{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,27]],"date-time":"2025-04-27T09:10:08Z","timestamp":1745745008075,"version":"3.40.4"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031910975","type":"print"},{"value":"9783031910982","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-91098-2_11","type":"book-chapter","created":{"date-parts":[[2025,4,27]],"date-time":"2025-04-27T08:44:10Z","timestamp":1745743450000},"page":"284-313","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Pseudorandom Functions with\u00a0Weak Programming Privacy and\u00a0Applications to\u00a0Private Information Retrieval"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2436-0230","authenticated-orcid":false,"given":"Ashrujit","family":"Ghoshal","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6034-9245","authenticated-orcid":false,"given":"Mingxun","family":"Zhou","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5605-1048","authenticated-orcid":false,"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0003-3032-8875","authenticated-orcid":false,"given":"Bo","family":"Peng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,28]]},"reference":[{"key":"11_CR1","unstructured":"Improving DNS privacy with oblivious DoH in 1.1.1.1. https:\/\/blog.cloudflare.com\/oblivious-dns\/"},{"key":"11_CR2","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"},{"key":"11_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/978-3-319-56620-7_15","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"D Boneh","year":"2017","unstructured":"Boneh, D., Kim, S., Montgomery, H.: Private puncturable PRFs from standard lattice assumptions. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 415\u2013445. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56620-7_15"},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1007\/978-3-662-54388-7_17","volume-title":"Public-Key Cryptography \u2013 PKC 2017","author":"D Boneh","year":"2017","unstructured":"Boneh, D., Lewi, K., Wu, D.J.: Constraining pseudorandom functions privately. In: Fehr, S. (ed.) PKC 2017. LNCS, vol. 10175, pp. 494\u2013524. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-54388-7_17"},{"key":"11_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-642-42045-0_15","volume-title":"Advances in Cryptology - ASIACRYPT 2013","author":"D Boneh","year":"2013","unstructured":"Boneh, D., Waters, B.: Constrained pseudorandom functions and their applications. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 280\u2013300. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-42045-0_15"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-031-15985-5_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2022","author":"E Boyle","year":"2022","unstructured":"Boyle, E., Gilboa, N., Ishai, Y., Kolobov, V.I.: Programmable distributed point functions. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13510, pp. 121\u2013151. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15985-5_5"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/978-3-642-54631-0_29","volume-title":"Public-Key Cryptography \u2013 PKC 2014","author":"E Boyle","year":"2014","unstructured":"Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 501\u2013519. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54631-0_29"},{"key":"11_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-319-70500-2_10","volume-title":"Theory of Cryptography","author":"Z Brakerski","year":"2017","unstructured":"Brakerski, Z., Tsabary, R., Vaikuntanathan, V., Wee, H.: Private constrained PRFs (and More) from LWE. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 264\u2013302. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70500-2_10"},{"key":"11_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-319-56620-7_16","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"R Canetti","year":"2017","unstructured":"Canetti, R., Chen, Y.: Constraint-hiding constrained PRFs for NC$$^{1}$$ from LWE. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 446\u2013476. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56620-7_16"},{"key":"11_CR10","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: FOCS (1995)"},{"key":"11_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 \u2013 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":"11_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":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-031-58751-1_8","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2024","author":"A Ghoshal","year":"2024","unstructured":"Ghoshal, A., Zhou, M., Shi, E.: Efficient pre-processing PIR without public-key cryptography. In: Joye, M., Leander, G. (eds.) EUROCRYPT 2024, Part IV. Lecture Notes in Computer Science, vol. 1465, pp. 210\u2013240. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-58751-1_8"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4) (1986)","DOI":"10.1145\/6490.6503"},{"key":"11_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-030-17656-3_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"A Hamlin","year":"2019","unstructured":"Hamlin, A., Ostrovsky, R., Weiss, M., Wichs, D.: Private anonymous data access. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 244\u2013273. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17656-3_9"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Henzinger, A., Dauterman, E., Corrigan-Gibbs, H., , Zeldovich, N.: Private web search with Tiptoe. In: 29th ACM Symposium on Operating Systems Principles (SOSP), Koblenz, Germany (2023)","DOI":"10.1145\/3600006.3613134"},{"key":"11_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-32009-5_1","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"VT Hoang","year":"2012","unstructured":"Hoang, V.T., Morris, B., Rogaway, P.: An enciphering scheme based on a card shuffle. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 1\u201313. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32009-5_1"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Hoover, A., Patel, S., Persiano, G., Yeo, K.: Plinko: single-server PIR with efficient updates via invertible PRFs. IACR Cryptol. ePrint Arch. 318 (2024)","DOI":"10.1007\/978-3-031-91095-1_1"},{"key":"11_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-031-68400-5_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2024","author":"Y Ishai","year":"2024","unstructured":"Ishai, Y., Shi, E., Wichs, D.: PIR with client-side preprocessing: information-theoretic constructions and lower bounds. In: Reyzin, L., Stebila, D. (eds.) CRYPTO 2024. LNCS, vol. 14928, pp. 148\u2013182. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-68400-5_5"},{"key":"11_CR20","unstructured":"Kogan, D., Corrigan-Gibbs, H.: Private blocklist lookups with checklist. In: 30th USENIX Security Symposium (USENIX Security 2021), pp. 875\u2013892. USENIX Association (2021). https:\/\/www.usenix.org\/conference\/usenixsecurity21\/presentation\/kogan"},{"key":"11_CR21","unstructured":"Lazzaretti, A., Papamanthou, C.: Single server PIR with sublinear amortized time and polylogarithmic bandwidth. Cryptology ePrint Archive, Paper 2022\/830 (2022). https:\/\/eprint.iacr.org\/2022\/830"},{"key":"11_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/978-3-031-38545-2_10","volume-title":"Advances in Cryptology \u2013 CRYPTO 2023","author":"A Lazzaretti","year":"2023","unstructured":"Lazzaretti, A., Papamanthou, C.: TreePIR: sublinear-time and polylog-bandwidth private information retrieval from DDH. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14082, pp. 284\u2013314. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-38545-2_10"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Lin, W.K., Mook, E., Wichs, D.: Doubly efficient private information retrieval and fully homomorphic ram computation from ring LWE. In: STOC (2023)","DOI":"10.1145\/3564246.3585175"},{"key":"11_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-642-11799-2_15","volume-title":"Theory of Cryptography","author":"U Maurer","year":"2010","unstructured":"Maurer, U., Tessaro, S.: A hardcore lemma for computational indistinguishability: security amplification for arbitrarily weak PRGs with optimal stretch. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 237\u2013254. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11799-2_15"},{"key":"11_CR25","unstructured":"Mughees, M.H., I, S., Ren, L.: Simple and practical amortized sublinear private information retrieval. Cryptology ePrint Archive, Paper 2023\/1072 (2023)"},{"key":"11_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/978-3-319-76581-5_23","volume-title":"Public-Key Cryptography \u2013 PKC 2018","author":"C Peikert","year":"2018","unstructured":"Peikert, C., Shiehian, S.: Privately constraining and programming PRFs, the LWE way. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10770, pp. 675\u2013701. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-76581-5_23"},{"key":"11_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/978-3-030-84259-8_22","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"E Shi","year":"2021","unstructured":"Shi, E., Aqeel, W., Chandrasekaran, B., Maggs, B.: Puncturable pseudorandom sets and private information retrieval with near-optimal online bandwidth and time. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 641\u2013669. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84259-8_22"},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"Woodruff, D., Yekhanin, S.: A geometric approach to information-theoretic private information retrieval. In: 20th Annual IEEE Conference on Computational Complexity (CCC 2005), pp. 275\u2013284 (2005)","DOI":"10.1109\/CCC.2005.2"},{"key":"11_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-031-30545-0_14","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2023","author":"M Zhou","year":"2023","unstructured":"Zhou, M., Lin, W.K., Tselekounis, Y., Shi, E.: Optimal single-server private information retrieval. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14004, pp. 395\u2013425. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30545-0_14"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Zhou, M., Park, A., Shi, E., Zheng, W.: Piano: extremely simple, single-server PIR with sublinear server computation. In: IEEE S & P (2024)","DOI":"10.1109\/SP54263.2024.00055"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-91098-2_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,27]],"date-time":"2025-04-27T08:44:14Z","timestamp":1745743454000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-91098-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031910975","9783031910982"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-91098-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"28 April 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Madrid","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","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":"4 May 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 May 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"44","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}