Kevin Lawler
New York University

TITLE:
On Robust Combiners for Private Information Retrieval and Other Primitives

ABSTRACT:

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.

AUTHORS : Remo Meier and Bartosz Przydatek