2026-07-25T23:49:47Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:16479 2024-03-06T10:57:35Z ddc:004 open_access
Multi-Server PIR with Full Error Detection and Limited Error Correction Eriguchi, Reo Kurosawa, Kaoru Nuida, Koji Private Information Retrieval Error Detection Error Correction An 𝓁-server Private Information Retrieval (PIR) scheme allows a client to retrieve the Ο„-th element a_Ο„ from a database a = (a₁,…,a_n) which is replicated among 𝓁 servers. It is called t-private if any coalition of t servers learns no information on Ο„, and b-error correcting if a client can correctly compute a_Ο„ from 𝓁 answers containing b errors. This paper concerns the following problems: Is there a t-private 𝓁-server PIR scheme with communication complexity o(n) such that a client can detect errors with probability 1-Ξ΅ even if 𝓁-1 servers return false answers? Is it possible to add error correction capability to it? We first formalize a notion of (1-Ξ΅)-fully error detecting PIR in such a way that an answer returned by any malicious server depends on at most t queries, which reflects t-privacy. We then prove an impossibility result that there exists no 1-fully error detecting (i.e., Ξ΅ = 0) PIR scheme with o(n) communication. Next, for Ξ΅ > 0, we construct 1-private (1-Ξ΅)-fully error detecting and (𝓁/2-O(1))-error correcting PIR schemes which have n^{o(1)} communication, and a t-private one which has O(n^{c}) communication for any t β‰₯ 2 and some constant c < 1. Technically, we show generic transformation methods to add error correction capability to a basic fully error detecting PIR scheme. We also construct such basic schemes by modifying certain existing PIR schemes which have no error detection capability. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Reo Eriguchi and Kaoru Kurosawa and Koji Nuida 2022 Is Part Of LIPIcs, Volume 230, 3rd Conference on Information-Theoretic Cryptography (ITC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2022.1 urn:nbn:de:0030-drops-164796 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.1 eng https://creativecommons.org/licenses/by/4.0/legalcode