License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2022.1
URN: urn:nbn:de:0030-drops-164796
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16479/
Eriguchi, Reo ;
Kurosawa, Kaoru ;
Nuida, Koji
Multi-Server PIR with Full Error Detection and Limited Error Correction
Abstract
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.
BibTeX - Entry
@InProceedings{eriguchi_et_al:LIPIcs.ITC.2022.1,
author = {Eriguchi, Reo and Kurosawa, Kaoru and Nuida, Koji},
title = {{Multi-Server PIR with Full Error Detection and Limited Error Correction}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {1:1--1:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-238-9},
ISSN = {1868-8969},
year = {2022},
volume = {230},
editor = {Dachman-Soled, Dana},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16479},
URN = {urn:nbn:de:0030-drops-164796},
doi = {10.4230/LIPIcs.ITC.2022.1},
annote = {Keywords: Private Information Retrieval, Error Detection, Error Correction}
}
|
Keywords: |
|
Private Information Retrieval, Error Detection, Error Correction |
|
Collection: |
|
3rd Conference on Information-Theoretic Cryptography (ITC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
30.06.2022 |
