Secure multi-party computation allows mutually distrusting parties to compute securely over their private data. However, even in the semi-honest two-party setting, most interesting functions cannot be computed securely in the information-theoretic plain model. Intuitively, the objective of accurately evaluating the output of such functions is inherently inimical to the privacy concerns of the parties. Securely evaluating OR of the input bits of two parties is the simplest example, and captures the essence of the hardness in securely evaluating most functions. This work studies the interplay between accuracy and privacy of secure 2-party function evaluation in the information-theoretic plain model. We provide an optimal accuracy versus privacy tradeoff for computing OR(x, y), where x and y are, respectively, the private input bits of Alice and Bob. In particular, we construct a round-optimal two-party protocol for OR that has maximum semi-honest security in the information-theoretic plain model. Prior results exhibit only weak tradeoffs that are far from the optimal. We generalize our techniques to obtain a tight accuracy-versus-privacy tradeoff characterization for a stronger notion of security, namely differentially-private semi-honest security. The technical heart of our result is a new technique to derive inequalities for distributions of transcripts generated by protocols. This approach reduces the domain of the optimization problem from an unbounded number of transcripts to a constant size while preserving the optimal solution to the original problem. We believe that these techniques for analyzing protocols in the information-theoretic plain model will be of independent interest.
We consider the problem of private function evaluation (PFE) in the two-party setting. Here, informally, one party holds an input x while the other holds a circuit describing a function f; the goal is for one (or both) of the parties to learn f(x) while revealing nothing more to either party. In contrast to the usual setting of secure computation — where the function being computed is known to both parties — PFE is useful in settings where the function (i.e., algorithm) itself must remain secret, e.g., because it is proprietary or classified. It is known that PFE can be reduced to standard secure computation by having the parties evaluate a universal circuit, and this is the approach taken in most prior work. Using a universal circuit, however, introduces additional overhead and results in a more complex implementation. We show here a completely new technique for PFE that avoids universal circuits, and results in constant-round protocols with communication/computational complexity linear in the size of the circuit computing f. This gives the first constant-round protocol for PFE with linear complexity (without using fully homomorphic encryption), even restricted to semi-honest adversaries. 1
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.
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.
The goal of secure two-party computation is to enable two parties to cooperatively evaluate a function that takes private data from both parties as input without exposing any of the private data. At the end of the computation, the participants learn nothing more than the output of the function. The two-party secure computation systems have three properties: (1) the application involves inputs from two independent parties; (2) each party wants to keep its own data secret; and (3) the participants agree to reveal the output of the computation. That is, the result itself does not imply too much information about either party's private input. Informally, the security requirements are that nothing is learned from the protocol other than the output (privacy), and that the output is distributed according to the prescribed functionality (correctness). The threat models in the two-party computation assume the presence of three different types of adversaries: 1) Semi honest, 2) Malicious and 3) Covert.
The purpose of secure multi-party computation is to enable protocol participants to compute a public function of their private inputs while keeping their inputs secret, without resorting to any trusted third party. However, opening the public output of such computations inevitably reveals some information about the private inputs. We propose a measure generalizing both Rényi entropy and g -entropy so as to quantify this information leakage. In order to control and restrain such information flows, we introduce the notion of function substitution, which replaces the computation of a function that reveals sensitive information with that of an approximate function. We exhibit theoretical bounds for the privacy gains that this approach provides and experimentally show that this enhances the confidentiality of the inputs while controlling the distortion of computed output values. Finally, we investigate the inherent compromise between accuracy of computation and privacy of inputs and we demonstrate how to realize such optimal trade-offs.
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.