On Robust Combiners for Oblivious Transfer and other Primitives

Danny Harnik     Joe Kilian     Moni Naor    Omer Reingold    Alon Rosen


Suppose that we have two implementations of a cryptographic primitive that we generally trust to be secure for some task. It makes a lot of sense to try and combine these two into one scheme that is guaranteed  to be secure even in the unfortunate case that one of the two original schemes is broken. Call such a mechanism a Robust Combiner. In general a (k,n)-Robust Combiner for a cryptographic primitive is a method for taking n candidate implementations for the primitive and combining them into a single scheme such that if at least k of the candidates are secure, then the combined one is secure.

In this paper we study what primitives admit robust combiners. In addition to known and very simple combiners for one-way functions and equivalent primitives, we show robust combiners for protocols in the world of public key cryptography, namely for Key Agreement (KA).
The main point we make is that things are not as nice for Oblivious Transfer (OT) and in general for secure computation.
We prove that there are no ``transparent black-box" robust combiners for OT, giving an indication to the difficulty of finding combiners for OT. On the positive side we show a black box construction of a (2,3)-robust combiner for OT, as well as a generic construction of (1,n)-robust OT-combiners from any (1,2)-robust OT-combiner.

The paper: Postscript , gzipped Postscript . Slides: ppt.

Related On-Line Papers:

Back to On-Line Publications

Back Home