Optimally Robust Private Information Retrieval

Date Added: Feb 2012
Format: PDF

The authors give a protocol for multi-server information-theoretic private information retrieval which achieves the theoretical limit for Byzantine robustness. That is, the protocol can allow a client to successfully complete queries and identify server misbehavior in the presence of the maximum possible number of malicious servers. They have implemented their scheme and it is extremely fast in practice: up to thousands of times faster than previous work. They achieve these improvements by using decoding algorithms for error-correcting codes that take advantage of the practical scenario where the client is interested in multiple blocks of the database.