On Robust Combiners for Private Information Retrieval and Other Primitives

Let and

$\mathcal A$

and

$\mathcal B$

denote cryptographic primitives.

$\mathcal A$

(k

,m

)-robust

$\mathcal A$

-to-

$\mathcal B$

combiner

is a construction, which takes

m

implementations of primitive

${\ensuremath{{\cal A}}}$

as input, and yields an implementation of primitive

${\ensuremath{{\cal 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

$\mathcal A$

-to-

$\mathcal B$

combiner yields a secure implementation of

${\ensuremath{{\cal B}}}$

even if an assumption underlying

one

of the input implementations of

${\ensuremath{{\cal 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

$\mathcal A$

-to-

$\mathcal B$

combiners with

${\ensuremath{{\cal A}}}\neq {\ensuremath{{\cal 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.