{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:05:32Z","timestamp":1757624732396,"version":"3.44.0"},"publisher-location":"Cham","reference-count":60,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783032019127"},{"type":"electronic","value":"9783032019134"}],"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-032-01913-4_6","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T08:22:47Z","timestamp":1755332567000},"page":"175-210","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Malicious Security for\u00a0PIR (Almost) for\u00a0Free"],"prefix":"10.1007","author":[{"given":"Brett","family":"Falk","sequence":"first","affiliation":[]},{"given":"Pratyush","family":"Mishra","sequence":"additional","affiliation":[]},{"given":"Matan","family":"Shtepel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"key":"6_CR1","unstructured":"Aiello, W., Bhatt, S.N., Ostrovsky, R., Rajagopalan, S.: Fast verification of any remote procedure call: short witness-indistinguishable one-round proofs for NP. In: ICALP \u201900"},{"key":"6_CR2","unstructured":"Angel, S., Chen, H., Laine, K., Setty, S.: PIR with compressed queries and amortized query processing. In: S &P \u201918"},{"key":"6_CR3","unstructured":"Boyle, E., Holmgren, J., Ma, F., Weiss, M.: On the Security of Doubly Efficient PIR. ePrint Report 2021\/1113 https:\/\/eprint.iacr.org\/2021\/1113"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., Malkin, T.: Reducing the servers\u2019 computation in private information retrieval: PIR with preprocessing. In: J. Cryptol. (2004)","DOI":"10.1007\/s00145-004-0134-y"},{"key":"6_CR5","unstructured":"Ben-David, S., Kalai, Y.T., Paneth, O.: Verifiable private information retrieval. In: TCC \u201922"},{"key":"6_CR6","unstructured":"blyssForBTC (2023). https:\/\/btc.usespiral.com\/"},{"key":"6_CR7","unstructured":"Boemer, F., Tarbe, K., Rishi, R.: Announcing Swift Homomorphic Encryption (2024). https:\/\/www.swift.org\/blog\/announcing-swift-homomorphic-encryption\/"},{"key":"6_CR8","unstructured":"Cachin, C., Camenisch, J., Kilian, J., M\u00fcller, J.: One-round secure computation and secure autonomous mobile agents. In: ICALP \u201910"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private Information Retrieval. In: J. ACM (1998)","DOI":"10.1145\/293347.293350"},{"key":"6_CR10","unstructured":"Canetti, R., Holmgren, J., Richelson, S.: Towards doubly efficient private information retrieval. In: TCC \u201917"},{"key":"6_CR11","unstructured":"Corrigan-Gibbs, H., Kogan, D.: Private information retrieval with sublinear online time. In: EUROCRYPT \u201920"},{"key":"6_CR12","unstructured":"de Castro, L., Lee, K.: VeriSimplePIR: Verifiability in SimplePIR at No Online Cost for Honest Servers. In: USENIX Security \u201924"},{"key":"6_CR13","doi-asserted-by":"publisher","DOI":"10.1145\/3397474","volume-title":"Testing linearity against non-signaling strategies","author":"A Chiesa","year":"2020","unstructured":"Chiesa, A., Manohar, P., Shinkar, I.: Testing linearity against non-signaling strategies. ACM Trans. Comput, Theory (2020)"},{"key":"6_CR14","unstructured":"Colombo, S., Nikitin, K., Corrigan-Gibbs, H., Wu, D.J., Ford, B.: Authenticated private information retrieval. In: USENIX \u201923"},{"key":"6_CR15","unstructured":"Cao, Q., et al.: Committed private information retrieval. In: ESORICS \u201923"},{"key":"6_CR16","unstructured":"Dvir, Z., Gopi, S.: 2-server PIR with sub-polynomial communication. In: STOC \u201915"},{"key":"6_CR17","unstructured":"Dwork, C., Langberg, M., Naor, M., Nissim, K., Reingold, O.: Succinct NP Proofs and Spooky Interactions. www.openu.ac.il\/home\/mikel\/papers\/spooky.ps"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511581274"},{"key":"6_CR19","unstructured":"Dietz, M., Tessaro, S.: Fully malicious authenticated PIR. In: CRYPTO \u201924"},{"key":"6_CR20","unstructured":"Eriguchi, R., Kurosawa, K., Nuida, K.: Efficient and generic methods to achieve active security in private information retrieval and more advanced database search. In: EUROCRYPT \u201924"},{"key":"6_CR21","unstructured":"Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: EUROCRYPT \u201913"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Ganesh, C., Nitulescu, A., Soria-Vazquez, E.: Rinocchio: SNARKs for ring arithmetic. In: J. Cryptol. (2023)","DOI":"10.1007\/s00145-023-09481-3"},{"key":"6_CR23","unstructured":"Granger, R., Page, D., Stam, M.: On Small Characteristic Algebraic Tori in Pairing-Based Cryptography. ePrint Report 2004\/132"},{"key":"6_CR24","unstructured":"Gentry, C., Ramzan, Z.: Single-database private information retrieval with constant communication rate. In: ICALP \u201905"},{"key":"6_CR25","unstructured":"Groth, J.: On the size of pairing-based non-interactive arguments. In: EUROCRYPT \u201916"},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"Guo, A..: High-rate locally correctable codes via lifting. In: IEEE Trans. Inf. Theory (2016)","DOI":"10.1109\/TIT.2015.2503767"},{"key":"6_CR27","unstructured":"Henzinger, A., Dauterman, E., Corrigan-Gibbs, H., Zeldovich, N.: Private web search with tiptoe. In: SOSP \u201923"},{"key":"6_CR28","unstructured":"Henzinger, A., Hong, M.M., Gibbs, H.C., Meiklejohn, S., Vaikuntanathan, V.: One server for the price of two: simple and fast single-server private information retrieval. In: USENIX Security \u201923. USENIX Association"},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"van der Hoeven, J., Schost, E.: Multi-point evaluation in higher dimensions. In: Appl. Algebra Eng. Commun. Comput. (2013)","DOI":"10.1007\/s00200-012-0179-3"},{"key":"6_CR30","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Sufficient conditions for collision- resistant hashing. In: TCC \u201905"},{"key":"6_CR31","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Batch codes and their applications. In: STOC \u201904"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Jutla, C.S., Patthak, A.C., Rudra, A., Zuckerman, D.: Testing low-degree polynomials over prime fields. In: Random Struct. Algorithms (2009)","DOI":"10.1002\/rsa.20262"},{"key":"6_CR33","unstructured":"Kogan, D., Corrigan-Gibbs, H.: Private blocklist lookups with checklist. In: USENIX Security \u201921"},{"key":"6_CR34","unstructured":"Kruglik, S., Dau, S.H., Kiah, H.M., Wang, H., Zhang, L.F.: Querying Twice to Achieve Information-Theoretic Verifiability in Private Information Retrieval. techrxiv Report 24290563"},{"key":"6_CR35","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC \u201992"},{"key":"6_CR36","doi-asserted-by":"crossref","unstructured":"Kopparty, S., Kumar, M., Sha, H.: High rate multivariate polynomial evaluation codes. In: CoRR (2024)","DOI":"10.1145\/3717823.3718106"},{"key":"6_CR37","unstructured":"Kalai, Y., Lombardi, A., Vaikuntanathan, V., Wichs, D.: Boosting batch arguments and RAM delegation. In: ACM"},{"key":"6_CR38","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. In: FOCS \u201997"},{"key":"6_CR39","unstructured":"Kalai, Y.T., Raz, R., Rothblum, R.D.: How to delegate computations: the power of no-signaling proofs. In: STOC \u201914"},{"key":"6_CR40","doi-asserted-by":"crossref","unstructured":"Kopparty, S., Saraf, S., Yekhanin, S.: High-rate codes with sublinear-time decoding. In: JACM (2014). Preliminary version appeared in STOC \u201911","DOI":"10.1145\/2629416"},{"key":"6_CR41","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: STOC \u201900"},{"key":"6_CR42","unstructured":"Ke, P., Zhang, L.F.: Private information retrieval with result verification for more servers. In: ACNS \u201923"},{"key":"6_CR43","unstructured":"Lin, W., Mook, E., Wichs, D.: Doubly efficient private information retrieval and fully homomorphic RAM computation from ring LWE. In: STOC \u201923"},{"key":"6_CR44","unstructured":"Lazzaretti, A., Papamanthou, C.: TreePIR: sublinear-time and polylog-bandwidth private information retrieval from DDH. In: CRYPTO \u201923"},{"key":"6_CR45","unstructured":"Merkle, R.C.: A certified digital signature. In: CRYPTO \u201989"},{"key":"6_CR46","doi-asserted-by":"crossref","unstructured":"Micali, S.: Computationally Sound Proofs. In: SIAM J. Comp. (2000). Preliminary version appeared in FOCS \u201994","DOI":"10.1137\/S0097539795284959"},{"key":"6_CR47","unstructured":"Mittal, P., Olumofin, F.G., Troncoso, C., Borisov, N., Goldberg, I.: PIR-Tor: scalable anonymous communication using private information retrieval. In: USENIX Security \u201911"},{"key":"6_CR48","unstructured":"Menon, S.J., Wu, D.J.: YPIR: High-Throughput Single-Server PIR with Silent Preprocessing. In"},{"key":"6_CR49","unstructured":"Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: EUROCRYPT \u201999"},{"key":"6_CR50","unstructured":"Patel, S., Seo, J.Y., Yeo, K.: Don\u2019t be dense: efficient keyword pir for sparse databases. In: USENIX Security \u201923"},{"key":"6_CR51","unstructured":"Ryan, M.D.: Enhanced certificate transparency and end-to-end encrypted mail. In: NDSS \u201914"},{"key":"6_CR52","unstructured":"Shi, E., Aqeel, W., Chandrasekaran, B., Maggs, B.M.: Puncturable pseudorandom sets and private information retrieval with near-optimal online bandwidth and time. In: CRYPTO \u201921"},{"key":"6_CR53","unstructured":"Soria-Vazquez, E.: Doubly efficient interactive proofs over infinite and noncommutative rings. In: TCC \u201922"},{"key":"6_CR54","unstructured":"spiralwiki. https:\/\/spiralwiki.com (2023)"},{"key":"6_CR55","unstructured":"Waters, B., Wu, D.J.: Adaptively-sound succinct arguments for NP from indistinguishability obfuscation"},{"key":"6_CR56","unstructured":"Wang, X., Zhao, L.: Verifiable single-server private information retrieval. In: ICICS"},{"key":"6_CR57","unstructured":"Wang, Y., Zhang, J., Liu, J., Yang, X.: Crust: verifiable and efficient private information retrieval with sublinear online time. ePrint Report 2023\/1607"},{"key":"6_CR58","doi-asserted-by":"crossref","unstructured":"Yekhanin, S.: Private information retrieval. In: Commun. ACM (2010)","DOI":"10.1007\/978-3-642-14358-8_4"},{"key":"6_CR59","unstructured":"Zhang, L.F., Safavi-Naini, R.: Verifiable multi-server private information retrieval. In: ACNS \u201914"},{"key":"6_CR60","doi-asserted-by":"crossref","unstructured":"Zhao, L., Wang, X., Huang, X.: Verifiable single-server private information retrieval from LWE with binary errors. In: Information Sciences (2021)","DOI":"10.1016\/j.ins.2020.08.071"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-01913-4_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T14:56:32Z","timestamp":1757429792000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01913-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783032019127","9783032019134"],"references-count":60,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01913-4_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"17 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","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 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"45","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}