Introduction The protocol we described in Chapter 3 is perfectly correct and perfectly private, but it cannot tolerate that any of the parties deviate from the protocol. In later chapters we will present protocols that are correct and private even if some parties do not follow the protocol. Such protocols are called robust. Before we can prove that these protocols are robust, we need a good definition of what we mean by that. In this section we will describe a security model for cryptographic protocols known as the UC model. Here UC stands for universally composable . The name was adopted because a protocol proven secure in this model remains secure regardless of the context in which it is used. In other words, it can be “universally” composed with any set of other protocols. Our formulation of the UC model differs in several respects from the way it was originally formalized in the literature. We will hint at these differences as we go; some additional comments can be found in the Notes section of this chapter. Before we look at the formal details, let us start by discussing the basic ideas of how to define privacy and robustness of a protocol and last, but not least, why and how these two concepts should be defined via one common definition because they are closely entangled. Defining Privacy It is convenient to first look back on how we defined privacy in Chapter 3. Informally, we defined a protocol to be private (against corruptions of size t ) as follows: first, pick an input ( x 1 ,…, x n )for the protocol, and make a run of the protocol on this input. Then pick some C ⊂{P 1 ,…,P n } with | C | ≤ t and consider the values {view j }P j∈C , where view j is the view of party P j in the execution. The values {view j }P j ∈ C constitute exactly the information leaked to the corrupted parties, C , during an execution. In the following we therefore call the values {view j }P j ∈ C the leaked values. We then want to say that the leaked values do not allow the corrupted parties to learn anything that they should not learn. It is clear that the corrupted parties necessarily must learn their own inputs and outputs; in fact, this is the entire purpose of the protocol. We therefore call the values { x j , y j }P j ∈ C the allowed values.
Introduction The protocol we described in Chapter 3 is perfectly correct and perfectly private, but it cannot tolerate that any of the parties deviate from the protocol. In later chapters we will present protocols that are correct and private even if some parties do not follow the protocol. Such protocols are called robust. Before we can prove that these protocols are robust, we need a good definition of what we mean by that. In this section we will describe a security model for cryptographic protocols known as the UC model. Here UC stands for universally composable . The name was adopted because a protocol proven secure in this model remains secure regardless of the context in which it is used. In other words, it can be “universally” composed with any set of other protocols. Our formulation of the UC model differs in several respects from the way it was originally formalized in the literature. We will hint at these differences as we go; some additional comments can be found in the Notes section of this chapter. Before we look at the formal details, let us start by discussing the basic ideas of how to define privacy and robustness of a protocol and last, but not least, why and how these two concepts should be defined via one common definition because they are closely entangled. Defining Privacy It is convenient to first look back on how we defined privacy in Chapter 3. Informally, we defined a protocol to be private (against corruptions of size t ) as follows: first, pick an input ( x 1 ,…, x n )for the protocol, and make a run of the protocol on this input. Then pick some C ⊂{P 1 ,…,P n } with | C | ≤ t and consider the values {view j }P j∈C , where view j is the view of party P j in the execution. The values {view j }P j ∈ C constitute exactly the information leaked to the corrupted parties, C , during an execution. In the following we therefore call the values {view j }P j ∈ C the leaked values. We then want to say that the leaked values do not allow the corrupted parties to learn anything that they should not learn. It is clear that the corrupted parties necessarily must learn their own inputs and outputs; in fact, this is the entire purpose of the protocol. We therefore call the values { x j , y j }P j ∈ C the allowed values.
Abstract. We introduce the notion of resource-fair protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to similar previously proposed definitions, our definition follows the standard simulation paradigm and enjoys strong composability properties. In particular, our definition is similar to the security definition in the universal composability (UC) framework, but works in a model that allows any party to request additional resources from the environment to deal with dishonest parties that may prematurely abort. In this model we specify the ideally fair functionality as allowing parties to “invest resources ” in return for outputs, but in such an event offering all other parties a fair deal. (The formulation of fair dealings is kept independent of any particular functionality, by defining it using a “wrapper.”) Thus, by relaxing the notion of fairness, we avoid a well-known impossibility result for fair multi-party computation with corrupted majority; in particular, our definition admits constructions that tolerate arbitrary number of corruptions. We also show that, as in the UC framework, protocols in our framework may be arbitrarily and concurrently composed. Turning to constructions, we define a “commit-prove-fair-open ” functionality and design an efficient resource-fair protocol that securely realizes it, using a new variant of a cryptographic primitive known as “timelines.” With (the fairly wrapped version of) this functionality we show that some of the existing secure multi-party computation protocols can be easily transformed into resource-fair protocols while preserving their security. 1
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.
Abstract. The recently proposed universally composable (UC) security framework, for analyzing security of cryptographic protocols, provides very strong security guarantees. In particular, a protocol proven secure in this framework is guaranteed to maintain its security even when deployed in arbitrary multi-party, multi-protocol, multi-execution environments. Protocols for securely carrying out essentially any cryptographic task in a universally composable way exist, both in the case of an honest majority (in the plain model, i.e., without set-up assumptions) and in the case of no honest majority (in the common reference string model). However, in the plain model, little was known for the case of no honest majority and, in particular, for the important special case of two-party protocols. We study the feasibility of universally composable two-party function evaluation in the plain model. Our results show that very few functions can be computed in this model so as to provide the UC security guarantees. Specifically, for the case of deterministic functions, we provide a full characterization of the functions computable in this model. (Essentially, these are the functions that depend on at most one of the parties’ inputs, and furthermore are “efficiently invertible ” in a sense defined within.) For the case of probabilistic functions, we show that the only functions computable in this model are those where one of the parties can essentially uniquely determine the joint output. 1
We put forward a framework for the modular design and analysis of multi-party protocols. Our framework is called “GNUC ” (with the recursive meaning “GNUC’s Not UC”), already alluding to the similarity to Canetti’s Universal Composability (UC) framework. In particular, like UC, we offer a universal composition theorem, as well as a theorem for composing protocols with joint state. We deviate from UC in several important aspects. Specifically, we have a rather different view than UC on the structuring of protocols, on the notion of polynomial-time protocols and attacks, and on corruptions. We will motivate our definitional choices by explaining why the definitions in the UC framework are problematic, and how we overcome these problems. Our goal is to offer a framework that is largely compatible with UC, such that previous results formulated in UC carry over to GNUC with minimal changes. We exemplify this by giving explicit formulations for several important protocol tasks, including authenticated and secure communication, as well as commitment and secure function evaluation. 1
We show how to securely realize any multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider a multi-party network with open communication and an adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and make general intractability assumptions.
We show how to securely realize any multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider a multi-party network with open communication and an adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and make general intractability assumptions.