On Robust Combiners for Private Information Retrieval and Other Primitives

Remo Meier and Bartosz Przydatek

Advances in Cryptology — CRYPTO 2006, Lecture Notes in Computer Science, Springer-Verlag, vol. 4117, pp. 555–569, Aug 2006.

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},
}