Byzantine-Robust Private Information Retrieval with Low Communication and Efficient Decoding
Liang Feng Zhang, Huaxiong Wang, Liping Wang · Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security · 2022
A b Byzantine-robust K-out-of-ℓ private information retrieval ((b, K,ℓ)-BRPIR) scheme allows a user to retrieve any item of a database from ℓ servers, even if only K out of the ℓ servers respond and at most b out of the K responding servers provide false answers. The existing BRPIR schemes require either an exponential time decoding algorithm or a communication complexity no better than O(n1/(2k-1) k ℓ log ℓ) with k=K-2b. In this paper, we show a new (b,K,ℓ)-BRPIR scheme that has both a polynomial time decoding algorithm and a communication cost of ℓ • exp(O((log n)1-over 1 r (log log n) 1 overr)) for r=log (K/(2b+1)), which is more efficient when n→ ∞.