{\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.
Category / Keywords: cryptographic protocols / mutli-party computation, black-box rings, constant-round protocols Publication Info: This is an extended version of a paper that appeared in Eurocrypt '03. Date: received 12 Feb 2003 Contact author: fehr at brics dk Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20030212:183149 (All versions of this report) Discussion forum: Show discussion | Start new discussion