List-Decodable Byzantine Robust PIR: Lower Communication Complexity, Higher Byzantine Tolerance, Smaller List Size
For cryptography researchers, this work advances the state of the art in Byzantine-robust PIR by simultaneously improving three key metrics.
This paper proposes two list-decodable Byzantine robust PIR schemes that tolerate a majority of malicious servers, achieve sublinear communication complexity of o(n^{1/2}) for a database of size n, and provide nontrivial list size bounds, outperforming existing solutions in communication, Byzantine tolerance, and list size.
Private Information Retrieval (PIR) is a privacy-preserving primitive in cryptography. Significant endeavors have been made to address the variant of PIR concerning the malicious servers. Among those endeavors, list-decodable Byzantine robust PIR schemes may tolerate a majority of malicious responding servers that provide incorrect answers. In this paper, we propose two perfect list-decodable BRPIR schemes. Our schemes are the first ones that can simultaneously handle a majority of malicious responding servers, achieve a communication complexity of $o(n^{1/2})$ for a database of size n, and provide a nontrivial estimation on the list sizes. Compared with the existing solutions, our schemes attain lower communication complexity, higher byzantine tolerance, and smaller list size.