|Previous||Table of Contents||Next|
There is a trick that makes BOBs chance of cheating even smaller. In step (4), ALICE randomly chooses n/2 of the documents to challenge, and BOB sends her the appropriate blinding factors in step (5). In step (7), ALICE multiplies together all of the unchallenged documents and signs the mega-document. In step (8), BOB strips off all the blinding factors. ALICEs signature is acceptable only if it is a valid signature of the product of n/2 identical documents. To cheat BOB has to be able to guess exactly which subset ALICE will challenge; the odds are much smaller than the odds of guessing which one document ALICE wont challenge.
BOB has another way to cheat. He can generate two different documents, one that ALICE is willing to sign and one that ALICE is not. Then he can find two different blinding factors that transform each document into the same blinded document. That way, if ALICE asks to examine the document, BOB gives her the blinding factor that transforms it into the benign document. If ALICE doesnt ask to see the document and signs it, he uses the blinding factor that transforms it into the malevolent document. While this is theoretically possible, the mathematics of the particular algorithms involved make the odds of BOBs being able to find such a pair negligibly small. In fact, it can be made as small as the odds of Bob being able to produce the signature on an arbitrary message himself. This issue is discussed further in Section 23.12.
Chaum has patents for several flavors of blind signatures (see Table 5.1).
Alice wants to send a secure message to Bob. She doesnt want to get his public key from a key server; she doesnt want to verify some trusted third partys signature on his public-key certificate; and she doesnt even want to store Bobs public key on her own computer. She just wants to send him a secure message.
Identity-based cryptosystems, sometimes called Non-Interactive Key Sharing (NIKS) systems, solve this problem . Bobs public key is based on his name and network address (or telephone number, or physical street address, or whatever). With normal public-key cryptography, Alice needs a signed certificate that associates Bobs public key with his identity. With identity-based cryptography, Bobs public key is his identity. This is a really cool idea, and about as ideal as you can get for a mail system: If Alice knows Bobs address, she can send him secure mail. It makes the cryptography about as transparent as possible.
The system is based on Trent issuing private keys to users based on their identity. If Alices private key is compromised, she has to change some aspect of her identity to get another one. A serious problem is designing a system in such a way that a collusion of dishonest users cannot forge a key.
A lot of work has been done on the mathematics of these sorts of schemesmost of it in Japanwhich turn out to be infuriatingly complicated to make secure. Many of the proposed solutions involve Trent choosing a random number for each userin my opinion this defeats the real point of the system. Some of the algorithms discussed in Chapters 19 and 20 can be identity-based. For details, algorithms, and cryptanalysis, see [191,1422,891,1022,1515,1202,1196,908,692,674,1131,1023,1516,1536,1544,63,
1210,314,313,1545,1539,1543,933,1517,748,1228]. An algorithm that does not rely on any random numbers is . The system discussed in [1546,1547,1507] is insecure against a chosen-public-key attack; so is the system proposed as NIKS-TAS [1542,1540,1541,993,375,1538]. Honestly, nothing proposed so far is both practical and secure.
Chaums Blind Signature Patents
|U.S. PATENT #||DATE||TITLE|
|4,759,063||7/19/88||Blind Signature Systems |
|4,759,064||7/19/88||Blind Unanticipated Signature Systems |
|4,914,698||3/3/90||One-Show Blind Signature Systems |
|4,949,380||8/14/90||Returned-Value Blind Signature Systems |
|4,991,210||2/5/91||Unpredictable Blind Signature Systems |
Cryptographer Bob is desperately trying to factor a 500-bit number, n. He knows its the product of five 100-bit numbers, but nothing more. (This is a problem. If he cant recover the key hell have to work overtime and hell miss his weekly mental poker game with Alice.)
What do you know? Here comes Alice now:
I happen to know one factor of the number, she says, and Ill sell it to you for $100. Thats a dollar a bit. To show shes serious, she uses a bit-commitment scheme and commits to each bit individually.
Bob is interested, but has only $50. Alice is unwilling to lower her price and offers to sell Bob half the bits for half the price. Itll save you a considerable amount of work, she says.
But how do I know that your number is actually a factor of n? If you show me the number and let me verify that it is a factor, then I will agree to your terms, says Bob.
They are at an impasse. Alice cannot convince Bob that her number is a factor of n without revealing it, and Bob is unwilling to buy 50 bits of a number that could very well be worthless.
This story, stolen from Joe Kilian , introduces the concept of oblivious transfer. Alice transmits a group of messages to Bob. Bob receives some subset of those messages, but Alice has no idea which ones he receives. This doesnt completely solve the problem, however. After Bob has received a random half of the bits, Alice has to convince him that the bits she sent are part of a factor of n, using a zero-knowledge proof.
In the following protocol, Alice will send Bob one of two messages. Bob will receive one, and Alice will not know which.
|Previous||Table of Contents||Next|