Pseudo-signatures, Broadcast, and Multi-party Computation from Correlated Randomness

摘要

Unconditionally secure multi-party computations in general, and broadcast in particular, are impossible if any third of the players can be actively corrupted and if no additional information-theoretic primitive is given. In this paper, we relativize this pessimistic result by showing that such a primitive can be as simple as noisy communication channels between the players or weakly correlated pieces of information. We consider the scenario where three players have access to random variables X, Y, and Z, respectively, and give the exact condition on the joint distribution PXYZ under which unconditional broadcast is possible. More precisely, we show that this condition characterizes the possibility of realizing so-called pseudo-signatures between the players. As a consequence of our results, we can give conditions for the possibility of achieving unconditional broadcast between n players and any minority of cheaters and, hence, general multi-party computation under the same condition.