Rabin signature algorithm

In cryptography, the Rabin signature algorithm is a method of digital signature originally published by Michael O. Rabin in 1979.
The Rabin signature algorithm was one of the first digital signature schemes proposed. By using a trapdoor function with a hash function|hash] of the message rather than with the message itself, in contrast to earlier proposals of one-time hash-based signatures or trapdoor-based signatures without hashing, Rabin's was the first published design to meet what is now the modern standard of security for digital signatures for more than one message, existential unforgeability under chosen-message attack.
Rabin signatures resemble RSA signatures with exponent, but this leads to qualitative differences that enable more efficient implementation and a security guarantee relative to the difficulty of integer factorization, which has not been proven for RSA.
However, Rabin signatures have seen relatively little use or standardization outside IEEE P1363 in comparison to RSA signature schemes such as RSASSA-PKCS1-v1_5 and RSASSA-PSS.

Definition

The Rabin signature scheme is parametrized by a randomized hash function of a message and -bit randomization string.
; Public key
; Signature
; Private key
; Signing a message

Security

Security against any adversary defined generically in terms of a hash function follows from the difficulty of factoring :
Any such adversary with high probability of success at forgery can, with nearly as high probability, find two distinct square roots and of a random integer modulo.
If then is a nontrivial factor of, since so but.
Formalizing the security in modern terms requires filling in some additional details, such as the codomain of ; if we set a standard size for the prime factors,, then we might specify.
Randomization of the hash function was introduced to allow the signer to find a quadratic residue, but randomized hashing for signatures later became relevant in its own right for tighter security theorems and resilience to collision attacks on fixed hash functions.

Variants

Removing

The quantity in the public key adds no security, since any algorithm to solve congruences for given and can be trivially used as a subroutine in an algorithm to compute square roots modulo and vice versa, so implementations can safely set for simplicity; was discarded altogether in treatments after the initial proposal. After removing, the equations for and in the signing algorithm become:

Rabin-Williams

The Rabin signature scheme was later tweaked by Williams in 1980 to choose and, and replace a square root by a tweaked square root, with and, so that a signature instead satisfies
which allows the signer to create a signature in a single trial without sacrificing security.
This variant is known as Rabin–Williams.

Others

Further variants allow tradeoffs between signature size and verification speed, partial message recovery, signature compression, and public key compression, still without sacrificing security.
Variants without the hash function have been published in textbooks, crediting Rabin for exponent 2 but not for the use of a hash function.
These variants are trivially broken—for example, the signature can be forged by anyone as a valid signature on the message if the signature verification equation is instead of.
In the original paper, the hash function was written with the notation, with C for compression, and using juxtaposition to denote concatenation of and as bit strings:

By convention, when wishing to sign a given message,, adds as suffix a word of an agreed upon length.
The choice of is randomized each time a message is to be signed.
The signer now compresses by a hashing function to a word, so that as a binary number …

This notation has led to some confusion among some authors later who ignored the part and misunderstood to mean multiplication, giving the misapprehension of a trivially broken signature scheme.