### Question 37. What is the Rabin Signature
Scheme?

The Rabin signature scheme [Rab79]
is a variant of the RSA signature
scheme (see Question 8). It has the advantage over
RSA 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*.

Signature: *s* = *m*^{1/2} mod *n* where *s* is the
signature

Verification: *m* = *s*^{2} mod *n*

The signature is easy to compute if the prime factors of *n *are
known, but probably difficult otherwise - anyone who can forge the signature
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.)