Robust Combiners for Cryptographic Primitives

Christian Sommer
Master's thesis, ETH Zurich, 2006

In cryptography, we do not know which computational assumptions are the most secure to rely on. Robust combiners attempt to solve this problem. Given several implementations of a certain primitive, e.g., of a commitment scheme, a combiner merges them into a new implementation that is secure if a minimum number of the input implementations are secure. A (k;n)-robust combiner merges n implementations, where k of them are required to remain secure. In this thesis, we investigate combiners for various primitives. We show which combiners for commitment schemes are possible and which combiners do not exist. We show that a certain combiner construction is impossible if only half of the input implementations are secure (technically speaking, we prove that transparent black-box (1; 2)-robust combiners for commitment schemes do not exist). Furthermore, we give explicit constructions for combiners where the majority of the input implementations are assumed to be secure.

We make further investigations about combiners for interactive proof systems. However, this scenario is far more complicated and therefore, the statements made are somewhat crude.

For oblivious transfer, a yet unpublished paper of Meier et al. proposes more tolerant constructions using a swap operation. We show that such an operation is necessary for certain types of combiners.

@mastersthesis{Som06,
 author = {Christian Sommer},
 title  = {Robust Combiners for Cryptographic Primitives},
 school = {ETH Zurich},
 year   = {2006}
}

Local version (270.1 KB)
Slides (86.8 KB)

Home → Publications → Robust Combiners for Cryptographic Primitives