|Previous||Table of Contents||Next|
David Chaum introduces this problem in :
A company has several computers, each connected to the local network. Each department of that company has its own printer (also connected to the network) and only persons of that department are allowed to use their departments printer. Before printing, therefore, the printer must be convinced that the user is working in that department. At the same time, the company wants privacy; the users name may not be revealed. If, however, someone discovers at the end of the day that a printer has been used too often, the director must be able to discover who misused that printer, and send him a bill.
The solution to this problem is called a group signature. Group signatures have the following properties:
Group Signatures with a Trusted Arbitrator
This protocol uses a trusted arbitrator:
The problem with this protocol is that it requires a trusted party. Trent knows everyones private keys and can forge signatures. Also, m must be long enough to preclude attempts to analyze which keys each member uses.
Chaum  lists a number of other protocols, some in which Trent is unable to fake signatures and others in which Trent is not even required. Another protocol  not only hides the identity of the signer, but also allows new members to join the group. Yet another protocol is .
Lets say Eve is a very powerful adversary. She has vast computer networks and rooms full of Cray computersorders of magnitude more computing power than Alice. All of these computers chug away, day and night, trying to break Alices private key. Finallysuccess. Eve can now impersonate Alice, forging her signature on documents at will.
Fail-stop digital signatures, introduced by Birgit Pfitzmann and Michael Waidner , prevent this kind of cheating. If Eve forges Alices signatures after a brute-force attack, then Alice can prove they are forgeries. If Alice signs a document and then disavows the signature, claiming forgery, a court can verify that it is not a forgery.
The basic idea behind fail-stop signatures is that for every possible public key, many possible private keys work with it. Each of these private keys yields many different possible signatures. However, Alice has only one private key and can compute just one signature. Alice doesnt know any of the other private keys.
Eve wants to break Alices private key. (Eve could also be Alice, trying to compute a second private key for herself.) She collects signed messages and, using her array of Cray computers, tries to recover Alices private key. Even if she manages to recover a valid private key, there are so many possible private keys that it is far more likely that she has a different one. The probability of Eves recovering the proper private key can be made so small as to be negligible.
Now, when Eve forges a signed document using the private key she generated, it will have a different signature than if Alice signs the document herself. When Alice is hauled off to court, she can produce two different signatures for the same message and public key (corresponding to her private key and to the private key Eve created) to prove forgery. On the other hand, if Alice cannot produce the two different signatures, there is no forgery and Alice is still bound by her signature.
This signature scheme protects against Eve breaking Alices signature scheme by sheer computational power. It does nothing against Mallorys much more likely attack of breaking into Alices house and stealing her private key or Alices attack of signing a document and then conveniently losing her private key. To protect against the former, Alice should buy herself a good guard dog; that kind of thing is beyond the scope of cryptography.
Additional theory and applications of fail-stop signatures can be found in [1239, 1241, 730, 731].
Alice wants to know the solution to some function f(x), for some particular value of x. Unfortunately, her computer is broken. Bob is willing to compute f(x) for her, but Alice isnt keen on letting Bob know her x. How can Alice let Bob compute f(x) for her without telling him x?
This is the general problem of computing with encrypted data, also called hiding information from an oracle. (Bob is the oracle; he answers questions.) There are ways to do this for certain functions; they are discussed in Section 23.6.
The Amazing Alice, magician extraordinaire, will now perform a mystifying feat of mental prowess. She will guess the card Bob will choose before he chooses it! Watch as Alice writes her prediction on a piece of paper. Marvel as Alice puts that piece of paper in an envelope and seals it shut. Thrill as Alice hands that sealed envelope to a random member of the audience. Pick a card, Bob, any card. He looks at it and shows it to Alice and the audience. Its the seven of diamonds. Alice now takes the envelope back from the audience. She rips it open. The prediction, written before Bob chose his card, says seven of diamonds! Applause.
|Previous||Table of Contents||Next|