Wikipedia / Rabin signature algorithm
Wikipedia / 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 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, 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.
Public key
is chosen arbitrarily and may be a fixed constant.
Signature
Private key
, chosen uniformly at random from some large space of primes.
Signing a message
is a quadratic nonresidue. using a standard algorithm for computing square roots modulo a prime makes it easiest. Square roots are not unique, and different variants of the signature scheme make different choices of square root; The signer then uses the Chinese remainder theorem.
.
Security
(i.e., security in the random oracle model. Formalizing the security in modern terms requires filling in some additional details, such as the codomain.
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 b
was discarded altogether in treatments after the initial proposal.
Rabin-Williams
The Rabin signature scheme was later tweaked by Williams in 1980 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 (down to one-half size), and public key compression (down to one-third size), 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.
In the original paper,, with C for compression as bit strings:
…
to mean multiplication, giving the misapprehension of a trivially broken signature scheme.