Optimally Robust Private Information Retrieval

Casey Devet; Ian Goldberg; Nadia Heninger

Paper 2012/083

Optimally Robust Private Information Retrieval

Casey Devet, 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Unknown where it was published
Keywords: private information retrieval implementation
Contact author(s): iang @ cs uwaterloo ca
History: 2012-06-22: revised; 2012-02-23: received; See all versions
Short URL: https://ia.cr/2012/083
License: CC BY

BibTeX

@misc{cryptoeprint:2012/083,
      author = {Casey Devet and Ian Goldberg and Nadia Heninger},
      title = {Optimally Robust Private Information Retrieval},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/083},
      year = {2012},
      url = {https://eprint.iacr.org/2012/083}
}