3.6.9 What are some other signature schemes?
Merkle proposed a digital signature scheme based on both one-time signatures (see Question 7.7) and a hash function (see Question 2.1.6); this provides an infinite tree of one-time signatures [Mer90b].
One-time signatures normally require the publishing of large amounts of data to authenticate many messages, since each signature can only be used once. Merkle's scheme solves the problem by implementing the signatures via a tree-like scheme. Each message to be signed corresponds to a node in a tree, with each node consisting of the verification parameters used to sign a message and to authenticate the verification parameters of subsequent nodes. Although the number of messages that can be signed is limited by the size of the tree, the tree can be made arbitrarily large. Merkle's signature scheme is fairly efficient, since it requires only the application of hash functions.
The Rabin signature scheme [Rab79] is a variant of the RSA signature scheme (see Question 3.1.1). It has the advantage over the RSA system that finding the private key and forgery are both provably as hard as factoring. Verification is faster than signing, as with RSA signatures. In Rabin's scheme, the public key is an integer n where n = pq, and p and q are prime numbers which form the private key. The message to be signed must have a square root mod n; otherwise, it has to be modified slightly. Only about 1/4 of all possible messages have square roots mod n. The signature s of m is s = m1/2 mod n. Thus to verify the signature, the receiver computes m = s2 mod n.
The signature is easy to compute if the prime factors of n are known, but provably difficult otherwise. Anyone who can consistently forge the signature for a modulus n can also factor n. The provable security has the side effect that the prime factors can be recovered under a chosen message attack. This attack can be countered by padding a given message with random bits or by modifying the message randomly, at the loss of provable security. See [GMR86] for a discussion of a way to get around the paradox between provable security and resistance to chosen message attacks.