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.
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 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.
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.
We revisit the exact round complexity of secure computation in the multi-party and two-party settings. For the special case of two-parties without a simultaneous message exchange channel, this question has been extensively studied and resolved. In particular, Katz and Ostrovsky CRYPTO '04 proved that 5 rounds are necessary and sufficient for securely realizing every two-party functionality where both parties receive the output. However, the exact round complexity of general multi-party computation, as well as two-party computation with a simultaneous message exchange channel, is not very well understood.
These questions are intimately connected to the round complexity of non-malleable commitments. Indeed, the exact relationship between the round complexities of non-malleable commitments and secure multi-party computation has also not been explored.
In this work, we revisit these questions and obtain several new results. First, we establish the following main results. Suppose that there exists a k-round non-malleable commitment scheme, and let k′=max4,k+1k'=max4,k+1; then,Two-party setting with simultaneous message transmission: there exists a k′k'-round protocol for securely realizing every two-party functionality;Multi-party setting: there exists a k′k'-round protocol for securely realizing the multi-party coin-flipping functionality.
As a corollary of the above results, by instantiating them with existing non-malleable commitment protocols from the literature, we establish that four rounds are both necessary and sufficient for both the results above. Furthermore, we establish that, for every multi-party functionalityfive rounds are sufficient.
We actually obtain a variety of results offering trade-offs between rounds and the cryptographic assumptions used, depending upon the particular instantiations of underlying protocols.
In STOC’05, von Ahn, Hopper and Langford introduced the notion of covert computation. In covert computation, a party runs a secure computation protocol over a covert (or steganographic) channel without knowing if the other parties are participating as well or not. At the end of the protocol, if all parties participated in the protocol and if the function output is “favorable ” to all parties, then the output is revealed (along with the fact that everyone participated). All covert computation protocols known so far require a large polynomial number of rounds. In this work, we first study the question of the round complexity of covert computation and obtain the following results: • There does not exist a constant round covert computation protocol with respect to black box simulation even for the case of two parties. (In comparison, such protocols are known even for the multi-party case if there is no covertness requirement.) • By relying on the two slot non-black-box simulation technique of Pass (STOC’04) and techniques from cryptography in NC 0 (Applebaum et al, FOCS’04), we obtain a construction of a constant round covert multi-party computation protocol. Put together, the above adds one more example to the growing list of tasks for which non-black-box simulation techniques (introduced in the work of Barak in FOCS’01) are necessary. Finally, we study the problem of covert multi-party computation in the setting where the parties only have point to point (covert) communication channels. We observe that our covert computation protocol for the broadcast channel inherits, from the protocol of Pass, the property of secure composition in the bounded concurrent setting. Then, as an application of this protocol, somewhat surprisingly we show the existence of covert multi-party computation with point to point channels (assuming that the number of parties is a constant). 0 1
In STOC'05, von Ahn, Hopper and Langford introduced the notion of covert computation. In covert computation, a party runs a secure computation protocol over a covert (or steganographic) channel without knowing if the other parties are participating as well or not. At the end of the protocol, if all parties participated in the protocol and if the function output is "favorable" to all parties, then the output is revealed (along with the fact that everyone participated). All covert computation protocols known so far require a large polynomial number of rounds. In this work, we first study the question of the round complexity of covert computation and obtain the following results: There does not exist a constant round covert computation protocol with respect to black box simulation even for the case of two parties. (In comparison, such protocols are known even for the multi-party case if there is no covertness requirement.) By relying on the two slot non-black-box simulation technique of Pass (STOC'04) and techniques from cryptography in NC0 (Applebaum et al, FOCS'04), we obtain a construction of a constant round covert multi-party computation protocol.
The notion of secure computation is central to cryptography. Introduced in the seminal works of Yao [FOCS'82, FOCS'86] and Goldreich, Micali and Wigderson [STOC'87], secure multiparty computation allows a group of (mutually) distrustful parties to jointly compute any functionality over their individual private inputs in such a manner that the honest parties obtain the correct outputs and no group of malicious parties learn anything beyond their inputs and the prescribed outputs. General feasibility results for secure computation were given by Yao [FOCS'86] and Goldreich et al. [STOC'87] more than two decades ago. Subsequent to these works, designing secure computation protocols that can tolerate more powerful adversaries and satisfy stronger notions of security has been a very active area of research. In this dissertation, we study two such new frontiers in the area of secure computation.
In the first part of this dissertation, we initiate a study of designing leakage-resilient interactive protocols. Specifically, we consider the scenario where an adversary, in addition to corrupting a subset of parties, can leak (potentially via physical attacks) arbitrary information from the secret state of any honest party. This is in contrast to the standard notion of secure computation where it is assumed that the adversary only has black-box'' access to the honest parties. In particular, we formalize a meaningful definition of leakage-resilient zero knowledge proof systems and provide constructions that satisfy our notion. We also discuss various applications of our results.
The second part of this dissertation concerns with the general question of whether it is possible to securely run cryptographic protocols over an insecure network environment such as the Internet. It is well-known that the standard notion of secure computation is only relevant to the stand-alone setting where a single protocol is being executed in isolation; as such it does not guarantee security when multiple protocol sessions may be executed concurrently under the control of an adversary who is present across all sessions. We consider the open problem of constructing secure password-based authenticated key exchange protocols in such a setting in the plain model (i.e., without assuming any trusted infrastructure or random oracles). We give the first construction of such a protocol based on standard cryptographic assumptions. Our results are in fact much more general, and extend to other functionalities w.r.t. a (necessarily) weakened notion of concurrently secure computation.
The results presented in this dissertation stem from two papers which are joint works with Sanjam Garg and Amit Sahai, and with Vipul Goyal and Rafail Ostrovsky, respectively.