Minimal Complete Primitives for Secure Multi-Party Computation

Matthias Fitzi, Juan A. Garay, Ueli Maurer, and Rafail Ostrovsky

Advances in Cryptology — CRYPTO 2001, Lecture Notes in Computer Science, Springer-Verlag, pp. 80–100, Aug 2001.

The study of minimal cryptographic primitives needed to implement secure computation among two or more players is a fundamental question in cryptography. The issue of complete primitives for the case of two players has been thoroughly studied. 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 \geq n / 3$ . We consider this question, and introduce complete primitives of minimal cardinality for secure multi-party computation. The cardinality issue (number of players accessing the primitive) 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. We show that our primitives are complete and of minimal cardinality possible.

BibTeX Citation

@inproceedings{FGMO01,
    author       = {Matthias Fitzi and Juan A. Garay and Ueli Maurer and Rafail Ostrovsky},
    title        = {Minimal Complete Primitives for Secure Multi-Party Computation},
    editor       = {Joe Kilian},
    booktitle    = {Advances in Cryptology --- CRYPTO 2001},
    pages        = {80--100},
    series       = {Lecture Notes in Computer Science},
    year         = {2001},
    month        = {8},
    publisher    = {Springer-Verlag},
}