Welcome to the resource topic for 2023/210
Title:
New Generic Constructions of Error-Correcting PIR and Efficient Instantiations
Authors: Reo Eriguchi, Kaoru Kurosawa, Koji Nuida
Abstract:A b-error-correcting m-server Private Information Retrieval (PIR) protocol enables a client to privately retrieve a data item of a database from m servers even in the presence of b malicious servers. List-decodable PIR is a generalization of error-correcting PIR to achieve a smaller number of servers at the cost of giving up unique decoding. Previous constructions of error-correcting and list-decodable PIR have exponential computational complexity in m or cannot achieve sub-polynomial communication complexity n^{o(1)}, where n is the database size. Recently, Zhang, Wang and Wang (ASIACCS 2022) presented a non-explicit construction of error-correcting PIR with n^{o(1)} communication and polynomial computational overhead in m. However, their protocol requires the number of servers to be larger than the minimum one m=2b+1 and they left it as an open problem to reduce it. As for list-decodable PIR, there is no construction with n^{o(1)} communication.
In this paper, we propose new generic constructions of error-correcting and list-decodable PIR from any one-round regular PIR. Our constructions increase computational complexity only by a polynomial factor in m while the previous generic constructions incur \binom{m}{b} multiplicative overheads. Instantiated with the best-known protocols, our construction provides for the first time an explicit error-correcting PIR protocol with n^{o(1)} communication, which reduces the number of servers of the protocol by Zhang, Wang and Wang (ASIACCS 2022). For sufficiently large b, we also show the existence of b-error-correcting PIR with n^{o(1)} communication achieving the minimum number of servers, by allowing for two rounds of interaction. Furthermore, we show an extension to list-decodable PIR and obtain for the first time a protocol with n^{o(1)} communication. Other instantiations improve the communication complexity of the state-of-the-art t-private protocols in which t servers may collude. Along the way, we formalize the notion of \textit{locally surjective map families}, which generalize perfect hash families and may be of independent interest.
ePrint: https://eprint.iacr.org/2023/210
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .