Paper 2021/241

On the Round Complexity of Fully Secure Solitary MPC with Honest Majority

Saikrishna Badrinarayanan and Peihan Miao and Pratyay Mukherjee and Divya Ravi

Abstract

We study the problem of secure multiparty computation for functionalities where only one party receives the output, to which we refer as solitary MPC. Recently, Halevi et al. (TCC 2019) studied fully secure (i.e., with guaranteed output delivery) solitary MPC and showed impossibility of such protocols for certain functionalities when there is no honest majority among the parties. In this work, we study fully secure solitary MPC in the honest majority setting and focus on its round complexity. We note that a broadcast channel or public key infrastructure (PKI) setup is necessary for an $n$-party protocol against malicious adversaries corrupting up to $t$ parties where $n/3 \leq t < n/2$. Therefore, we study the following settings and ask the question: Can fully secure solitary MPC be achieved in fewer rounds than fully secure standard MPC in which all parties receive the output? - When there is a broadcast channel and no PKI: * We start with a negative answer to the above question. In particular, we show that the exact round complexity of fully secure solitary MPC is 3, which is the same as fully secure standard MPC. * We then study the minimal number of broadcast rounds needed in the design of round-optimal fully secure solitary MPC. We show that both the first and second rounds of broadcast are necessary when $2 \lceil n/5 \rceil \leq t < n/2$, whereas pairwise-private channels suffice in the last round. Notably, this result also applies to fully secure standard MPC in which all parties receive the output. - When there is a PKI and no broadcast channel, nevertheless, we show more positive results: * We show an upper bound of 5 rounds for any honest majority. This is superior to the super-constant lower bound for fully secure standard MPC in the exact same setting. * We complement this by showing a lower bound of 4 rounds when $3\lceil n/7 \rceil \leq t < n/2$. * For the special case of $t=1,n=3$, when the output receiving party does not have an input to the function, we show an upper bound of $2$ rounds, which is optimal. When the output receiving party has an input to the function, we show a lower bound of 3, which matches an upper bound from prior work. * For the special case of $t=2,n=5$, we show a lower bound of 3 rounds (an upper bound of 4 follows from prior work). All our results also assume the existence of a common reference string (CRS) and pairwise-private channels. Our upper bounds use a decentralized threshold fully homomorphic encryption (dTFHE) scheme (which can be built from the learning with errors (LWE) assumption) as the main building block.