Robust Combiners: Definitions, Results, and Applications.

Yesterday, the study group given by Nigel was on robust combiners (RC) and their applications. Combining different implementations of the same primitve to enhance its security has been exploited, explicitely or implicitely, for long time in the literature, and is nothing but the cryptographic version of "not placing all your eggs in the same basket". We looked at two papers, the first one studies what cryptographic primitives admit RC, and the second paper is concerned about bounds on the size of OT networks. It uses RC for the Oblivious Transfer primitive to prove some of the upper bounds.

 A description of a cryptographic primitive P includes the semantics, thus what P does (usually one privides a functionality  describing the task), and the security of P, which deals with the ability of an attacker to learn something from an implementation of the functionality. For an interactive primitive, one splits the semantics in two parts: the "next message function" sent by one of the participants, and the "output function". This turns out to be useful to formalize the notion of combiners.

So what is a combiner? It is a box (a PPTM) that takes as input several implementations of the same primitive P, and uses them to implement P. At first it might seem redundant, the goal being that even if some but not all the implementations are insecure, the composition is still secure.  Several notions of RC can be considered depending on the type of access to the candidates. The most general notion is a (k,n)-RC, thus the box takes n candidates, with the property that if at least k of them are secure, then RC implements P securely (also the runtime of RC is polynomial in the security parameter, in n and in the length of P's inputs). However this notion does not necessarily base the security of RC in its candidates, as the construction could ignore the candidates and implement P on its own. A black-box combiner (bbRC)  is one which really uses the candidates in its implementation and security proof. Formally a (k,n)-bbRC is given oracle access to the implementation function of the candidates, and for every adversary breaking the combiner, there are n-k+1 candidates S(i) and n-k+1 adversarial PPTMs R(i), with access to A, such that R(i) breaks S(i). If one looks at interactive primitives, more restrictions can be applied. In a third-party bbRC the candidates act as trusted parties (they give no transcript, only take inputs from the combiner and generate outputs). Also one could consider transparent combiners where the  candidates are used only in the context of the interaction: every call to the next message's function is followed by the message being sent to the appropiate party. Turns out that for non-interactive primitives the three variants of bb combiners are equivalent.

Positive and negative results steam from these definitions. On the negative side, the authors show that there are no transparent (1,2)-bbRC for Oblivious Transfer. The idea of the proof is that any such combiner is equally secure when takes two insecure candidates: one secure only for the sender, and the other secure only for the receiver. This inmediatly gives a contradiction since such faulty OTs can be instantiated without any assumptions at all, giving a secure implementation of OT (those of the combiner) with no hardness assumptions. The actual proof is very evolved and is in the spirit of many other black-box impossibility results, they show a world in which OT exists, but OT-combiners do not.

On the positive side, they make a powerful observation: there exist a (1,2)-RC for OWF. The combiner simply concatenates the two outputs of the candidates. This inmediatly implies that any primitive P equivalent to OWF has also a RC (by equivalence we obviously mean a bidirectional polynomial-time reduction between the two primitives). The construction is simple: the two candidates implementing P are reduced to two OWFs, these in turn are combined into a single one which is used to construct back the primitive P. Although a nice feasibility result for Minicrypt, there are more efficient constructions: for example double-keyed encryption, XORing two PRGs, or concatenating two signatures are secure combiners. The only exception seems to be bit commitments, for which achieving efficiency is not trivial. Also they are able to show a third-party (2,3)-bbRC for OT, which is good news after the impossibility result for transparent (1,2)-bbRC.

A nice application of combiners is found in the second paper of the study group. The authors want to implement the n-ary OT functionality. Thus between n parties, any two want to run an OT between them. This is trivial if every pair has a bidirectional OT channel, but then the network would have a quadratic number (in n) of channels. Using combiners they reduce the size of the network to be linear in n (this is true if the adversary corrupts a constant fraction of the parties, note this also includes dishonest majority). The idea is to divide the parties into committees, each with the same number of members (one party may, and will be part of several committees). Within each committe there is a full OT network. Now if two parties want to run an OT, they additively secret share their inputs within the committees, each giving rise to a candidate OT implementation. The committees compute the OT in MPC (the ouptut of the OT can be  expressed as a function of its inputs). In particular they propose to use the GMW protocol, a natural choice as it builds on OT. If at least one member in a given committee is honest, the corresponding candidate is secure. The candidates are combined in a RC, which is secure if a majority of the candidates is secure. The latter is ensured by giving a collection of committees such that any adversary, corrupting an a priori constant number of parties, can cover less than half of the committes. At bottom they use techniques of disperser graphs to find such collection of committees.