Secure Multiparty Computation

There exist certain situations in which multiple individuals or parties need to get together to compute functions on variables which they each provide. In some of these situations, it is imperative that while the result of the function is known to everybody, nobody learns anything about the inputs of others. Consider, for example, the following situation (see Applied Cryptography 6.2): four individuals, Alice, Bob, Carol, and Dave, want to calculate their average salary without anybody learning anybody else's salary. In addition, they are not allowed to tell their salaries to some arbitrator who computes the function. One way of calculating the average salary is as follows (see Applied Cryptography 6.2):

  1. Alice adds a secret random number to her salary, encrypts the result with Bob's public key, and sends it to Bob.
  2. Bob decrypts Alice's result with his private key. He adds his salary to what he received from Alice, encrypts the result with Carol's public key, and sends it to Carol.
  3. Carol decrypts Bob's result with her private key. She adds her salary to what she received from Bob, encrypts the result with Dave's public key, and sends it to Dave.
  4. Dave decrypts Carol's result with his private key. He adds his salary to what he received from Carol, encrypts the result with Alice's public key, and sends it to Alice.
  5. Alice decrypts Dave's result with her private key. She subtracts the random number from step (1) to recover the sum of everyone's salaries.
  6. Alice divides the result by the number of people (four, in this case) and announces the result.

Of course, this protocol assumes that all of the participants are honest; any participant could potentially lie about his salary, and Alice could even misrepresent the result when she reveals it to the other participants.

Another perhaps more famous problem in which secure multiparty computation strategies are necessary is known as "Yao's millionaire problem." Let us assume that two individuals, Alice and Bob, are millionaires with between one and one-hundred million dollars each. For some reason, both Alice and Bob want to know who has more money, but neither one of them wants to tell the other how much money they actually have. Supposing that Alice has i million dollars and Bob has j million dollars, one possible way for them to determine this is as follows (see Applied Cryptography 23.14):

  1. Alice chooses a large random number, x, and encrypts it in Bob's public key.
    c = EB(x)
  2. Alice computes c - i and sends the result to Bob.
  3. Bob computes the following 100 numbers:
    yu = DB(c - i + u), for 1 ≤ u ≤ 100
    DB is the decryption algorithm with Bob's private key.
    He chooses a large random prime, p. (The size of p should be somewhat smaller than x. Bob doesn't know x, but Alice could easily tell him the size of x.) He then computes the following 100 numbers:
    zu = (yu mod p), for 1 ≤ u ≤ 100
    He then verifies that, for all u ≠ v
    | zu - zv | ≥ 2
    and that for all u
    0 < zu < p - 1
    If this is not true, Bob chooses another prime and tries again.
  4. Bob sends Alice this sequence of numbers in this exact order:
    z1, z2, ... , zj, zj+1 + 1, zj+2 + 1, ... , z100 + 1, p
  5. Alice checks whether the ith number in the sequence is congruent to x mod p. If it is, she concludes that i ≤ j. If it is not, she concludes that i > j.
  6. Alice tells Bob the conclusion.

As with the average salary computation, this protocol assumes that Alice and Bob are honest about their wealth. Furthermore, since Alice learns the result of the computation before Bob does, she could potentially misrepresent the result. Given this relatively simple method for secretly comparing two numbers, we can now perform far more complicated computations; for example, by conducting many secret individual comparisons, one could determine who is offering the highest bid at a secret auction.

A third multiparty computation problem called the Dining Cryptographers Problem (a clever twist on the Dining Philosophers Problem) is described by David Chaum:

Three cryptographers are sitting down to dinner at their favorite three-star restaurant. Their waiter informs them that arrangements have been made with the maître d'hôtel for the bill to be paid anonymously. One of the cryptographers might be paying for the dinner, or it might have been the NSA. The three cryptographers respect each other's right to make an anonymous payment, but they wonder if the NSA is paying.

How can the cryptographers (named Alice, Bob, and Carol, of course) determine if one of them is paying for dinner without revealing the payer's identity? One solution to this problem relies on the same concept that was used to solve the average salary problem:

  1. Alice chooses some random positive integer.
  2. If Alice is paying for dinner, she adds one to this number. If she is not paying for dinner, she adds two to this number.
  3. Alice encrypts the number with Bob's public key and sends it to Bob.

The other cryptographers at the table follow steps (2) and (3) until the number returns to Alice. At this point, Alice subtracts the random number she chose in (1). If the result is odd, one of the cryptographers is paying for dinner. If the result is even, the NSA is paying.

Unfortunately, this solution requires that the number passed from cryptographer to cryptographer be encrypted. Another (perhaps more elegant) solution is proposed by Chaum himself:

Each cryptographer flips an unbiased coin behind his menu, between him and the cryptographer to his right, so that only the two of them can see the outcome. Each cryptographer then states aloud whether the two coins he can see--the one he flipped and the one his left-hand neighbor flipped--fell on the same side or on different sides. If one of the cryptographers is the payer, he states the opposite of what he sees. An odd number of differences uttered at the table indicates that a cryptographer is paying; and even number of differences indicates that NSA is paying (assuming that the dinner was paid for only once). Yet, if a cryptographer is paying, neither of the other two learns anything from the utterances about which cryptographer it is.

This solution also requires encryption to achieve complete security (here, the encryption is represented by the menus that hide the coins). However, this solution is much more efficient than the previous one because all of the cryptographers can broadcast their results after the coins are flipped. Suppose that instead of three cryptographers, there were three hundred; with the former method, the last cryptographer would have to wait for all of the others to pass encrypted information from one to the next. With the latter method, all of the cryptographers can simultaneously broadcast their results.

There are many real-world applications of secure multiparty computation, and in "Multiparty Unconditionally Secure Protocols," Chaum, Claude Crépeau, and Ivan Damgard show that "essentially any multiparty protocol problem can be solved under the assumption of the existence of authenticated secrecy channels between pairs of participants and that each party's secrets can be unconditionally secure." In addition, under their model, "it is required that less than one third of the participants deviate from the protocol. The number of cheaters tolerated by our solution is therefore optimal." Unlike our solutions to the three multiparty computation problems that we discussed previously, these authors' method of solving such problems actually allows for limited cheating (i.e. dishonesty) among the participants!