One of the most fundamental questions in cryptography is the study of minimal cryptographic primitives needed to implement secure computation among two or more players. The issue of minimal complete primtivies for the case of two players was completely resolved. (A primitive is called complete if any computation can be carried out by the players having access (only) to the primitive and local computation. A primitive is called minimal if any primitive involving less players is not complete.)
However, in the multi-party setting, when there are n > 2 players, and t of them are corrupted, the question of what are the simplest complete primitives remained open for t > n/3. In this talk we consider this question, and introduce complete primitives of minimal cardinality for secure multi-party computation. In particular, we show that ``Oblivious Cast,’’ a natural generalization of Oblivious Transfer to the three-party case, is minimal and complete for t < n/2.
The cardinality issue is essential in settings where the primitives are implemented by some other means, and the simpler the primitive, the easier it is to realize it.
This is joint work with Matthias Fitzi and Ueli Maurer (ETH Zurich), and Rafail Ostrovsky (Telcordia).