Rabin signature algorithm

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 ${\displaystyle 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 ${\displaystyle H(m,u)}$ of a message ${\displaystyle m}$ and ${\displaystyle k}$-bit randomization string ${\displaystyle u}$.

Public key

A public key is a pair of integers ${\displaystyle (n,b)}$ with ${\displaystyle 0\leq b<n}$ and ${\displaystyle n}$ odd. ${\displaystyle b}$ is chosen arbitrarily and may be a fixed constant.

Signature

A signature on a message ${\displaystyle m}$ is a pair ${\displaystyle (u,x)}$ of a ${\displaystyle k}$-bit string ${\displaystyle u}$ and an integer ${\displaystyle x}$ such that $${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}.}$$

Private key

The private key for a public key ${\displaystyle (n,b)}$ is the secret odd prime factorization ${\displaystyle p\cdot q}$ of ${\displaystyle n}$, chosen uniformly at random from some large space of primes.

Signing a message

To make a signature on a message ${\displaystyle m}$ using the private key, the signer starts by picking a ${\displaystyle k}$-bit string ${\displaystyle u}$ uniformly at random, and computes ${\displaystyle c:=H(m,u)}$. Let ${\displaystyle d=(b/2){\bmod {n}}}$. If ${\displaystyle c+d^{2}}$ is a quadratic nonresidue modulo ${\displaystyle n}$, the signer starts over with an independent random ${\displaystyle u}$. ^{[1] : p. 10} Otherwise, the signer computes $${\displaystyle {\begin{aligned}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{aligned}}}$$ using a standard algorithm for computing square roots modulo a prime —picking ${\displaystyle 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 ${\displaystyle c}$. ${\displaystyle x_{p}}$ and ${\displaystyle x_{q}}$ satisfy the equations $${\displaystyle {\begin{aligned}x_{p}(x_{p}+b)&\equiv H(m,u){\pmod {p}},\\x_{q}(x_{q}+b)&\equiv H(m,u){\pmod {q}}.\end{aligned}}}$$ The signer then uses the Chinese remainder theorem to solve the system $${\displaystyle {\begin{aligned}x&\equiv x_{p}{\pmod {p}},\\x&\equiv x_{q}{\pmod {q}},\end{aligned}}}$$ for ${\displaystyle x}$, so that ${\displaystyle x}$ satisfies $${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}}$$ as required. The signer reveals ${\displaystyle (u,x)}$ as a signature on ${\displaystyle m}$.

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

Security

