We show that any function f can be securely evaluated by a protocol with ballots and a ballot box. That is, n mutually suspicious players, each player i possessing a secret input xi, can use ballots and ballot boxes to jointly evaluate f(x1,..., xn) = (y1,..., yn), so that (no matter how many players may collude and deviate from their prescribed instructions, and no matter how long they compute!) each player i learns exactly yi with the same privacy and correctness as if all players privately handed their secret inputs to a trusted party, who privately evaluates f and privately returns yi to each player i. Our protocol is (1) efficient, (2) enjoys perfect privacy, (3) guarantees perfect correctness, (4) is universally composable in the sense of [DoMi00] and [Can01], and (5) is always collusion-free in the sense of [LMS05], even for games with secret actions. 1 Main Theorem For any function f, mapping n private inputs to a single public output, there exists an n party protocol for a ballot-box network with public opening that securely evaluates f. We now procedure to define (1) a ballot-box network, (2) a ballot-box network with public opening and (3) the notion of securely evaluating a function. In a subsequent version of this work, we will provide a proof of our main theorem, generalize our results to functions with n inputs and n outputs and explore applications to economic mechanisms.
We show that any function f can be securely evaluated by a protocol with ballots and a ballot box. That is, n mutually suspicious players, each player i possessing a secret input xi, can use ballots and ballot boxes to jointly evaluate f(x1,..., xn) = (y1,..., yn), so that (no matter how many players may collude and deviate from their prescribed instructions, and no matter how long they compute!) each player i learns exactly yi with the same privacy and correctness as if all players privately handed their secret inputs to a trusted party, who privately evaluates f and privately returns yi to each player i. Our protocol is (1) efficient, (2) enjoys perfect privacy, (3) guarantees perfect correctness, (4) is universally composable in the sense of [DoMi00] and [Can01], and (5) is always collusion-free in the sense of [LMS05], even for games with secret actions. 1 Main Theorem For any function f, mapping n private inputs to a single public output, there exists an n party protocol for a ballot-box network with public opening that securely evaluates f. We now procedure to define (1) a ballot-box network, (2) a ballot-box network with public opening and (3) the notion of securely evaluating a function. In a subsequent version of this work, we will provide a proof of our main theorem, generalize our results to functions with n inputs and n outputs and explore applications to economic mechanisms.
It seems to be a generally acknowledged fact that you should never trust a computer and that you should trust the person operating the computer even less. This in particular becomes a problem when the party that you do not trust is one which is separated from you and is one on which you depend, e.g. because that party is the holder of some data or some capability that you need in order to operate correctly. How do you perform a given task involving interaction with other parties while allowing these parties a minimal influence on you and, if privacy is an issue, allowing them to learn as little about you as possible. This is the general problem of secure multiparty computation. The usual way of formalizing the problem is to say that a number of parties who do not trust each other wish to compute some function of their local inputs, while keeping their inputs as secret as possible and guaranteeing the correctness of the output. Both goals should be obtained even if some parties stop participating or some malevolent coalition of the parties start deviating arbitrarily from the agreed protocol. The task is further complicated by the fact that besides their mutual distrust, nor do the parties trust the channels by which they communicate. A general solution to the secure multiparty computation problem is a compiler which given any feasible function describes an efficient protocol which allows the parties to compute the function securely on their local inputs over an open network. Over the past twenty years the secure multiparty computation problem has been the subject of a large body of research, both research into the models of multiparty computation and research aimed at realizing general secure multiparty computation. The main approach to realizing secure multiparty computation has been based on verifiable secret sharing as computation, where each party holds a secret share of each input and during the execution computes secret shares of all intermediate values. This approach allows the parties to keep all inputs and intermediate values secret and to pool the shares of the output values to learn exactly these values. More recently an approach based on joint homomorphic encryption was introduced, allowing for an efficient realization of general multiparty computation secure against an eavesdropper. A joint encryption scheme is an encryption scheme where all parties can encrypt, but where it takes the participation of all parties to open an encryption. The computation then starts by all parties broadcasting encryptions of their inputs and progresses through computing encryptions of the intermediary values using the homomorphic properties of the encryption scheme. The encryptions of the outputs can then be jointly decrypted. In this dissertation we extend this approach by using threshold homomorphic encryption to provide full-fledged security against an active attacker which might control some of the parties and which might take over parties during the course of the protocol execution. As opposed to a joint encryption scheme a threshold encryption scheme only requires that a given number of the parties are operating correctly for decryption to be possible. In this dissertation we show that threshold homomorphic encryption allows to solve the secure general multiparty computation problem more efficiently than previous approaches to the problem. Starting from an open point-to-point network there is a long way to general secure multiparty computation. The dissertation contains contributions at several points along the way. In particular we investigate how to realize secure channels. We also show how threshold signature schemes can be used to efficiently realize a broadcast channel and how threshold cryptography can be used to provide the parties of the network with a source of shared randomness. All three tools are well-known to be extremely powerful resources in a network, and our principle contribution is to provide efficient realizations. The dissertation also contains contributions to the definitional part of the field of multiparty computation. Most significantly we augment the recent model of universally composable security with a formal notion of what it means for a protocol to only realize a given problem under a given restricted input-output behavior of the environment. This e.g. allows us to give the first specification of a universally composable zero-knowledge proof of membership which does not at the same time require the proof system to be a proof of knowledge.
Secure protocols attempt to minimize the injuries to privacy and correctness inflicted by malicious participants who collude during run-time. They do not, however, prevent malicious parties from colluding and coordinating their actions in the first place!Eliminating such collusion of malicious parties during the execution of a protocol is an important and exciting direction for research in Cryptography. We contribute the first general result in this direction: (1) We provide a rigorous definition of what a collusion-free protocol is; and (2) We prove that, under standard physical and computational assumptions ---i.e., plain envelopes and trapdoor permutations---collusion-free protocols exist for all finite protocol tasks with publicly observable actions. (Note that such tasks are allowed to have secret global state, and thus include Poker, Bridge, and other such games.Our solution is tight in the sense that, for a collusion-free protocol to exist, each of (a) the finiteness of the game of interest, (b) the public observability of its actions, and (c) the use of some type of physically private channel is provably essential.
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.
At present, research on secure multi-party computation is of great interest in modern cryptography. It should be acknowledged that if any function can be computed securely, then it results in a very powerful tool. In fact, all natural protocols are, or can be rephrased to be, special cases of the multi-party computation problems. Design and analysis of the special multi-party computation protocols is meaningful and has attracted much interest in this field. Based on the combination of a public-key cryptosystem of the homomorphic encryption and on the theoretic construction relying on the F-hiding assumption, a protocol for comparing information of equality is proposed. The protocol needs only a single round of interaction and ensures fairness, efficiency and security. The protocol is fair, which means that one party knows the sound result of the comparison if and only if the other one knows the result. The protocol is efficient with the help of an oblivious third party for calculating. However, the third party cannot learn any information about the participant抯 private inputs and even about the comparison result, and cannot collude with any participant. The protocol is secure for the two participants, that is, any information about their secret input will not leak except the final computation result. A precise proof of security of the protocol is presented. Applications of this protocol may include private bidding and auctions, secret ballot elections, commercial business, identification in a number of scenarios and so on. It is believed that the protocol may be of practical significance for electronic transaction.
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.
Abstract. In this note, we report on the first large-scale and practical application of multiparty computation, which took place in January 2008. We also report on the novel cryptographic protocols that were used. 1 Introduction and History In multiparty computation (MPC), we consider a number of players P1,..., Pn, who initially each hold inputs x1,..., xn, and we then want to securely compute some function f on these inputs, where f(x1,..., xn) = (y1,..., yn), such that Pi learns yi but no other information. This should hold, even if players exhibit some amount of adversarial behavior. The goal can be accomplished by an interactive