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.

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

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},
note = {\url{https://eprint.iacr.org/2012/083}},
url = {https://eprint.iacr.org/2012/083}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.