In cryptography, the Rabin signature algorithm is a method of digital signature originally published by Michael O. Rabin in 1979.[1][2]

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,[3][4] 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.[5]

Rabin signatures resemble RSA signatures with exponent e=2, but this leads to qualitative differences that enable more efficient implementation[5] and a security guarantee relative to the difficulty of integer factorization,[1][2][6] which has not been proven for RSA. However, Rabin signatures have seen relatively little use or standardization outside IEEE P1363[7] 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 H(m, u) of a message m and k-bit randomization string u.

Public key
A public key is a pair of integers (n, b) with 0 \leq b < n and n odd. b is chosen arbitrarily and may be a fixed constant.
Signature
A signature on a message m is a pair (u, x) of a k-bit string u and an integer x such that
x (x + b) \equiv H(m, u) \pmod n.
Private key
The private key for a public key (n, b) is the secret odd prime factorization p\cdot q of n, chosen uniformly at random from some large space of primes.
Signing a message
To make a signature on a message m using the private key, the signer starts by picking a k-bit string u uniformly at random, and computes c := H(m, u). Let d = (b/2) \bmod n. If c + d^2 is a quadratic nonresidue modulo n, the signer starts over with an independent random u.[1]: p. 10 Otherwise, the signer computes
\begin{align}
      x_p &:= \Bigl(-d \pm \sqrt{c + d^2}\Bigr) \bmod p, \\
      x_q &:= \Bigl(-d \pm \sqrt{c + d^2}\Bigr) \bmod q,
    \end{align}

using a standard algorithm for computing square roots modulo a prime—picking p \equiv q \equiv 3 \pmod 4 makes it easiest. Square roots are not unique, and different variants of the signature scheme make different choices of square root;[5] in any case, the signer must ensure not to reveal two different roots for the same hash c. x_p and x_q satisfy the equations

\begin{align}
      x_p (x_p + b) &\equiv H(m,u) \pmod p, \\
      x_q (x_q + b) &\equiv H(m,u) \pmod q.
    \end{align}

The signer then uses the Chinese remainder theorem to solve the system

\begin{align}
      x &\equiv x_p \pmod p, \\
      x &\equiv x_q \pmod q,
    \end{align}

for x, so that x satisfies

x (x + b) \equiv H(m,u) \pmod n

as required. The signer reveals (u, x) as a signature on m.

The number of trials for u before x (x + b) \equiv H(m,u) \pmod n can be solved for x is geometrically distributed with an average around 4 trials, because about 1/4 of all integers are quadratic residues modulo n.

Security

Security against any adversary defined generically in terms of a hash function H (i.e., security in the random oracle model) follows from the difficulty of factoring n: Any such adversary with high probability of success at forgery can, with nearly as high probability, find two distinct square roots x_1 and x_2 of a random integer c modulo n. If x_1 \pm x_2 \not\equiv 0 \pmod n then \gcd(x_1 \pm x_2, n) is a nontrivial factor of n, since {x_1}^2 \equiv {x_2}^2 \equiv c \pmod n so n \mid {x_1}^2 - {x_2}^2 = (x_1 + x_2) (x_1 - x_2) but n \nmid x_1 \pm x_2.[2] Formalizing the security in modern terms requires filling in some additional details, such as the codomain of H; if we set a standard size K for the prime factors, 2^{K - 1} < p < q < 2^K, then we might specify H\colon \{0,1\}^* \times \{0,1\}^k \to \{0,1\}^K.[6]

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[2] and resilience to collision attacks on fixed hash functions.[8][9][10]

Variants

Removing b

The quantity b in the public key adds no security, since any algorithm to solve congruences x (x + b) \equiv c \pmod n for x given b and c can be trivially used as a subroutine in an algorithm to compute square roots modulo n and vice versa, so implementations can safely set b = 0 for simplicity; b was discarded altogether in treatments after the initial proposal.[11][2][7][5] After removing b, the equations for x_p and x_q in the signing algorithm become:

\begin{align}
      x_p &:= \pm \sqrt{c} \bmod p, \\
      x_q &:= \pm \sqrt{c} \bmod q.
    \end{align}

Rabin-Williams

The Rabin signature scheme was later tweaked by Williams in 1980[11] to choose p \equiv 3 \pmod 8 and q \equiv 7 \pmod 8, and replace a square root x by a tweaked square root (e, f, x), with e = \pm1 and f \in \{1,2\}, so that a signature instead satisfies

e f x^2 \equiv H(m, u) \pmod n,

which allows the signer to create a signature in a single trial without sacrificing security. This variant is known as Rabin–Williams.[5][7]

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.[5]

Variants without the hash function have been published in textbooks,[12][13] crediting Rabin for exponent 2 but not for the use of a hash function. These variants are trivially broken—for example, the signature x = 2 can be forged by anyone as a valid signature on the message m = 4 if the signature verification equation is x^2 \equiv m \pmod n instead of x^2 \equiv H(m, u) \pmod n.

In the original paper,[1] the hash function H(m, u) was written with the notation C(MU), with C for compression, and using juxtaposition to denote concatenation of M and U as bit strings:

By convention, when wishing to sign a given message, M, [the signer] P adds as suffix a word U of an agreed upon length k. The choice of U is randomized each time a message is to be signed. The signer now compresses M_1 = MU by a hashing function to a word C(M_1) = c, so that as a binary number c \leq n…

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

References

  1. ^ Rabin, Michael O. (January 1979). Digitalized Signatures and Public Key Functions as Intractable as Factorization. No. TR-212. Cambridge, MA, United States: MIT Laboratory for Computer Science.
  2. ^ Bellare, Mihir & Rogaway, Phillip (May 1996). The Exact Security of Digital Signatures—How to Sign with RSA and Rabin. Advances in Cryptology – EUROCRYPT ’96. Vol. 1070. Lecture Notes in Computer Science. Maurer, Ueli (ed.). Saragossa, Spain: Springer. pp. 399–416. doi:10.1007/3-540-68339-9_34. ISBN 978-3-540-61186-8.
  3. ^ "New Directions in Cryptography". IEEE Transactions on Information Theory. 22 (6): 644–654. IEEE. November 1976. Bibcode:1976ITIT...22..644D. doi:10.1109/TIT.1976.1055638
  4. ^ Graham, S.L; Rivest, R.L.; Manacher, G.K. (eds.) (February 1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". Communications of the ACM. 21 (2): 120–126. ACM. doi:10.1145/359340.359342
  5. ^ RSA signatures and Rabin–Williams signatures: the state of the art. January 31, 2008. (additional information at https://cr.yp.to/sigs.html)
  6. ^ Bernstein, Daniel J. (April 2008). Proving tight security for Rabin–Williams signatures. Advances in Cryptology – EUROCRYPT 2008. Vol. 4965. Lecture Notes in Computer Science. Smart, Nigel (ed.). Istanbul, Turkey: Springer. pp. 70–87. doi:10.1007/978-3-540-78967-3_5. ISBN 978-3-540-78966-6.
  7. ^ IEEE Standard Specifications for Public-Key Cryptography. IEEE Std 1363-2000. Institute of Electrical and Electronics Engineers. August 25, 2000. doi:10.1109/IEEESTD.2000.92292. ISBN 0-7381-1956-3.
  8. ^ Submission to IEEE P1393—PSS: Provably Secure Encoding Method for Digital Signatures. August 1998. Archived 2004-07-13 at the Wayback Machine.
  9. ^ Dwork, Cynthia (ed.) (August 2006). Strengthening Digital Signatures via Randomized Hashing. Advances in Cryptology – CRYPTO 2006. Vol. 4117. Lecture Notes in Computer Science. Santa Barbara, CA, United States: Springer. pp. 41–59. doi:10.1007/11818175_3. Archived 2022-03-19 at the Wayback Machine.
  10. ^ Dang, Quynh (February 2009). Randomized Hashing for Digital Signatures. Vol. 800-106. NIST Special Publication. United States Department of Commerce, National Institute for Standards and Technology. doi:10.6028/NIST.SP.800-106
  11. ^ "A modification of the RSA public-key encryption procedure". IEEE Transactions on Information Theory. 26 (6): 726–729. doi:10.1109/TIT.1980.1056264. ISSN 0018-9448
  12. ^ "§11.3.4: The Rabin public-key signature scheme". Handbook of Applied Cryptography. CRC Press. October 1996. pp. 438–442. ISBN 0-8493-8523-7.
  13. ^ "§24.2: The textbook Rabin cryptosystem". Mathematics of Public Key Cryptography. Cambridge University Press. 2012. pp. 491–494. ISBN 978-1-10701392-6.
  14. ^ On the Rabin signature. Workshop on Computational Security. 2011.