Two large corporations decide that they will proceed with some joint venture conditioned on their joint capital being greater than some specified amount. However, they do not wish to disclose these amounts to the other party. This is a simple example of a secure two party computation. For security, we require that the parties learn only the value of the joint capital, and in particular get no other information on the amount that the other party inputted.
This article defines various types of secure computation, before giving some results about what types can be achieved with unconditional security, i.e. security guaranteed by the laws of physics alone. Most of this has been taken from Colbeck and Kent quant-ph/0508149.
Secure Multi-Party Computation
A secure multi-party classical computation involves N mistrusful parties. It takes input xi from the ith party, and returns fi(x1, …, xN) to that party. fi(x1, …, xN) need not be deterministic. We call this a classical computation because the inputs and outputs are classical, although we allow such computations to be implemented by protocols which involve the processing of quantum states. A perfectly secure computation guarantees, for each i, each subset J ⊆ {1, …, N}, and each set of possible inputs xi and {xj}j ∈ J, that if the parties J do indeed input {xj}j ∈ J and then collaborate, they can gain no more information about the input xi than what is implied by {xj}j ∈ J and {fj(x1, …, xN)}j ∈ J.
In what follows, we specialize to the case where {fi} are the same for all i.
Secure Two-Party Computation
The two party case is the simplest. We classify such computations by the number of inputs, the number of outputs (the sidedness of the computation), and whether they are deterministic or random. We summarize the known results for each class, where we allow protocos that are both quantum and relativistic (that is exploit the properties of quantum systems and/or the impossibility of superluminal signalling for their operation).
Zero-input computations
A deterministic zero-input computation simply gives some output to one or both parties (depending on the sidedness). It hence has no cryptographic value: the relevant computations can be carried out by one or both parties separately. The most general type of zero-input two-sided random secure computation is a biased n-faced secure die roll. This can be implemented with unconditional security by generalizing the well-known relativistic protocol for a secure coin toss.
One-input computations
Secure protocols for deterministic one-input computations are trivial; the party making the input can always choose it to generate any desired output on the other side, so might as well compute the function on their own and send the output directly to the other party.
The non-deterministic case is of interest. For one-sided computations, where the output goes to the party that did not make the input, the most general function is a one-sided variable bias n-faced die roll. The input simply defines a probability distribution over the outputs. In essence, one party chooses one from a collection of biased n-faced dice to roll (the members of the collection are known to both parties). The output of the roll goes to one party only, who has no other information about which die was chosen.
It is known that some computations of this type are impossible. A special case of these computations defines a version of oblivious transfer (OT), in which Alice inputs a bit, Bob inputs nothing, Bob receives Alice's bit with probability half, and otherwise receives the outcome fail. Rudolph quant-ph/0202143 has shown that no non-relativistic quantum protocol can securely implement this task, and his argument trivially generalizes to the relativistic case.
The two-sided case of a non-deterministic one-input function we call a variable bias n-faced die roll. For the two-faced case, there exist protocols which have been shown to be achievable with unconditional security for a limited range of biases, with cheat-evident security for all biases, and two further protocols that allow any range of biases and which are conjectured to be unconditionally secure. Some of these protocols can be readily extended to the n-faced case.
Two-input computations
Lo Lo considered the task of finding a secure non-relativistic quantum protocol for a two-input, deterministic, one-sided function. He showed that if the protocol allows Alice to input i, Bob to input j, and Bob to receive f(i, j), while giving Alice no information on j, then Bob can also obtain f(i, jʹ) for all jʹ. For any cryptographically nontrivial computation, there must be at least one i for which knowing f(i, jʹ) for all jʹ gives Bob more information than knowing f(i, j) for just one value of j. As this violates the definition of security for a secure classical computation, it is impossible to implement any cryptographically nontrivial computation securely. Lo's proof as stated applies to non-relativistic protocols, and extends trivially to relativistic protocols. We hence conclude that all secure two-input deterministic one-sided cryptographically nontrivial computations are impossible.
Lo also noted that some secure two-input deterministic, two-sided non-relativistic quantum computations are impossible, because they imply the ability to do non-trivial secure two-input, deterministic one-sided computations. This argument also extends trivially torelativistic protocols.
As far as we are aware, neither existence nor no-go results are presently known for secure two-input non-deterministic computations.