In secure multi-party computation @math parties jointly evaluate an @math -variate function @math in the presence of an adversary which can corrupt up till @math parties. Almost all the works that have appeared in the literature so far assume the presence of authenticated channels between the parties. This assumption is far from realistic. Two directions of research have been borne from relaxing this (strong) assumption: (a) The adversary is virtually omnipotent and can control all the communication channels in the network, (b) Only a partially connected topology of authenticated channels is guaranteed and adversary controls a subset of the communication channels in the network. This work introduces a new setting for (unconditional) secure multiparty computation problem which is an interesting intermediate model with respect to the above well studied models from the literature (by sharing a salient feature from both the above models). We consider the problem of (unconditional) secure multi-party computation when 'some' of the communication channels connecting the parties can be corrupted passively as well as actively. For this setting, some honest parties may be connected to several other honest parties via corrupted channels and may not be able to authentically communicate with them. Such parties may not be assured the canonical guarantees of correctness or privacy. We present refined definitions of security for this new intermediate model of unconditional multiparty computation. We show how to adapt protocols for (Unconditional) secure multiparty computation to realize the definitions and also argue the tightness of the results achieved by us.
Assuming that strictly more than @math parties are honest, it has been shown that it is possible to securely compute any @math -variate function, @cite_0 , @cite_8 for the information theoretic regime. In the computational model, the results have been given in @cite_5 , @cite_3 .
@cite_0 @cite_5 @cite_3 @cite_8
2006453614 44936433 2092422002 2080911030
Every function of n inputs can be efficiently computed by a complete network of n processors in such a way that: If no faults occur, no set of size t n 2 of players gets any additional information (other than the function value), Even if Byzantine faults are allowed, no set of size t n 3 can either disrupt the computation or get additional information. Furthermore, the above bounds on t are tight! Permission to copy without fee all or part of this material is granted provided that the copies are not made or Idistributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machimery. To copy otherwise, or to republish, requires a fee and or specfic permission. correctly run a given Turing machine hi on these 2;‘s while keeping the maximum possible pniracy about them. That is, they want to compute Y ( l,..., 2,) without revealing more about the Zi’s than it is already contained in the value y itself. For instance, if M computes the sum of the q’s, every single player should not be able to learn more than the sum of the inputs of the other parties. Here A4 ma.y very well be a probabilistic Turing machine. In this case, all playen want to agree on a single string y, selected with the right probability distribution, as M’s output. Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth. How can they carry out such a conversation? This is a special case of the following general problem. Suppose m people wish to compute the value of a function f(x1, x2, x3, . . . , xm), which is an integer-valued function of m integer variables xi of bounded range. Assume initially person Pi knows the value of xi and no other x’s. Is it possible for them to compute the value of f , by communicating among themselves, without unduly giving away any information about the values of their own variables? The millionaires’ problem corresponds to the case when m = 2 and f(x1, x2) = 1 if x1 < x2, and 0 otherwise. In this paper, we will give precise formulation of this general problem and describe three ways of solving it by use of one-way functions (i.e., functions which are easy to evaluate but hard to invert). These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc. We will also discuss the complexity question “How many bits need to be exchanged for the computation”, and describe methods to prevent participants from cheating. Finally, we study the question “What cannot be accomplished with one-way functions”. Before describing these results, we would like to put this work in perspective by first considering a unified view of secure computation in the next section. Under the assumption that each pair of participants can communicate secretly, we show that any reasonable multiparty protocol can be achieved if at least 2 n 3 of the participants are honest. The secrecy achieved is unconditional. It does not rely on any assumption about computational intractability.