Distributing the Setup in Universally Composable Multi-Party Computation
Jonathan Katz and Aggelos Kiayias and Hong-Sheng Zhou and Vassilis Zikas
Universally composable (UC) protocols retain their security properties even when run concurrently alongside arbitrary other protocols. Unfortunately, it is known that UC multi- party computation (for general functionalities, and without assuming honest majority) is impossible without some form of setup. To circumvent this impossibility, various types of setup assumptions have been proposed. With only a few notable exceptions, past work has viewed these setup assumptions as being implemented by some ideal, incorruptible entity. Any such entity is thus a single point of failure, and security fails catastrophically in case the setup entity is subverted by an adversary. We propose here a clean, general, and generic approach for distributing trust among m arbitrary setups, by model- ing potential corruption of setups within the UC framework, where such corruption might be fail-stop, passive, or arbi- trary and is in addition to possible corruption of the parties themselves. We show several feasibility and impossibility results in this model, for different specifications of the cor- ruptible sets. For example, we show that given m complete setups, up to t of which might be actively corrupted in an adaptive manner, general multiparty computation with no honest majority is possible if and only if t < m/2.