SCN '02: Abstract

After an introduction to secure multi-party computation and its applications, we describe a new approach to unconditionally-secure multi-party computation which is considerably simpler than all previous approaches and therefore well-suited from a didactic viewpoint and for giving simple security proofs. Unlike previous protocols it does not rely on algebraic structure (like a finite field of certain size, polynomials, or threshold circuits) and applies equally naturally to threshold and general adversary structures. The complexity is linear in the size of the adversary structure, which for threshold adversaries leads to complexity exponential in the number of players. However, for a small number of players the protocol appears to be more efficient than the previous threshold protocols.