In cryptography, the Rabin signature algorithm is a method of digital signature originally proposed by Michael O. Rabin in 1978.
By introducing the use of hashing as an essential step in signing, it was the first design to meet what is now the modern standard of security against forgery, existential unforgeability under chosen-message attack, assuming suitably scaled parameters.
, but this leads to qualitative differences that enable more efficient implementation[4] and a security guarantee relative to the difficulty of integer factorization,[2][3][5] which has not been proven for RSA.
However, Rabin signatures have seen relatively little use or standardization outside IEEE P1363[6] in comparison to RSA signature schemes such as RSASSA-PKCS1-v1_5 and RSASSA-PSS.
The Rabin signature scheme is parametrized by a randomized hash function
Security against any adversary defined generically in terms of a hash function
(i.e., security in the random oracle model) 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
[3] Formalizing the security in modern terms requires filling in some additional details, such as the codomain of
; if we set a standard size
[5] 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[3] and resilience to collision attacks on fixed hash functions.
in the public key adds no security, since any algorithm to solve congruences
can be trivially used as a subroutine in an algorithm to compute square roots modulo
and vice versa, so implementations can safely set
was discarded altogether in treatments after the initial proposal.
The Rabin signature scheme was later tweaked by Williams in 1980[10] to choose
which allows the signer to create a signature in a single trial without sacrificing security.
[4][6] Further variants allow tradeoffs between signature size and verification speed, partial message recovery, signature compression (down to one-half size), and public key compression (down to one-third size), still without sacrificing security.
[4] Variants without the hash function have been published in textbooks,[11][12] 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
In the original paper,[2] the hash function
, with C for compression, and using juxtaposition to denote concatenation of
as bit strings: By convention, when wishing to sign a given message,
adds as suffix a word
is randomized each time a message is to be signed.
by a hashing function to a word
… This notation has led to some confusion among some authors later who ignored the
to mean multiplication, giving the misapprehension of a trivially broken signature scheme.