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.
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.
We prove two classes of lower bounds on the communication complexity of information-theoretically secure multiparty computation. The first lower bound applies to perfect passive secure multiparty computation in the standard model with n = 2t+1 parties of which t are corrupted. We show a lower bound that applies to secure evaluation of any function, assuming that each party can choose to learn or not learn the output. Specifically, we show that there is a function H^* such that for any protocol that evaluates y_i = b_i ⋅ f(x₁,...,x_n) with perfect passive security (where b_i is a private boolean input), the total communication must be at least 1/2 ∑_{i = 1}ⁿ H_f^*(x_i) bits of information. The second lower bound applies to the perfect maliciously secure setting with n = 3t+1 parties. We show that for any n and all large enough S, there exists a reactive functionality F_S taking an S-bit string as input (and with short output) such that any protocol implementing F_S with perfect malicious security must communicate Ω(nS) bits. Since the functionalities we study can be implemented with linear size circuits, the result can equivalently be stated as follows: for any n and all large enough g ∈ ℕ there exists a reactive functionality F_C doing computation specified by a Boolean circuit C with g gates, where any perfectly secure protocol implementing F_C must communicate Ω(n g) bits. The results easily extends to constructing similar functionalities defined over any fixed finite field. Using known techniques, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor lg n off for Boolean circuits). Both results also extend to the case where the threshold t is suboptimal. Namely if n = kt+s the bound is weakened by a factor O(s), which corresponds to known optimizations via packed secret-sharing.
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 Multiparty Computation (abrv. MPC) is a group of techniques that enable multiple entities to compute some function on their private inputs. Moreformally,itenablesasetofplayers{P1,...,Pn},eachofthemholding private inputs xi, where i is the index of the player, to evaluate a function f(x1,...,xn) = (y1,...,yn) so that every player Pi learns yi. Multiparty Computation has many application scenarios such as private auctioning, computation outsourcing, or private information retrieval. These and other applications make MPC a very appealing object of study, since it may be a solution to problems in different fields. The objective of this thesis is twofold. First, we aim to provide a comprehensive guide to the current state of multiparty computation protocols. Wedosobyinspectingthetwocategorieswheremostgeneralfunctionality secure function evaluation protocols are inserted - boolean or arithmetic circuit evaluation. Moreover, we show how to implement MPC protocols with current constructions, and what problems are inherently connected to the chosen representations. Second, we document some of the design choices behind a partial implementation of a concrete secure arithmetic circuit evaluation protocol - the SPDZ protocol by Damgård et al. [10]. We explain the protocol in general terms, and then go into the details of some subprotocols, namely those that were implemented.
Introduction In this chapter we will show how the protocols we have seen so far can be generalized to be based on general linear secret-sharing schemes. Doing this generalization has several advantages: first, it allows us to design protocols that protect against general adversary structures, a concept we explain later, and second, it allows us to consider protocols in which the field that is used in defining the secret-sharing scheme can be of size independent of the number of players. This turns out to be an advantage for the applications of multiparty computation (MPC) that we consider later but cannot be done for the protocols that we have seen so far: to use Shamir's scheme for n players based on polynomials as we have seen, the field must be of size at least n +1. For now, we will only consider the theory for linear secret sharing that we need to construct the protocols in this chapter. However, we note already that to get full mileage from the more general applications of secret sharing and MPC, we need additional theory, in particular, about the asymptotic behavior of secret-sharing schemes. This material can be found in Chapter 11. General Adversary Structures The corruption tolerance of the protocols that we have seen so far has been characterized by only a single number t , the maximal number of corruptions that can be tolerated. This is also known as the threshold-t model . One way to motivate this might be to think of corruption of a player as something that requires the adversary to invest some amount of resource, such as time or money. If the adversary has only bounded resources, there should be a limit on the corruptions he or she can do. However, characterizing this limit by only an upper bound implicitly assumes that all players are equally hard to corrupt. In reality, this may be completely false: some players may have much better security than others, so a more realistic model might be that the adversary can corrupt a small number of well-protected players or a large number of poorly protected players. However, the threshold model does not allow us to express this.
While classically cryptography is concerned with the problem of private communication among two entities, say players, in modern cryptography multi-player protocols play an important role.And among these, it is probably fair to say that secret sharing, and its stronger version verifiable secret sharing (VSS), as well as multi-party computation (MPC) belong to the most appealing and/or useful ones.The former two are basic tools to achieve better robustness of cryptographic schemes against malfunction or misuse by "decentralizing" the security from one single to a whole group of individuals (captured by the term threshold cryptography).The latter allows-at least in principle-to execute any collaboration among a group of players in a secure way that guarantees the correctness of the outcome but simultaneously respects the privacy of the participants.In this work, we study three aspects of secret sharing, VSS and MPC, which we denote by fundamentals, generality, and efficiency.By fundamentals we mean the quest for understanding why a protocol works and is secure in abstract (and hopefully simple) mathematical terms.By generality we mean generality with respect to the underlying mathematical structure, in other words, minimizing the mathematical axioms required to do some task.And efficiency of course deals with the improvement of protocols with respect to some meaningful complexity measure.We briefly summarize our main results.(1) We give a complete characterization of blackbox secret sharing in terms of simple algebraic conditions on the integer sharing coefficients, and we propose a black-box secret sharing scheme with minimal expansion factor.Note that, in contrast to the classical field-based secret sharing schemes, a black-box secret sharing scheme allows to share a secret sampled from an arbitrary Abelian group and requires only black-box access to the group operations and to random group elements.Such a scheme may be very useful in the construction of threshold cryptosystems based on groups with secret order (like RSA).(2) We show that without loss of efficiency, MPC can be based on arbitrary finite rings.This is in sharp contrast to the literature where essentially all MPC protocols require a much stronger mathematical structure, namely a field.Apart from its theoretical value, this can lead to efficiency improvements since it allows a greater freedom in the (mathematical) representation of the task that needs to be securely executed.(3) We propose a unified treatment of perfectly secure linear VSS and distributed commitments (a weaker version of the former), and we show that the security of such a scheme can be reduced to a linear algebra condition.The security of all known schemes follows as corollaries whose proofs are pure linear algebra arguments, in contrast v to some hybrid arguments used in the literature.(4) We construct a new unconditionally secure VSS scheme with minimized reconstruction complexity in the setting of a dishonest minority.This improves on the reconstruction complexity of the previously best known scheme without affecting the (asymptotic) complexity of the sharing phase.In the context of MPC with pre-processing, our scheme allows to improve the computation phase of earlier protocols without increasing the complexity of the pre-processing.(5) Finally, we consider commitment multiplication proofs, which allow to prove a multiplicative relation among three commitments, and which play a crucial role in computationally secure MPC.We study a non-interactive solution which works in a distributed-verifier setting and essentially consists of a few executions of Pedersen's VSS.We simplify and improve the protocol, and we point out a (previously overlooked) property which helps to construct non-interactive proofs of partial knowledge in this setting.This allows for instance to prove the knowledge of ℓ out of m given secrets, without revealing which ones.We also construct a noninteractive distributed-verifier proof of circuit satisfiability, which-in principle-allows to prove anything that can be proven without giving away the proof.
Multiparty computation (MPC) is a powerful and generic cryptographic framework capable of realizing essentially any cryptographic task (functionality) while preserving privacy and robustness. In the MPC model, a group of mutually distrustful parties seek to jointly compute a function f of their privately held inputs x1, ..., xn, while revealing no information about those inputs beyond what is entailed by the function output(s). Some portion of these players may be corrupted, controlled by a centralized adversary who directs their (mis)behavior and seeks to gain information on private inputs or to disrupt the protocol execution.
In this work, we examine the resource requirements of information-theoretically secure multiparty computation. In particular, we look at trade-offs involving what we call assumptions, by which we mean two aspects of the model's setup: (1) the extent to which parties are connected by secure, pairwise communication channels; and (2) the usage (as a black box) of a channel—a primitive which enforces consistency among views by allowing a single party to send a message to all other parties which is guaranteed to be consistent, even if the broadcaster is corrupted.
Part I of this work focuses on the first network-model assumption, that of the graph's connectivity by pairwise channels. We show upper and lower bounds on communication complexity in the Secure Message Transmission with Public Discussion (SMT-PD) model, as a function of the threshold of corrupted parties. The SMT-PD model, which abstracts the problem of secure communication over a partially connected network, includes two components: a public and a set of simple channels. We show significant improvements in both areas: on the channel, we reduce communication to logarithmic in terms of the message's bit-length m, where the previous best result was linear in m; on the simple channels, we reduce from O(mn) to O(mn/(n−t)), where n is the number of simple channels and t is a bound on the number of corrupted channels. Using tools from information theory, we show this amount of simple-wire communication is essentially optimal. Finally, we give an amortized solution which drastically improves communication over channel when the protocol is repeated many times sequentially.
Part II shifts focus to the second network-model assumption, the use of an atomic broadcast primitive. Here we show that three broadcast rounds suffice for general secure computation, while two broadcast rounds are necessary. In particular we show that even for the natural and important functionality of Weak Secret Sharing—a type of distributed commitment—there is no protocol which uses only a single broadcast and achieves better than an explicit constant probability of success (so the protocol's success cannot be a function of a security parameter).