Security against any adversary defined generically in terms of a hash function ${\displaystyle H}$ (i.e., security in the random oracle model) follows from the difficulty of factoring ${\displaystyle n}$: Any such adversary with high probability of success at forgery can, with nearly as high probability, find two distinct square roots ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ of a random integer ${\displaystyle c}$ modulo ${\displaystyle n}$. If ${\displaystyle x_{1}\pm x_{2}\not \equiv 0{\pmod {n}}}$ then ${\displaystyle \gcd(x_{1}\pm x_{2},n)}$ is a nontrivial factor of ${\displaystyle n}$, since ${\displaystyle {x_{1}}^{2}\equiv {x_{2}}^{2}\equiv c{\pmod {n}}}$ so ${\displaystyle n\mid {x_{1}}^{2}-{x_{2}}^{2}=(x_{1}+x_{2})(x_{1}-x_{2})}$ but ${\displaystyle 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 ${\displaystyle H}$; if we set a standard size ${\displaystyle K}$ for the prime factors, ${\displaystyle 2^{K-1}<p<q<2^{K}}$, then we might specify ${\displaystyle 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 ${\displaystyle b}$ in the public key adds no security, since any algorithm to solve congruences ${\displaystyle x(x+b)\equiv c{\pmod {n}}}$ for ${\displaystyle x}$ given ${\displaystyle b}$ and ${\displaystyle c}$ can be trivially used as a subroutine in an algorithm to compute square roots modulo ${\displaystyle n}$ and vice versa, so implementations can safely set ${\displaystyle b=0}$ for simplicity; ${\displaystyle b}$ was discarded altogether in treatments after the initial proposal. ^{[11] [2] [7] [5]} After removing ${\displaystyle b}$, the equations for ${\displaystyle x_{p}}$ and ${\displaystyle x_{q}}$ in the signing algorithm become:$${\displaystyle {\begin{aligned}x_{p}&:=\pm {\sqrt {c}}{\bmod {p}},\\x_{q}&:=\pm {\sqrt {c}}{\bmod {q}}.\end{aligned}}}$$

Rabin-Williams

The Rabin signature scheme was later tweaked by Williams in 1980 ^[11] to choose ${\displaystyle p\equiv 3{\pmod {8}}}$ and ${\displaystyle q\equiv 7{\pmod {8}}}$, and replace a square root ${\displaystyle x}$ by a tweaked square root ${\displaystyle (e,f,x)}$, with ${\displaystyle e=\pm 1}$ and ${\displaystyle f\in \{1,2\}}$, so that a signature instead satisfies $${\displaystyle efx^{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 ${\displaystyle x=2}$ can be forged by anyone as a valid signature on the message ${\displaystyle m=4}$ if the signature verification equation is ${\displaystyle x^{2}\equiv m{\pmod {n}}}$ instead of ${\displaystyle x^{2}\equiv H(m,u){\pmod {n}}}$.

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

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

This notation has led to some confusion among some authors later who ignored the ${\displaystyle C}$ part and misunderstood ${\displaystyle 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 (PDF) (Technical report). Cambridge, MA, United States: MIT Laboratory for Computer Science. TR-212.
2. Bellare, Mihir; Rogaway, Phillip (May 1996). Maurer, Ueli (ed.). The Exact Security of Digital Signatures—How to Sign with RSA and Rabin. Advances in Cryptology – EUROCRYPT ’96. Lecture Notes in Computer Science. Vol. 1070. Saragossa, Spain: Springer. pp. 399–416. doi: 10.1007/3-540-68339-9_34 . ISBN   978-3-540-61186-8.
3. Diffie, Whitfield; Hellman, Martin (November 1976). "New Directions in Cryptography" (PDF). IEEE Transactions on Information Theory . 22 (6). IEEE: 644–654. doi:10.1109/TIT.1976.1055638.
4. Rivest, R.L.; Shamir, A. Shamir; Adleman, L. (February 1978). Graham, S.L; Rivest, R.L.; Manacher, G.K. (eds.). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". Communications of the ACM . 21 (2). ACM: 120–126. doi: 10.1145/359340.359342 .
5. Bernstein, Daniel J. (January 31, 2008). RSA signatures and Rabin–Williams signatures: the state of the art (Report). (additional information at https://cr.yp.to/sigs.html)
6. Bernstein, Daniel J. (April 2008). Smart, Nigel (ed.). Proving tight security for Rabin–Williams signatures. Advances in Cryptology – EUROCRYPT 2008. Lecture Notes in Computer Science. Vol. 4965. 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. Bellare, Mihir; Rogaway, Phillip (August 1998). Submission to IEEE P1393—PSS: Provably Secure Encoding Method for Digital Signatures (PDF) (Report). Archived from the original (PDF) on 2004-07-13.
9. Halevi, Shai; Krawczyk, Hugo (August 2006). Dwork, Cynthia (ed.). Strengthening Digital Signatures via Randomized Hashing (PDF). Advances in Cryptology – CRYPTO 2006. Lecture Notes in Computer Science. Vol. 4117. Santa Barbara, CA, United States: Springer. pp. 41–59. doi: 10.1007/11818175_3 . Archived from the original (PDF) on 2022-03-19.
10. Dang, Quynh (February 2009). Randomized Hashing for Digital Signatures (Report). NIST Special Publication. Vol. 800–106. United States Department of Commerce, National Institute for Standards and Technology. doi: 10.6028/NIST.SP.800-106 .
11. Williams, Hugh C. "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. Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). "§11.3.4: The Rabin public-key signature scheme" (PDF). Handbook of Applied Cryptography. CRC Press. pp. 438–442. ISBN   0-8493-8523-7.
13. Galbraith, Steven D. (2012). "§24.2: The textbook Rabin cryptosystem". Mathematics of Public Key Cryptography. Cambridge University Press. pp. 491–494. ISBN   978-1-10701392-6.
14. Elia, Michele; Schipani, David (2011). On the Rabin signature (PDF). Workshop on Computational Security. Centre de Recerca Matemàtica, Barcelona, Spain.

External links

• Rabin–Williams signatures at cr.yp.to