On Robust Combiners for Private Information Retrieval and Other Primitives
Remo Meier and Bartosz Przydatek
Let $A$ and $B$ denote cryptographic primitives. A $(k,m)$-robust $A$-to-$B$ combiner is a construction, which takes $m$ implementations of primitive $A$ as input, and yields an implementation of primitive $B$, which is guaranteed to be secure as long as at least $k$ input implementations are secure. The main motivation for such constructions is the tolerance against wrong assumptions on which the security of implementations is based. For example, a (1,2)-robust $A$-to-$B$ combiner yields a secure implementation of $B$ even if an assumption underlying one of the input implementations of $A$ turns out to be wrong.
In this work we study robust combiners for private information retrieval (PIR), oblivious transfer (OT), and bit commitment (BC). We propose a (1,2)-robust PIR-to-PIR combiner, and describe various optimizations based on properties of existing PIR protocols. The existence of simple PIR-to-PIR combiners is somewhat surprising, since OT, a very closely related primitive, seems difficult to combine (Harnik et al., Eurocrypt'05). Furthermore, we present (1,2)-robust PIR-to-OT and PIR-to-BC combiners. To the best of our knowledge these are the first constructions of $A$-to-$B$ combiners with $A \neq B$. Such combiners, in addition to being interesting in their own right, offer insights into relationships between cryptographic primitives. In particular, our PIR-to-OT combiner together with the impossibility result for OT-combiners of Harnik et al. rule out certain types of reductions of PIR to OT. Finally, we suggest a more fine-grained approach to construction of robust combiners, which may lead to more efficient and practical combiners in many scenarios.
BibTeX Citation
@inproceedings{MeiPrz06,
author = {Remo Meier and Bartosz Przydatek},
title = {On Robust Combiners for Private Information Retrieval and Other Primitives},
editor = {Cynthia Dwork},
booktitle = {Advances in Cryptology --- CRYPTO 2006},
pages = 555--569,
series = {Lecture Notes in Computer Science},
volume = 4117,
year = 2006,
month = 8,
publisher = {Springer-Verlag},
}