In this dissertation, we study the round complexity of cryptographic protocols, giving special attention to secure multi-party computation (MPC), which allows a group of mutually distrusting parties P1, . . . , Pn, each with private input xi, to compute the evaluation of some function f(x1,...,xn) without revealing their inputs to each other. We study this question via a recent new strong version of MPC, identified by a recent work by Benhamouda and Lin [BL20] and termed Multiparty reusable Non-Interactive Secure Computation (MrNISC). MrNISC requires the following general structure:
1. Input encoding: at any time, a party can publish an encoding of its input noninteractively, independent of the number of parties.2. Computation encoding: At any time, any subset I of parties can jointly compute a function f on their inputs xI = {xi}i∈I by
broadcasting a single public message. Each party’s message is only dependent on the input encodings of the parties in I.
Parties are allowed to join the system at any time by publishing their input encoding, even after an arbitrary number of computation sessions have occurred. MrNISC achieves
ii
essentially the best-possible form of non-interactivity for MPC protocols without running into known impossibility results on non-interactive MPC. MrNISC is a strict generalization of two-round concurrent-secure MPC.
We give the first construction of MrNISC which satisfies the full definition of malicious security in the plain model. By doing so, we also give the first construction of concurrent- secure two-round MPC. Security is given in the super-polynomial-simulation regime, and relies on the existence of an indistinguishability obfuscation scheme along with other standard assumptions.
During the course of obtaining our main result, we also obtain new results in the areas of zero-knowledge arguments and non-malleable commitments.
First, we give a two-round zero-knowledge argument which satisfies a weak form of statistical soundness, which we call sometimes-statistical soundness. Previously, no two-round zero knowledge protocols satisfied any form of statistical soundness. We also are able to give such a protocol which simultaneously satisfies statistical zero-knowledge and is highly reusable.
Second, we give a new one-round non-malleable commitment which satisfies full non- malleability with respect to commitment. Our construction works in the simultaneous-message model and is based heavily on the work of (Khurana, EUROCRYPT 2021), and is notable for not relying on the “multi-collision-resistant” hash function. All previous one-round non-malleable commitments with full security have relied on this assumption.
