Cryptology ePrint Archive: Report 2012/083

Optimally Robust Private Information Retrieval

Casey Devet and Ian Goldberg and Nadia Heninger

Abstract: We 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. We have implemented our scheme and it is extremely fast in practice: up to thousands of times faster than previous work. We 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.

Category / Keywords: cryptographic protocols / private information retrieval, implementation

Date: received 22 Feb 2012, last revised 22 Jun 2012

Contact author: iang at cs uwaterloo ca

Available format(s): PDF | BibTeX Citation

Version: 20120622:115220 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]