Paper 2003/030

Efficient Multi-Party Computation over Rings

Ronald Cramer, Serge Fehr, Yuval Ishai, and Eyal Kushilevitz

Abstract

Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in various directions. However, all current techniques for secure MPC apply to functions that are represented by (boolean or arithmetic) circuits over finite {\em fields}. We are motivated by two limitations of these techniques: {\sc Generality.} Existing protocols do not apply to computation over more general algebraic structures (except via a brute-force simulation of computation in these structures). {\sc Efficiency.} The best known {\em constant-round} protocols do not efficiently scale even to the case of large finite fields. Our contribution goes in these two directions. First, we propose a basis for unconditionally secure MPC over an arbitrary finite {\em ring}, an algebraic object with a much less nice structure than a field, and obtain efficient MPC protocols requiring only a {\em black-box access} to the ring operations and to random ring elements. Second, we extend these results to the constant-round setting, and suggest efficiency improvements that are relevant also for the important special case of fields. We demonstrate the usefulness of the above results by presenting a novel application of MPC over (non-field) rings to the round-efficient secure computation of the maximum function.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. This is an extended version of a paper that appeared in Eurocrypt '03.
Keywords
mutli-party computationblack-box ringsconstant-round protocols
Contact author(s)
fehr @ brics dk
History
2003-02-12: received
Short URL
https://ia.cr/2003/030
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/030,
      author = {Ronald Cramer and Serge Fehr and Yuval  Ishai and Eyal Kushilevitz},
      title = {Efficient Multi-Party Computation over Rings},
      howpublished = {Cryptology ePrint Archive, Paper 2003/030},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/030}},
      url = {https://eprint.iacr.org/2003/030}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.