Paper 2012/083 Original: eprint.iacr.org/2012/083 ↗
Optimally Robust Private Information Retrieval
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
- Preprint.
- History
- 2012-06-22: last updated
- 2012-02-23: published
- Short URL
- https://ia.cr/2012/083
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}