. This paper discusses a cryptographic protocol to evaluate an and-gate such that a party can keep his input bit secret from the other party. Such a protocol is of interest, because it can be generalized to any logical circuit for any number of participants. A formal statement of this generalization reads as follows: n participants want to compute together a function f(x1 ; x2 ; :::; xn) with x i being their inputs; nobody wants to reveal information about his input except what can be logically be deduced from the output. The paper contains no new results but provides an illustration of a sub-field of cryptography, and introduces several interesting protocols and protocol design techniques. 1 Introduction Suppose Alice and Bob meet for the first time. They want to find out whether they are interested in each other, so both engage in a cryptographic protocol transmitted in infra-red through their watches. The protocol has to be such that if both parties show interest they find out, bu...
. This paper discusses a cryptographic protocol to evaluate an and-gate such that a party can keep his input bit secret from the other party. Such a protocol is of interest, because it can be generalized to any logical circuit for any number of participants. A formal statement of this generalization reads as follows: n participants want to compute together a function f(x1 ; x2 ; :::; xn) with x i being their inputs; nobody wants to reveal information about his input except what can be logically be deduced from the output. The paper contains no new results but provides an illustration of a sub-field of cryptography, and introduces several interesting protocols and protocol design techniques. 1 Introduction Suppose Alice and Bob meet for the first time. They want to find out whether they are interested in each other, so both engage in a cryptographic protocol transmitted in infra-red through their watches. The protocol has to be such that if both parties show interest they find out, bu...
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.
A two-party oblivious circuit evaluation (2P- OCE) protocol is a way for a party Alice owns a secret x and another party Bob owns a secret y to compute the value of an agreed upon function f(x,y), where f can be computed by a polynomial sized Boolean circuit. This is done in such a way that Alice learns nothing about y and Bob learns nothing about x, except for what can be inferred from one's private input and the public value of f(x,y). This paper presents a general, correct, fair, honest, and maximum privacy 2P-OCE protocol that is based on a set of reductions to more simple cryptographic primitives. The protocol uses the primitives of one-out-of-two oblivious transfer (1-2-OT) and bit commitment (BC) as black boxes. Consequently, the protocol may be implemented with or without computational assumptions, depending on the type of 1-2-OT and BC used by participants.
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.
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.
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?
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.