The standard model of Secure Multi-Party Computation (MPC) allows a set of parties with private inputs to compute some joint function of their inputs. The aim of MPC is to allow this computation without revealing any more information than the output of the function. However, achieving this requires a full interaction among the participating parties, which is not always feasible in real life. On the other hand, in certain restricted interaction patterns it is possible for the adversary to learn the output of the function on honest inputs and every possible combination of the corrupted inputs. This motivates the study of different interaction patterns and their properties to better understand and formalize the scenarios under which we can limit the amount of information an adversary can derive.The interaction pattern that different parties participate in, to compute a function, can be modeled as a graph. This thesis studies the different properties of this graph and answers the following question - ``What is the minimum sequence of edges that are needed to ensure that an adversary cannot collude with other corrupted parties to learn different outputs of the function?". We analyze different scenarios with different bounds on the number of corrupted and output parties.
Secure Multiparty Computation (MPC) is an expression encompassing cryptographic techniques that allow mutually distrustful parties to jointly perform computations over private data, ensuring correctness and preserving privacy despite malicious behavior. Guaranteed output is the strongest security goal for MPC: protocols with this property always deliver results. This is in contrast with weaker notions that allow malicious aborts. The seminal works of Ben-Or, Goldwasser, and Wigderson (STOC’88) and Rabin and Ben-Or (STOC’89) showed interactive protocols to compute any function with guaranteed output and perfect security if fewer than one third of parties are corrupted, or with statistical security (with a small error probability) if fewer than half are corrupted. These results hold when the set of participants is fixed throughout the execution. Ostrovsky and Yung’s proactive model (PODC’91) relaxes this assumption by allowing the set of corrupted parties to evolve over time, better capturing the dynamics of long-lived computations, where machines may be periodically compromised and recovered. The recent YOSO (You Only Speak Once) and fluid MPC models (CRYPTO’21) push this ambitious modelling even further by allowing for fully dynamic participation, with parties joining and leaving the computation at will. In this setting, known protocols with guaranteed output fall short of optimal resilience or rely on non-standard communication and adversarial assumptions. Matching the classical BGW and Rabin–Ben-Or bounds in these settings remained an open problem. We resolve these questions within the Layered MPC abstraction of David et al. (CRYPTO’23), in which the interaction pattern of a protocol is restricted to be a layered graph, meaning parties are partitioned into a sequence of disjoint sets (layers) and can send private and broadcast messages to parties in immediately subsequent layers. We match the BGW and Rabin and Ben-Or bounds in this model, fully characterizing the feasibility landscape of Layered MPC with guaranteed output. As a stepping stone towards our statistically secure protocol, we construct a more efficient and conceptually simpler computationally secure protocol relying on linear non-interactive commitments. Our results yield optimally-resilient and maximally-proactive MPC protocols with guaranteed output for both perfect and statistical security.
The need for Cryptography arises out of the following fundamental question: can we perform useful computation while ensuring that an adversary does not learn anything about our private sensitive data? The notion of secure multiparty computation (MPC) \\cite{Yao82,GMW87} is a unifying framework for general secure protocols. MPC allows mutually distrusting parties to jointly evaluate any efficiently computable function on their private inputs in such a manner that each party does not learn anything beyond the output of the function. In this thesis, we study the question of building MPC protocols in various security models from standard cryptographic assumptions while minimizing the number of rounds of interaction amongst parties. In the first part of this thesis, (in a joint work with Vipul Goyal, Abhishek Jain, Yael Kalai, Dakshita Khurana and Amit Sahai, CRYPTO 2018) we construct the first round-optimal (i.e., four round) MPC protocol for general functions based on polynomially hard DDH (or QR or N
th-Residuosity) in the plain model where parties have access to no trusted setup. We further show how to overcome the four-round barrier for MPC by constructing a three-round protocol for ``list coin-tossing'' -- a slight relaxation of coin-tossing that suffices for most conceivable applications -- based on polynomially hard DDH (or QR or N
th-Residuosity). This result generalizes to randomized input-less functionalities. Previously, four round MPC protocols required sub-exponential-time hardness assumptions and no multi-party three-round protocols were known for any relaxed security notions with polynomial-time simulation against malicious adversaries. In order to build these protocols, we devise a new {\\em partitioned simulation} technique for MPC where the simulator uses different strategies for simulating the view of aborting adversaries and non-aborting adversaries. The protagonist of this technique is a new notion of {\\em promise zero knowledge} (ZK) where the ZK property only holds against non-aborting verifiers. We show how to realize promise ZK in three rounds in the simultaneous-message model assuming polynomially hard DDH (or QR or N
th-Residuosity). We also rely upon a new {\\em leveled rewinding security} technique that can be viewed as a polynomial-time alternative to leveled complexity leveraging for achieving ``non-malleability'' across different primitives. Then, we also we study the round complexity of concurrently secure multi-party computation (MPC) with super-polynomial simulation (SPS) in the plain model (in a joint work with Vipul Goyal, Abhishek Jain, Dakshita Khurana and Amit Sahai, TCC 2017). In the plain model, there are known explicit attacks that show that concurrently secure MPC with polynomial simulation is impossible to achieve; SPS security is the most widely studied model for concurrently secure MPC in the plain model. We construct a three-round concurrent MPC with SPS security against Byzantine adversaries, assuming sub-exponentially secure DDH and LWE. Prior to our work, the best known round complexity for SPS concurrent MPC was around twenty, although to the best of our knowledge, no previous work even gave an approximation of the constant round complexity that is sufficient for concurrent MPC.In the second part of the thesis, (in a joint work with Abhishek Jain, Rafail Ostrovsky and Ivan Visconti, ASIACRYPT 2018), we study the problem of non-interactive secure computation in the stateless hardware token model where parties have access to physical hardware as part of a trusted setup phase. The notion of non-interactive secure computation (NISC) first introduced in the work of Ishai et al. [EUROCRYPT 2011] studies the following problem: Suppose a receiver
R wishes to publish an encryption of her secret input
y so that any sender
S with input
x can then send a message
m that reveals
f(x,y) to
R (for some function
f). Here,
m can be viewed as an encryption of
f(x,y) that can be decrypted by
R. NISC requires security against both malicious senders and receivers, and also requires the receiver's message to be reusable across multiple computations (w.r.t. a fixed input of the receiver). All previous solutions to this problem necessarily rely upon OT (or specific number-theoretic assumptions) even in the common reference string model or the random oracle model or to achieve weaker notions of security such as super-polynomial-time simulation. In this work, we construct a NISC protocol based on the minimal assumption of one way functions, in the stateless hardware token model. Our construction achieves UC security and requires a single token sent by the receiver to the sender.
In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with perfect (information-theoretic and error-free) security at the presence of an active (aka Byzantine) rushing adversary that controls up to n/3 of the parties. We study the round complexity of general secure multiparty computation in the BGW model. Our main result shows that every functionality can be realized in only four rounds of interaction, and that some functionalities cannot be computed in three rounds. This completely settles the round-complexity of perfect actively-secure optimally-resilient MPC, resolving a long line of research. Our lower-bound is based on a novel round-reduction technique that allows us to lift existing three-round lower-bounds for verifiable secret sharing to four-round lower-bounds for general MPC. To prove the upper-bound, we develop new round-efficient protocols for computing degree-2 functionalities over large fields, and establish the completeness of such functionalities. The latter result extends the recent completeness theorem of Applebaum, Brakerski and Tsabary (TCC 2018, Eurocrypt 2019) that was limited to the binary field.
Most existing work on secure multi-party computation (MPC) ignores a key idiosyncrasy of modern communication networks, that there are a limited number of communication paths between any two nodes, many of which might even be corrupted. The problem becomes particularly acute in the information-theoretic setting, where the lack of trusted setups (and the cryptographic primitives they enable) makes communication over sparse networks more challenging. The work by Garay and Ostrovsky [EUROCRYPT’08] on almost-everywhere MPC (AE-MPC), introduced “best-possible security” properties for MPC over such incomplete networks, where necessarily some of the honest parties may be excluded from the computation. In this work, we provide a universally composable definition of almost-everywhere security , which allows us to automatically and accurately capture the guarantees of AE-MPC (as well as AE-communication, the analogous “best-possible security” version of secure communication) in the Universal Composability (UC) framework of Canetti. Our results offer the first simulation-based treatment of this important but under-investigated problem, along with the first simulation-based proof of AE-MPC. To achieve that goal, we state and prove a general composition theorem, which makes precise the level or “quality” of AE-security that is obtained when a protocol’s hybrids are replaced with almost-everywhere components.