A Zero-One Law for Secure Multi-party Computation with Ternary Outputs
2011 (English)In: Theory Of Cryptography / [ed] Yuval Ishai, Springer Berlin/Heidelberg, 2011, Vol. 6597, 382-399 p.Conference paper (Refereed)
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  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 Z3, meaning that each function with range Z3 either requires honest majority or tolerates up to n colluding nodes.
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2011. Vol. 6597, 382-399 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 6597
IdentifiersURN: urn:nbn:se:kth:diva-31980DOI: 10.1007/978-3-642-19571-6_23ISI: 000297038500023ScopusID: 2-s2.0-79953210030ISBN: 978-364219570-9OAI: oai:DiVA.org:kth-31980DiVA: diva2:407881
8th Theory of Cryptography Conference, TCC 2011; Providence, RI; 28 March 2011 through 30 March 2011
FunderICT - The Next Generation
QC 201104202011-04-012011-04-012012-06-13Bibliographically approved