4.6 Group Signatures

David Chaum introduces this problem in [330]:

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 department’s 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 user’s 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:

—  Only members of the group can sign messages.

—  The receiver of the signature can verify that it is a valid signature from the group.

—  The receiver of the signature cannot determine which member of the group is the signer.

—  In the case of a dispute, the signature can be “opened” to reveal the identity of the signer.

Group Signatures with a Trusted Arbitrator

This protocol uses a trusted arbitrator:

(1)  Trent generates a large pile of public-key/private-key key pairs and gives every member of the group a different list of unique private keys. No keys on any list are identical. (If there are n members of the group, and each member gets m key pairs, then there are n*m total key pairs.)

(2)  Trent publishes the master list of all public keys for the group, in random order. Trent keeps a secret record of which keys belong to whom.

(3)  When group members want to sign a document, he chooses a key at random from his personal list.

(4)  When someone wants to verify that a signature belongs to the group, he looks on the master list for the corresponding public key and verifies the signature.

(5)  In the event of a dispute, Trent knows which public key corresponds to which group member.

The problem with this protocol is that it requires a trusted party. Trent knows everyone’s private keys and can forge signatures. Also, m must be long enough to preclude attempts to analyze which keys each member uses.

Chaum [330] 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 [348] not only hides the identity of the signer, but also allows new members to join the group. Yet another protocol is [1230].

4.7 Fail-Stop Digital Signatures

Let’s say Eve is a very powerful adversary. She has vast computer networks and rooms full of Cray computers—orders of magnitude more computing power than Alice. All of these computers chug away, day and night, trying to break Alice’s private key. Finally—success. Eve can now impersonate Alice, forging her signature on documents at will.

Fail-stop digital signatures, introduced by Birgit Pfitzmann and Michael Waidner [1240], prevent this kind of cheating. If Eve forges Alice’s 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 doesn’t know any of the other private keys.

Eve wants to break Alice’s 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 Alice’s 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 Eve’s 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 Alice’s signature scheme by sheer computational power. It does nothing against Mallory’s much more likely attack of breaking into Alice’s house and stealing her private key or Alice’s 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].

4.8 Computing with Encrypted Data

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 isn’t 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.

4.9 Bit Commitment

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. It’s 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.