A Zero-One Law for Secure Multi-Party Computation with Ternary Outputs

by Gunnar Kreitz

Theory of Cryptography Conference 2011 (TCC 2011), LNCS 6597

Abstract

There are protocols to privately evaluate any function in the passive (honest-but-curious) setting assuming that the honest nodes are in majority. For some specific functions, protocols are known which remain secure even without an honest majority. The seminal work by Chor and Kushilevitz [1] gave a complete characterization of Boolean functions, showing that each Boolean function either requires an honest majority, or is such that it can be privately evaluated regardless of the number of colluding nodes.

The problem of discovering the threshold for secure evaluation of more general functions remains an open problem. Towards a resolution, we provide a complete characterization of the security threshold for functions with three different outputs. Surprisingly, the zero-one law for Boolean functions extends to Z₃, meaning that each function with range Z₃ either requires honest majority or tolerates up to n colluding nodes.

Download

• Full Version. The full version is also available as Cryptology ePrint Archive, Report 2011/002.
• Conference Version (identical to full version, but with most proofs omitted)
• Slides from TCC 2011

Copyright

This paper (in both full and conference version) has been published on this web site under a Creative Commons license. Subsequently, the copyright to the conference version was assigned to IACR.

A Zero-One Law for Secure Multi-Party Computation with Ternary Outputs by Gunnar Kreitz is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.