UCLA

The standard model of Secure Multi-Party Computation (MPC) allows a set of parties with private inputs to compute some joint function of their inputs. The aim of MPC is to allow this computation without revealing any more information than the output of the function. However, achieving this requires a full interaction among the participating parties, which is not always feasible in real life. On the other hand, in certain restricted interaction patterns it is possible for the adversary to learn the output of the function on honest inputs and every possible combination of the corrupted inputs. This motivates the study of different interaction patterns and their properties to better understand and formalize the scenarios under which we can limit the amount of information an adversary can derive.

The interaction pattern that different parties participate in, to compute a function, can be modeled as a graph. This thesis studies the different properties of this graph and answers the following question - ``What is the minimum sequence of edges that are needed to ensure that an adversary cannot collude with other corrupted parties to learn different outputs of the function?". We analyze different scenarios with different bounds on the number of corrupted and output parties.