millionaires, and the pair wishes to determine who has more money. However, neither person wishes to reveal his or her precise wealth to the other. [5] One approach to this problem (dubbed the ideal solution) is for Alice and Bob to find a third party that they both trust. Then Alice tells the third party how much money she has, and Bob follows suit. Once both Alice and Bob have both revealed the necessary information to him, the third party provides both of them with an answer to their question. However, the use of such a trusted third party is not always practical. Therefore, our goal is to simulate the presence of such a third party using cryptography. Secure two-party computation provides a generalization of this problem: Suppose we wish to compute the value of a function F (A, B) where A is an input provided by Alice and B is provided by Bob. Assume furthermore that Alice does not wish to disclose her input to Bob, and that likewise, Bob wishes to conceal his input from Alice. How can they compute F (A, B) together while observing these constraints?
millionaires, and the pair wishes to determine who has more money. However, neither person wishes to reveal his or her precise wealth to the other. [5] One approach to this problem (dubbed the ideal solution) is for Alice and Bob to find a third party that they both trust. Then Alice tells the third party how much money she has, and Bob follows suit. Once both Alice and Bob have both revealed the necessary information to him, the third party provides both of them with an answer to their question. However, the use of such a trusted third party is not always practical. Therefore, our goal is to simulate the presence of such a third party using cryptography. Secure two-party computation provides a generalization of this problem: Suppose we wish to compute the value of a function F (A, B) where A is an input provided by Alice and B is provided by Bob. Assume furthermore that Alice does not wish to disclose her input to Bob, and that likewise, Bob wishes to conceal his input from Alice. How can they compute F (A, B) together while observing these constraints?
Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth. How can they carry out such a conversation? This is a special case of the following general problem. Suppose m people wish to compute the value of a function f(x1, x2, x3, . . . , xm), which is an integer-valued function of m integer variables xi of bounded range. Assume initially person Pi knows the value of xi and no other x’s. Is it possible for them to compute the value of f , by communicating among themselves, without unduly giving away any information about the values of their own variables? The millionaires’ problem corresponds to the case when m = 2 and f(x1, x2) = 1 if x1 < x2, and 0 otherwise. In this paper, we will give precise formulation of this general problem and describe three ways of solving it by use of one-way functions (i.e., functions which are easy to evaluate but hard to invert). These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc. We will also discuss the complexity question “How many bits need to be exchanged for the computation”, and describe methods to prevent participants from cheating. Finally, we study the question “What cannot be accomplished with one-way functions”. Before describing these results, we would like to put this work in perspective by first considering a unified view of secure computation in the next section.
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.
Consider several parties that do not trust each other, yet they wish to correctly compute some common function of their local inputs while keeping these inputs private. This problem is known as "Secure Multi-Party Computation", and was introduced by Andrew Yao in 1982. Secure multi-party computations have some real world examples like electronic auctions, electronic voting or fingerprinting. In this thesis we consider the case where there are only two parties involved. This is known as "Secure Two-Party Computation". If there is a trusted third party called Carol, then the problem is pretty straightforward. The participating parties could hand their inputs in Carol who can compute the common function correctly and could return the outputs to the corresponding parties. The goal is to achieve (almost) the same result when there is no trusted third party. Cryptographic protocols are designed in order to solve these kinds of problems. These protocols are analyzed within an appropriate model in which the behavior of parties is structured. The basic level is called the Semi-Honest Model where parties are assumed to follow the protocol specification, but later can derive additional information based on the messages which have been received so far. A more realistic model is the so-called Malicious Model. The common approach is to first analyze a protocol in the semi-honest model and then later extend it into the malicious model. Any cryptographic protocol for secure two-party computation must satisfy the following security requirements: correctness, privacy and fairness. It must guarantee the correctness of the result while preserving the privacy of the parties’ inputs, even if one of the parties is malicious and behaves arbitrarily throughout the protocol. It must also guarantee fairness. This roughly means that whenever a party aborts the protocol prematurely, he or she should not have any advantage over the other party in discovering the output. The main question for researchers is to construct new protocols that achieve the above mentioned goals for secure multi-party computation. Of course, such protocols must be secure in a given model, as well as be as efficient as possible. In 1986, Yao presented the first general protocol for secure two-party computation which was applicable only to the semi-honest model. He uses a tool called "Garbled Circuit". Yao’s protocol uses the underlying primitives ("Pseudorandom Generator" and "Oblivious Transfer") as blackboxes which lead to efficient results. After Yao’s work many variants and improvements have been proposed for the malicious model. In this thesis, we design several new protocols for secure two-party computation based on Yao’s garbled circuit. Before we present the details of our new designs, we first show several weaknesses, security flaws or problems with the existing protocols in the literature. We first work in the semi-honest model and then extend it into the malicious model by presenting new protocols. Finally we add fairness to our protocol. Oblivious transfer (OT) is a fundamental primitive in modern cryptography which is useful for implementing protocols for secure multi-party computation. We study several variants of oblivious transfer in this thesis. We present a new protocol for the so-called "Committed OT". This protocol is very efficient in the sense that it is quite good in comparison to the most efficient committed OT protocols in the literature. The abovementioned flaw with the use of OT can be fixed with our committed oblivious transfer protocol. Furthermore, it is more general than all previous protocols, and, therefore, it is of independent interest. We also deal with fairness in this thesis. For protocols based on garbled circuit, so far only Benny Pinkas has presented a protocol in the literature for achieving fairness. We show a subtle problem with this protocol where the privacy of the inputs of one party can be compromised. We also describe this problem in detail which is in fact related to the fairness, and finally propose a more efficient scheme that does achieve fairness.
In this dissertation, we address several issues that arise in protecting communication between parties, as well as in the area of secure function evaluation. Intuitively, the notion of secure function evaluation is clear and natural: several parties wish to compute some function of their inputs without revealing any information about the inputs, other than what is implied by the value of the function. Research included in this dissertation follows three main directions, briefly described below. The first direction (Chapters 3 and 4) is the design of efficient protocols for concrete functions of interest. Specifically, we present new, more efficient protocols for securely computing the Greater Than (GT) function on the inputs of two parties. Secure evaluation of GT is frequently needed in financial transactions. We introduce new primitives, which are convenient building blocks for more complex tasks, and generalize our GT solutions to satisfy them. Based on this, we construct secure auction protocols, protocols for determining whether an integer lies on an interval, and others. The second direction (Chapter 5) is a fundamental approach to secure evaluation of any function, given as a boolean circuit. We present a very efficient information-theoretic (IT) reduction from the problem of secure evaluation of a polysize formula (or, equivalently, a log-depth boolean circuit) to Oblivious Transfer (a fundamental well-researched cryptographic primitive). Our cost of evaluating each gate of the formula is quadratic in its depth, while in previous reductions it was exponential. Our constructions imply efficient one-round protocols for evaluation of polysize formulas on the players' inputs. We extend our solutions to evaluation of polysize circuits, at the cost of having only computational security. The third direction (Chapter 6) is research on key exchange (KE). In contrast with the previous two directions, here the goal is for two parties to protect their communication against eavesdropping and active interference of an external attacker. KE is a basic procedure, frequently used to establish secure channels between parties. It is a prerequisite to a large number of protocols, including those of the above two directions. We demonstrate a subtle flaw in a previous family of KE protocols and give new KE definitions for the following practical "bank" setting. Here, a server wishes to exchange a key with a client. They have a shared password, and the client carries a "bank card", capable of storing several cryptographic keys. Finally, we present new, more efficient KE protocols for this setting, and prove their security.
We introduce covert two-party computation, a stronger notion of security than standard secure two-party computation. Like standard secure two-party computation, covert two-party computation allows Alice and Bob, with secret inputs xA and xB respectively, to compute a function f(xA,xB) without leaking any additional information about their inputs. In addition, covert two-party computation guarantees that even the existence of a computation is hidden from all protocol participants unless the value of the function mandates otherwise. This allows the construction of protocols that return f(xA,xB) only when it equals a certain value of interest (such as "Yes, we are romantically interested in each other") but for which neither party can determine whether the other even ran the protocol whenever f(xA,xB) is not a value of interest. Since existing techniques for secure function evaluation always reveal that both parties participate in the computation, covert computation requires the introduction of new techniques based on provably secure steganography. We introduce security definitions for covert two-party computation and show that this surprising notion can be achieved by a protocol given the Decisional Diffie-Hellman assumption in the "honest but curious" model. Using this protocol as a subroutine, we present another protocol which is fair and secure against malicious adversaries in the Random Oracle Model --- unlike most other protocols against malicious adversaries, this protocol does not rely on zero-knowledge proofs (or similar cut-and-choose techniques), because they inherently reveal that a computation took place. We remark that all our protocols are of comparable efficiency to protocols for standard secure two-party computation.
Broadly speaking, cryptography is the problem of doing communication or computation involving two or more parties who may not trust one another. The best known cryptographic problem is the transmission of secret messages. Suppose wish to communicate in secret. For example, you may wish to give your credit card number to a merchant in exchange for goods, hopefully without any malevolent third party intercepting your credit card number. The way this is done is to use a cryptographic protocol. The most important distinction is between private key cryptosystems and public key cryptosystems.