Signing Documents with Symmetric Cryptosystems and an Arbitrator

Alice wants to sign a digital message and send it to Bob. With the help of Trent and a symmetric cryptosystem, she can.

Trent is a powerful, trusted arbitrator. He can communicate with both Alice and Bob (and everyone else who may want to sign a digital document). He shares a secret key, K_A, with Alice, and a different secret key, K_B, with Bob. These keys have been established long before the protocol begins and can be reused multiple times for multiple signings.

(1)  Alice encrypts her message to Bob with K_A and sends it to Trent.

(2)  Trent decrypts the message with K_A.

(3)  Trent takes the decrypted message and a statement that he has received this message from Alice, and encrypts the whole bundle with K_B.

(4)  Trent sends the encrypted bundle to Bob.

(5)  Bob decrypts the bundle with K_B. He can now read both the message and Trent’s certification that Alice sent it.

How does Trent know that the message is from Alice and not from some imposter? He infers it from the message’s encryption. Since only he and Alice share their secret key, only Alice could encrypt a message using it.

Is this as good as a paper signature? Let’s look at the characteristics we want:

1.  This signature is authentic. Trent is a trusted arbitrator and Trent knows that the message came from Alice. Trent’s certification serves as proof to Bob.

2.  This signature is unforgeable. Only Alice (and Trent, but everyone trusts him) knows K_A, so only Alice could have sent Trent a message encrypted with K_A. If someone tried to impersonate Alice, Trent would have immediately realized this in step (2) and would not certify its authenticity.

3.  This signature is not reusable. If Bob tried to take Trent’s certification and attach it to another message, Alice would cry foul. An arbitrator (it could be Trent or it could be a completely different arbitrator with access to the same information) would ask Bob to produce both the message and Alice’s encrypted message. The arbitrator would then encrypt the message with K_A and see that it did not match the encrypted message that Bob gave him. Bob, of course, could not produce an encrypted message that matches because he does not know K_A.

4.  The signed document is unalterable. Were Bob to try to alter the document after receipt, Trent could prove foul play in exactly the same manner just described.

5.  The signature cannot be repudiated. Even if Alice later claims that she never sent the message, Trent’s certification says otherwise. Remember, Trent is trusted by everyone; what he says is true.

If Bob wants to show Carol a document signed by Alice, he can’t reveal his secret key to her. He has to go through Trent again:

(1)  Bob takes the message and Trent’s statement that the message came from Alice, encrypts them with K_B, and sends them back to Trent.

(2)  Trent decrypts the bundle with K_B.

(3)  Trent checks his database and confirms that the original message came from Alice.

(4)  Trent re-encrypts the bundle with the secret key he shares with Carol, K_C, and sends it to Carol.

(5)  Carol decrypts the bundle with K_C. She can now read both the message and Trent’s certification that Alice sent it.

These protocols work, but they’re time-consuming for Trent. He must spend his days decrypting and encrypting messages, acting as the intermediary between every pair of people who want to send signed documents to one another. He must keep a database of messages (although this can be avoided by sending the recipient a copy of the sender’s encrypted message). He is a bottleneck in any communications system, even if he’s a mindless software program.

Harder still is creating and maintaining someone like Trent, someone that everyone on the network trusts. Trent has to be infallible; if he makes even one mistake in a million signatures, no one is going to trust him. Trent has to be completely secure. If his database of secret keys ever got out or if someone managed to modify his programming, everyone’s signatures would be completely useless. False documents purported to be signed years ago could appear. Chaos would result. Governments would collapse. Anarchy would reign. This might work in theory, but it doesn’t work very well in practice.

Digital Signature Trees

Ralph Merkle proposed a digital signature scheme based on secret-key cryptography, producing an infinite number of one-time signatures using a tree structure [1067,1068]. The basic idea of this scheme is to place the root of the tree in some public file, thereby authenticating it. The root signs one message and authenticates its sub-nodes in the tree. Each of these nodes signs one message and authenticates its sub-nodes, and so on.

Signing Documents with Public-Key Cryptography

There are public-key algorithms that can be used for digital signatures. In some algorithms—RSA is an example (see Section 19.3)—either the public key or the private key can be used for encryption. Encrypt a document using your private key, and you have a secure digital signature. In other cases—DSA is an example (see Section 20.1)—there is a separate algorithm for digital signatures that cannot be used for encryption. This idea was first invented by Diffie and Hellman [496] and further expanded and elaborated on in other texts [1282,1328,1024,1283,426]. See [1099] for a good survey of the field.

The basic protocol is simple:

(1)  Alice encrypts the document with her private key, thereby signing the document.

(2)  Alice sends the signed document to Bob.

(3)  Bob decrypts the document with Alice’s public key, thereby verifying the signature.

This protocol is far better than the previous one. Trent is not needed to either sign or verify signatures. (He is needed to certify that Alice’s public key is indeed her public key.) The parties do not even need Trent to resolve disputes: If Bob cannot perform step (3), then he knows the signature is not valid.