|Previous||Table of Contents||Next|
Proofs of Membership
Alice wants to prove to Bob that she is a member of some super-secret organization, but she does not want to reveal her identity. This problem is similar but different to proving identity, and has also been studied [887,906,907,1201,1445]. Some solutions are related to the problem of group signatures (see Section 4.6).
An essential feature of digital signature protocols is that the signer knows what he is signing. This is a good idea, except when we want the reverse.
We might want people to sign documents without ever seeing their contents. There are ways that a signer can almost, but not exactly, know what he is signing. But first things first.
Completely Blind Signatures
Bob is a notary public. Alice wants him to sign a document, but does not want him to have any idea what he is signing. Bob doesnt care what the document says; he is just certifying that he notarized it at a certain time. He is willing to go along with this.
This protocol only works if the signature function and multiplication are commutative. If they are not, there are other ways to modify the document other than by multiplying. Some relevant algorithms appear in Section 23.12. For now, assume that the operation is multiplication and all the math works.
Can Bob cheat? Can he collect any information about the document that he is signing? If the blinding factor is truly random and makes the blinded document truly random, he cannot. The blinded document Bob signs in step (2) looks nothing like the document Alice began with. The blinded document with Bobs signature on it in step (3) looks nothing like the signed document at the end of step (4). Even if Bob got his hands on the document, with his signature, after completing the protocol, he cannot prove (to himself or to anyone else) that he signed it in that particular protocol. He knows that his signature is valid. He can, like anyone else, verify his signature. However, there is no way for him to correlate any information he received during the signing protocol with the signed document. If he signed a million documents using this protocol, he would have no way of knowing in which instance he signed which document.
The properties of completely blind signatures are:
Eve, who is in the middle, watching this protocol, has even less information than Bob.
With the completely blind signature protocol, Alice can have Bob sign anything: Bob owes Alice a million dollars, Bob owes Alice his first-born child, Bob owes Alice a bag of chocolates. The possibilities are endless. This protocol isnt useful in many applications.
However, there is a way that Bob can know what he is signing, while still maintaining the useful properties of a blind signature. The heart of this protocol is the cut-and-choose technique. Consider this example. Many people enter this country every day, and the Department of Immigration wants to make sure they are not smuggling cocaine. The officials could search everyone, but instead they use a probabilistic solution. They will search one-tenth of the people coming in. One person in ten has his belongings inspected; the other nine get through untouched. Chronic smugglers will get away with their misdeeds most of the time, but they have a 10 percent chance of getting caught. And if the court system is effective, the penalty for getting caught once will more than wipe out the gains from the other nine times.
If the Department of Immigration wants to increase the odds of catching smugglers, they have to search more people. If they want to decrease the odds, they have to search fewer people. By manipulating the probabilities, they control how successful the protocol is in catching smugglers.
The blind signature protocol works in a similar manner. Bob will be given a large pile of different blinded documents. He will open, that is examine, all but one and then sign the last.
Think of the blinded document as being in an envelope. The process of blinding the document is putting the document in an envelope and the process of removing the blinding factor is opening the envelope. When the document is in an envelope, nobody can read it. The document is signed by having a piece of carbon paper in the envelope: When the signer signs the envelope, his signature goes through the carbon paper and signs the document as well.
This scenario involves a group of counterintelligence agents. Their identities are secret; not even the counterintelligence agency knows who they are. The agencys director wants to give each agent a signed document stating: The bearer of this signed document, (insert agents cover name here), has full diplomatic immunity. Each of the agents has his own list of cover names, so the agency cant just hand out signed documents. The agents do not want to send their cover names to the agency; the enemy might have corrupted the agencys computer. On the other hand, the agency doesnt want to blindly sign any document an agent gives it. A clever agent might substitute a message like: Agent (name) has retired and collects a million-dollar-a-year pension. Signed, Mr. President. In this case, blind signatures could be useful.
Assume that all the agents have 10 possible cover names, which they have chosen themselves and which no one else knows. Also assume that the agents dont care under which cover name they are going to get diplomatic immunity. Also assume that the agencys computer is the Agencys Large Intelligent Computing Engine, or ALICE, and that our particular agent is the Bogota Operations Branch: BOB.
This protocol is secure against BOB cheating. For him to cheat, he would have to predict accurately which document ALICE would not examine. The odds of him doing this are 1 in nnot very good. ALICE knows this and feels confident signing a document that she is not able to examine. With this one document, the protocol is the same as the previous completely blinded signature protocol and maintains all of its properties of anonymity.
|Previous||Table of Contents||Next|