2014/02/18 by Ye Wang, Wang, Ye, Prakash Ishwar +3
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Privacy-Preserving Technologies in Data #cs.CR #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1402.4360
6 pages, extended version of ITW 2014 paper
arxiv created 2014/12/12 · arxiv updated 2014/12/16
In the secure two-party computation problem, two parties wish to compute a (possibly randomized) function of their inputs via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own input and output. For semi-honest parties and information-theoretic security guarantees, it is well-known that, if only noiseless communication is available, only a limited set of functions can be securely computed; however, if interaction is also allowed over general communication primitives (multi-input/output channels), there are "complete" primitives that enable any function to be securely computed. The general set of complete primitives was characterized recently by Maji, Prabhakaran, and Rosulek leveraging an earlier specialized characterization by Kilian. Our contribution in this paper is a simple, self-contained, alternative derivation using elementary information-theoretic tools.