Paper 2021/684

Tight Setup Bounds for Identifiable Abort

Nicholas Brandt

Abstract

We present fundamental (in-)feasibility results for the strongest security notion for Secure Multi-Party Computation (MPC) that is achievable when a majority of parties is malicious, i.e. security with Identifiable Abort. As general Universally Composable (UC) MPC requires a setup, typically in the form of a Common Reference String or Common-Randomness, we investigate whether the setup must provide randomness to all parties. Given broadcast, we give tight bounds for the necessary and sufficient setup cardinality, i.e. number of participating parties, for UC-MPC protocols with Identifiable Abort. Concretely, we improve previous upper bounds by constructing Secure Function Evaluation for $$ parties ($$ of which are honest) from setups of cardinality $$ and broadcast. Conversely, we present the first general lower bound on the minimal setup cardinality for Identifiable Abort by proving that setups of cardinality $$ plus broadcast are insufficient even for a commitment among $$ parties. Somewhat surprisingly, we show that Oblivious Transfer plus broadcast is sufficient for $$ which is consistent with the fact that in two-party MPC Identifiable Abort comes for free. We present the results in the Universal Composibility (UC) framework and assume the setup functionalities to be secure with Identifiable Abort. Our constructions yield an efficient (poly-time) protocol for any $$ where $$ is the security parameter if at least a constant fraction $$ of parties is honest. However for $$ our results suggest that for efficient protocols the overall number of parties $$ is limited quite severely by $$.