|Table of Contents
Of course, this protocol doesnt protect against active cheaters. Theres 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 Bobs age to any degree of accuracy she wishes.
Assuming that the participants dont 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.
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, weve designed a protocol for people like them. Weve 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 dont, 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.
Heres how it works:
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.
Theres 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.
This is another problem for secure multiparty computation : A council of seven meets regularly to cast secret ballots on certain issues. (All right, they rule the worlddont 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, N1 through N5, and two super voters: S1 and S2. Heres 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 S1 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 isnt 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 corporations organizational structure, where certain people have more power than others, or it could be part of the United Nationss 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 Bobs input and Bob learns nothing about Alices 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:
Details on secure circuit evaluation can be found in .
|Table of Contents