Secure multi-party computation (MPC) enables mutually distrusting parties to compute functions over private inputs without revealing additional information. A general MPC protocol is the one that can be used to securely compute any function. General MPC requires either an honest majority or oblivious transfer, which can be provided via computational assumptions, a black-box hybrid, or trusted hardware. However, in the setting of dishonest majority, there are still many tasks that can be computed securely in the information-theoretic plain model without relying on oblivious transfer or any other computational hardness assumptions. Such protocols are perfectly secure, fast, and do not require any setup or preprocessing.This thesis investigates the feasibility and complexity of secure two-party computation, which inherently falls under the dishonest majority setting, with randomized output in the information-theoretic plain model against honest-but-curious adversaries. For deterministic output functions, seminal work by Chor, Kushilevitz, and Beaver provided a complete characterization of which computations admit secure protocols. In contrast, randomized functionalities give rise to a substantially richer landscape, where questions of round complexity, communication complexity, and even decidability have remained unresolved for decades.The thesis develops a geometric framework for analyzing secure computation by encoding candidate private-coin secure protocols for a given functionality as points in high-dimensional spaces. Within this representation, the space of all secure protocols forms recursively defined geometric sets whose structure can be studied using tools from real algebraic geometry and convex analysis. This perspective enables feasibility, search, and optimization problems in secure computation to be reduced to structural properties of these sets.Using this framework, the thesis establishes that determining whether a given two-party functionality with randomized output admits a secure protocol is decidable. A finite procedure is provided that either constructs a secure protocol with optimal round and communication complexity or identifies a geometric obstruction to security, resolving a foundational open problem in secure computation and information complexity. These results rely on showing that certain lamination hulls arising in the analysis are semi-algebraic, which is achieved by reducing the problem to solving systems of linear inequalities over convex sets. To this end, the thesis introduces a Gaussian-elimination-inspired algorithm and a new set operator, the positive geometric join, leading to a class of algebraically well-behaved geometric objects called hemihedra.The thesis also studies the round and communication complexity of secure computation with randomized output and disproves a longstanding folklore conjecture asserting that round complexity depends only on the cardinalities of the input and output domains. Explicit constructions demonstrate the existence of securely realizable functions with arbitrarily high round complexity, even for fixed size inputs and outputs, while matching upper bounds are proved for small output alphabets. These results reveal a close connection between secure computation and lamination hulls originally studied in hydrodynamics, highlighting unexpected geometric structure underlying information-theoretic security.
Secure multi-party computation (MPC) enables mutually distrusting parties to compute functions over private inputs without revealing additional information. A general MPC protocol is the one that can be used to securely compute any function. General MPC requires either an honest majority or oblivious transfer, which can be provided via computational assumptions, a black-box hybrid, or trusted hardware. However, in the setting of dishonest majority, there are still many tasks that can be computed securely in the information-theoretic plain model without relying on oblivious transfer or any other computational hardness assumptions. Such protocols are perfectly secure, fast, and do not require any setup or preprocessing.This thesis investigates the feasibility and complexity of secure two-party computation, which inherently falls under the dishonest majority setting, with randomized output in the information-theoretic plain model against honest-but-curious adversaries. For deterministic output functions, seminal work by Chor, Kushilevitz, and Beaver provided a complete characterization of which computations admit secure protocols. In contrast, randomized functionalities give rise to a substantially richer landscape, where questions of round complexity, communication complexity, and even decidability have remained unresolved for decades.The thesis develops a geometric framework for analyzing secure computation by encoding candidate private-coin secure protocols for a given functionality as points in high-dimensional spaces. Within this representation, the space of all secure protocols forms recursively defined geometric sets whose structure can be studied using tools from real algebraic geometry and convex analysis. This perspective enables feasibility, search, and optimization problems in secure computation to be reduced to structural properties of these sets.Using this framework, the thesis establishes that determining whether a given two-party functionality with randomized output admits a secure protocol is decidable. A finite procedure is provided that either constructs a secure protocol with optimal round and communication complexity or identifies a geometric obstruction to security, resolving a foundational open problem in secure computation and information complexity. These results rely on showing that certain lamination hulls arising in the analysis are semi-algebraic, which is achieved by reducing the problem to solving systems of linear inequalities over convex sets. To this end, the thesis introduces a Gaussian-elimination-inspired algorithm and a new set operator, the positive geometric join, leading to a class of algebraically well-behaved geometric objects called hemihedra.The thesis also studies the round and communication complexity of secure computation with randomized output and disproves a longstanding folklore conjecture asserting that round complexity depends only on the cardinalities of the input and output domains. Explicit constructions demonstrate the existence of securely realizable functions with arbitrarily high round complexity, even for fixed size inputs and outputs, while matching upper bounds are proved for small output alphabets. These results reveal a close connection between secure computation and lamination hulls originally studied in hydrodynamics, highlighting unexpected geometric structure underlying information-theoretic security.
What is the round and communication complexity of secure computation? The seminal results of Chor-Kushilevitz-Beaver (STOC-1989, FOCS-1989, DIMACS-1989) answer this question for computations with deterministic output. However, this question has remained unanswered for computations with randomized output. Our work answers this question for two-party secure function evaluation functionalities. We introduce a geometric encoding of all candidate secure protocols for a given computation as points in a high-dimensional space. The following results follow by analyzing the properties of these sets of points.1)It is decidable to determine if a given computation has a secure protocol within round or communication constraints.2)We construct one such protocol if it exists.3)Otherwise, we present an obstruction to achieving security.Our technical contributions imply new information complexity bounds for secure computation.
Secure Multiparty Computation (MPC) allows a set of parties, each having its own private data, to compute a function of their joint data such that the parties only learn the output of this function and everything else about their data is hidden. MPC is a fundamental cryptographic abstraction that captures many other natural cryptographic primitives as special cases. It also has a wide range of practical applications such as conducting secure electronic auctions, delegating sensitive computation to untrusted cloud service providers, secure computation on genomic data and training machine learning models on private data.A long-standing open problem in this area is to construct MPC protocols that have {\\it optimal} (two-round) round complexity under the {\\it weakest} possible cryptographic hardness assumptions.We {\\it completely resolve} this problem by showing lower bounds and matching upper bounds on the hardness assumptions required for constructing round-optimal MPC. Specifically, we obtain the following results.\\begin{itemize}\\item \\textbf{Black-Box Separation.} We show that there exists no construction of two-round semi-honest MPC protocol for general functions that makes black-box use of a two-round oblivious transfer. As a corollary, a similar separation holds when starting with any 2-party functionality other than oblivious transfer. \\item \\textbf{Non-Black-Box Construction.} We show that the above negative result can be bypassed by making non-black-box use of a two-round oblivious transfer. Specifically, starting from a semi-honest (resp. malicious) secure two-round oblivious transfer protocol, we construct a two-round MPC protocol against semi-honest (resp. malicious) adversaries. \\end{itemize}Since any two-round MPC protocol for general functionalities implies a two-round oblivious transfer as a special case, the above two results show that non-black-box use of oblivious transfer is {\\it necessary and sufficient} to construct round-optimal MPC protocols.
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 Nth-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 Nth-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 Nth-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.
Secure Multi-Party Computation (MPC) protocols allow a group of mutually distrusting users to compute a function jointly on their inputs without revealing any information beyond the output. For many years, implementations of MPC protocols have targeted security against semi-honest adversaries, i.e., attackers are assumed to execute the protocol honestly but try to learn private information after the fact. Protocols secure against stronger and more realistic malicious adversaries, who could behave arbitrarily during the protocol execution, were known to exist but were much less efficient. This thesis introduces a new paradigm to construct extremely efficient MPC protocols with malicious security. In particular, this thesis consists of three major contributions. 1. We introduce the authenticated garbling framework, and present an efficient concrete instantiation of the protocol. The resulting protocol partially closes the gap between semi-honest and malicious MPC protocols asymptotically; the implementation of the protocol represents the state-of-the-art system for malicious two-party computation. 2. We discuss how to apply authenticated garbling to the multi-party setting, where all-but-one parties can be corrupted by the adversary. The resulting protocol improves upon the best previous constant-round protocol by orders of magnitude. We also present a system that, for the first time, enables MPC executions among hundreds of parties, distributed globally. 3. We present a series of optimizations to two-party authenticated garbling by interpreting authenticated garbling in a new way. The improved malicious protocol has essentially the same concrete efficiency as the best semi-honest protocol in the preprocessing model. 4. We develop these protocols in EMP-toolkit, a practical and efficient MPC tool that can be used to build new protocols and to develop applications using our existing protocols.
We show that any multiparty functionality can be evaluated using a 2-round protocol with perfect correctness and perfect semihonest security, provided that the majority of parties are honest. This settles the round complexity of information-theoretic semihonest multiparty computation, resolving a longstanding open question [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294--304]. The protocol is efficient for NC1 functionalities. Furthermore, given black-box access to a one-way function, the protocol can be made efficient for any polynomial functionality, at the cost of only guaranteeing computational security. Our results are based on a new notion of multiparty randomized encoding which extends and relaxes the standard notion of randomized encoding of functions [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294--304]. The property of a multiparty randomized encoding (MPRE) is that if the functionality g is an encoding of the functionality f, then for any (permitted) coalition of players, their respective outputs and inputs in g allow them to simulate their respective inputs and outputs in f, without learning anything else, including the other outputs of f. We further introduce a new notion of effective degree, and show that the round complexity of a functionality f is characterized by the degree of its MPRE. We construct degree-2 MPREs for general functionalities in several settings under different assumptions, and use these constructions to obtain 2-round protocols. Our constructions also give rise to new protocols in the client-server model with optimal round complexity.
In the setting of secure multiparty computation, several distrustful parties wish to carry out a distributed computing task on their local private data while satisfying several security properties such as correctness, privacy, independence of inputs and fairness. The aim of secure multiparty computation (MPC) is to enable the parties to carry out the computation in a secure manner, eliminating any attempt of an adversarial entity to harm the execution. The concept of secure computation is very general and fundamental in cryptography, and models any distributed computing task, including simple computations as coin-tossing and broadcast, as well as more complex tasks such as electronic auctions and anonymous transactions. In this thesis, we study two foundational aspects of secure computation: perfect security and fairness. In the first part of this thesis, we study perfect security in secure computation. A protocol that is perfectly secure cannot be broken even when the adversary has unlimited computational power and its security holds unconditionally. One of the most fundamental results of secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. When the adversary is semi-honest this holds as long as t < n/2 parties are corrupted, and when the adversary is malicious this holds as long as t < n/3 parties are corrupted. Unfortunately, a full proof of these results was never published. In this thesis, we remedy this situation and provide a full proof of security of the BGW protocol. This also includes a full description of the protocol for the malicious setting. In addition to the above, we observe that by some simple and natural modifications, the BGW protocol can be significantly simplified and one of its expensive (and perhaps most complicated) subprotocols can be saved. We present a new multiplication protocol that is based on the original construction, but is simpler and achieves higher efficiency. In the second part of this thesis, we study fairness in secure two party computation. Informally, the fairness property guarantees that if one party receives its output, then the other party does too. The well-known impossibility result of Cleve (STOC 1986) implies that, in general, it is impossible to securely compute a function with complete fairness without an honest majority. Until recently, the accepted belief has been that nothing non-trivial can be computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist some non-trivial (deterministic, finite-domain) Boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. We focus on this question and give both positive and negative results. We first characterize