Of course, this protocol doesn’t protect against active cheaters. There’s nothing to stop Alice (or Bob, for that matter) from lying about her age. If Bob were a computer program that blindly executed the protocol, Alice could learn his age (is the age of a computer program the length of time since it was written or the length of time since it started running?) by repeatedly executing the protocol. Alice might give her age as 60. After learning that she is older, she could execute the protocol again with her age as 30. After learning that Bob is older, she could execute the protocol again with her age as 45, and so on, until Alice discovers Bob’s age to any degree of accuracy she wishes.

Assuming that the participants don’t actively cheat, it is easy to extend this protocol to multiple participants. Any number of people can find out the order of their ages by a sequence of honest applications of the protocol; and no participant can learn the age of another.

Protocol #3

Alice likes to do kinky things with teddy bears. Bob has erotic fantasies about marble tables. Both are pretty embarrassed by their particular fetish, but would love to find a mate who shared in their...um...lifestyle.

Here at the Secure Multiparty Computation Dating Service, we’ve designed a protocol for people like them. We’ve numbered an astonishing list of fetishes, from “aardvarks” to “zoot suits.” Discreetly separated by a modem link, Alice and Bob can participate in a secure multiparty protocol. Together, they can determine whether they share the same fetish. If they do, they might look forward to a lifetime of bliss together. If they don’t, they can part company secure in the knowledge that their particular fetish remains confidential. No one, not even the Secure Multiparty Computation Dating Service, will ever know.

Here’s how it works:

(1)  Using a one-way function, Alice hashes her fetish into a seven-digit string.

(2)  Alice uses the seven-digit string as a telephone number, calls the number, and leaves a message for Bob. If no one answers or the number is not in service, Alice applies a one-way function to the telephone number until she finds someone who can play along with the protocol.

(3)  Alice tells Bob how many times she had to apply the one-way hash function to her fetish.

(4)  Bob hashes his fetish the same number of times that Alice did. He also uses the seven-digit string as a telephone number, and asks the person at the other end whether there were any messages for him.

Note that Bob has a chosen-plaintext attack. He can hash common fetishes and call the resulting telephone numbers, looking for messages for him. This protocol only really works if there are enough possible plaintext messages for this to be impractical.

There’s also a mathematical protocol, one similar to Protocol #2. Alice knows a, Bob knows b, and together they will determine whether a = b, such that Bob does not learn anything additional about a and Alice does not learn anything additional about b. Details are in Section 23.14.

Protocol #4

This is another problem for secure multiparty computation [1373]: A council of seven meets regularly to cast secret ballots on certain issues. (All right, they rule the world—don’t tell anyone I told you.) All council members can vote yes or no. In addition, two parties have the option of casting “super votes”: S-yes and S-no. They do not have to cast super votes; they can cast regular votes if they prefer. If no one casts any super votes, then the majority of votes decides the issue. In the case of a single or two equivalent super votes, all regular votes are ignored. In the case of two contradicting super votes, the majority of regular votes decides. We want a protocol that securely performs this style of voting.

Two examples should illustrate the voting process. Assume there are five regular voters, N₁ through N_5, and two super voters: S₁ and S₂. Here’s the vote on issue #1:

S1        S2      N1    N2    N3    N4    N5
S-yes     no     no    no    no    yes    yes

In this instance the only vote that matters is S₁ ’s, and the result is “yes.”

Here is the vote on issue #2:

S1       S2     N1   N2   N3   N4   N5
S-yes    S-no   no   no   no   yes  yes

Here the two super votes cancel and the majority of regular “no” votes decide the issue.

If it isn’t important to hide the knowledge of whether the super vote or the regular vote was the deciding vote, this is an easy application of a secure voting protocol. Hiding that knowledge requires a more complicated secure multiparty computation protocol.

This kind of voting could occur in real life. It could be part of a corporation’s organizational structure, where certain people have more power than others, or it could be part of the United Nations’s procedures, where certain nations have more power than others.

Multiparty Unconditionally Secure Protocols

This is just a simple case of a general theorem: Any function of n inputs can be computed by a set of n players in a way that will let all learn the value of the function, but any set of less than n/2 players will not get any additional information that does not follow from their own inputs and the value of the output information. For details, see [136, 334, 1288, 621].

Secure Circuit Evaluation

Alice has her input, a. Bob has his input, b. Together they wish to compute some general function, f (a,b), such that Alice learns nothing about Bob’s input and Bob learns nothing about Alice’s input. The general problem of secure multiparty computation is also called secure circuit evaluation. Here, Alice and Bob can create an arbitrary Boolean circuit. This circuit accepts inputs from Alice and from Bob and produces an output. Secure circuit evaluation is a protocol that accomplishes three things:

1.  Alice can enter her input without Bob’s being able to learn it.

2.  Bob can enter his input without Alice’s being able to learn it.

3.  Both Alice and Bob can calculate the output, with both parties being sure the output is correct and that neither party has tampered with it.

Details on secure circuit evaluation can be found in [831].