Multiparty computation considers the design of protocols such that a set of n users U] ... lim each with their own secret input Xi, can compute a function Y =F(x], ... , x/J. In this paper, we study a requirement for devising non-interactive multiparty computation protocols and present the first non-interactive multiparty computation protocol, which has the following advantages: a) The amount of computation required by each participant is equal to the amount of computation in an ideal model (i.e. the proposed scheme is optimal). b) In the presence of passive adversaries, no set of less than n users can leam more than what is allowed in the underlying secret sharing scheme (other than the function value), c) In the presence of active adversaries (i.e, Byzantine faults are allowed), no set of less than nl2 users can either leam more than what is allowed in the underlying secret sharing scheme, nor can they dismpt the computation. d) The partial security provided in our scheme is unconditional. That is, the proposed scheme does not rely on any non-proven cryptographic assumption.
Multiparty computation considers the design of protocols such that a set of n users U] ... lim each with their own secret input Xi, can compute a function Y =F(x], ... , x/J. In this paper, we study a requirement for devising non-interactive multiparty computation protocols and present the first non-interactive multiparty computation protocol, which has the following advantages: a) The amount of computation required by each participant is equal to the amount of computation in an ideal model (i.e. the proposed scheme is optimal). b) In the presence of passive adversaries, no set of less than n users can leam more than what is allowed in the underlying secret sharing scheme (other than the function value), c) In the presence of active adversaries (i.e, Byzantine faults are allowed), no set of less than nl2 users can either leam more than what is allowed in the underlying secret sharing scheme, nor can they dismpt the computation. d) The partial security provided in our scheme is unconditional. That is, the proposed scheme does not rely on any non-proven cryptographic assumption.
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.
In secure multi-party computation n parties jointly evaluate an n-variate function f in the presence of an adversary which can corrupt up till t parties. Almost all the works that have appeared in the literature so far assume the presence of authenticated channels between the parties. This assumption is far from realistic. Two directions of research have been borne from relaxing this (strong) assumption: (a) The adversary is virtually omnipotent and can control all the communication channels in the network, (b) Only a partially connected topology of authenticated channels is guaranteed and adversary controls a subset of the communication channels in the network. This work introduces a new setting for (unconditional) secure multiparty computation problem which is an interesting intermediate model with respect to the above well studied models from the literature (by sharing a salient feature from both the above models). We consider the problem of (unconditional) secure multi-party computation when 'some' of the communication channels connecting the parties can be corrupted passively as well as actively. For this setting, some honest parties may be connected to several other honest parties via corrupted channels and may not be able to authentically communicate with them. Such parties may not be assured the canonical guarantees of correctness or privacy. We present refined definitions of security for this new intermediate model of unconditional multiparty computation. We show how to adapt protocols for (Unconditional) secure multiparty computation to realize the definitions and also argue the tightness of the results achieved by us.
We introduce and study the notion of non-interactive secure multiparty computation (NIMPC). An NIMPC protocol for a function f(x1,..., xn) is specified by a joint probability distribution R = (R1,..., Rn) and local encoding functions Enci(xi, Ri), 1 ≤ i ≤ n. Given correlated randomness (R1,..., Rn) ∈R R, each party Pi, using its input xi and its randomness Ri, computes the message mi = Enci(xi, Ri). The messagesm1,...,mn can be used to decode f(x1,..., xn). For a set T ⊆ [n], the protocol is said to be T-robust if revealing the messages (Enci(xi, Ri))i 6∈T together with the random-ness (Ri)i∈T gives the same information about (xi)i 6∈T as an oracle access to the function f restricted to these input values. Namely, a coalition T can learn no more than the restriction of f fixing the inputs of uncorrupted parties, which, in this non-interactive setting, one cannot hope to hide. For 0 ≤ t ≤ n, the protocol is t-robust if it is T-robust for every T of size at most t and it is fully robust if it is n-robust. A 0-robust NIMPC protocol for f coincides with a protocol in the private simultaneous messages model of Feige et al. (STOC 1994). In the setting of computational (indistinguishability-based) security, fully robust NIMPC is implied by multi-input functional encryption, a notion that was recently introduced by Goldwasser et al. (Euro-
Two types of generalizations in secure multi-party computation are described. First, we report on a new general adversary model: while previous protocols were designed to tolerate misbehavior of one of two types (active or passive adversaries) the new protocols tolerate mixed types of adversaries, i.e. an adversary that can corrupt players actively, passively, or can let them crash (i.e. stop execution). We derive the necessary and sufficient conditions under which such a general adversary can be tolerated. Second, we present a generic protocol framework that unifies previous approaches achieving unconditional (or information-theoretic) security and cryptographic security (i.e. security based on a cryptographic intractability assumption). This is achieved by introducing secret sharing schemes with an additional property called the multiplication property and a new type of homomorphic commitment scheme, and by generalizing the concept of commitments.
Introduction In Chapter 1 we gave an introduction to the multiparty computation problem and explained what it intuitively means for a protocol to compute a given function securely, namely, we want a protocol that is correct and private. However, we only considered three players, we only argued that a single player does not learn more than he or she is supposed to, and finally, we assumed that all players would follow the protocol. In this chapter we will consider a more general solution to multiparty computation, where we remove the first two restrictions: we will consider any number n ≥ 3 of players, and we will be able to show that as long as at most t < n /2 of the players go together after the protocol is executed and pool all their information, they will learn nothing more than their own inputs and the outputs they were supposed to receive, even if their computing power is unbounded. We will still assume, however, that all players follow the protocol. This is known as semihonest or passive security . To argue security in this chapter, we will use a somewhat weak but very simple definition that only makes sense for semihonest security. We then extend this in Chapter 4 to a fully general model of what protocols are and what security means. Throughout this chapter we will assume that each pair of players can communicate using a perfectly secure channel, so if two players exchange data, a third player has no information at all about what is sent. Such channels might be available because of physical circumstances, or we can implement them relative to a computational assumption using cryptography. For more details on this, see Chapter 7. We end the chapter by showing that the bound t < n /2 is optimal: if t ≥ n /2, then some functions cannot be computed securely in the model mentioned, that is, obtaining perfect security by using only secure point-to-point communication as the communication resource. Secret Sharing Our main tool to build the protocol will be secret-sharing schemes. The theory of secret-sharing schemes is a large and interesting field in its own right with many applications to multiparty computation (MPC), and we look at this in more detail in Chapter 11, where a formal definition of the notion as well as a general treatment of the theory of secret sharing can be found.
Current secure multiparty protocols have the following deficiency. The public transcript of the communication can be used as an involuntary commitment of the parties to their inputs and outputs. Thus parties can be later coerced by some authority to reveal their private data. Previous work that has pointed this interesting problem out contained only partial treatment. In this work we present the first general treatment of the coercion problem in secure computation. First we present a general definition of protocols that provide resilience to coercion. Our definition constitutes a natural extension of the general paradigm used for defining secure multiparty protocols. Next we show that if trapdoor permutations exist then any function can be incoercibly computed (i.e., computed by a protocol that provides resilience to coercion) in the presence of computationally bounded adversaries and only public communication channels. This holds as long as less than half the parties are coerced (or corrupted). In particular, ours are the first incoercible protocols without physical security assumptions. Also, our protocols constitute an alternative solution to the recently solved adaptive security problem. Our techniques are quite surprising and include non-standard use of deniable encryptions.