The Rabin cryptosystem is a family of public-key encryption schemes

based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization.

The Rabin trapdoor function has the advantage that inverting it has been mathematically proven to be as hard as factoring integers, while there is no such proof known for the RSA trapdoor function.

It has the disadvantage that each output of the Rabin function can be generated by any of four possible inputs; if each output is a ciphertext, extra complexity is required on decryption to identify which of the four possible inputs was the true plaintext.

Naive attempts to work around this often either enable a chosen-ciphertext attack to recover the secret key or, by encoding redundancy in the plaintext space, invalidate the proof of security relative to factoring.

The Rabin signature scheme was the first digital signature scheme where forging a signature could be proven to be as hard as factoring.

The trapdoor function was later repurposed in textbooks as an example of a public-key encryption scheme,

Efficiency

For encryption, a square modulo n must be calculated. This is more efficient than RSA, which requires the calculation of at least a cube.

For decryption, the Chinese remainder theorem is applied, along with two modular exponentiations. Here the efficiency is comparable to RSA.

Security

It has been proven that any algorithm which finds one of the possible plaintexts for every Rabin-encrypted ciphertext can be used to factor the modulus <math>n</math>. Thus, Rabin decryption for random plaintext is at least as hard as the integer factorization problem, something that has not been proven for RSA. It is generally believed that there is no polynomial-time algorithm for factoring, which implies that there is no efficient algorithm for decrypting a random Rabin-encrypted value without the private key <math>(p,q)</math>.

The Rabin cryptosystem does not provide indistinguishability against chosen plaintext attacks since the process of encryption is deterministic. An adversary, given a ciphertext and a candidate message, can easily determine whether or not the ciphertext encodes the candidate message (by simply checking whether encrypting the candidate message yields the given ciphertext).

The Rabin cryptosystem is insecure against a chosen ciphertext attack (even when challenge messages are chosen uniformly at random from the message space). By adding redundancies, for example, the repetition of the last 64 bits, the system can be made to produce a single root. This thwarts this specific chosen-ciphertext attack, since the decryption algorithm then only produces the root that the attacker already knows. If this technique is applied, the proof of the equivalence with the factorization problem fails, so it is uncertain as of 2004 if this variant is secure. The Handbook of Applied Cryptography by Menezes, Oorschot and Vanstone considers this equivalence probable, however, as long as the finding of the roots remains a two-part process (1. roots <math>\bmod{p}</math> and <math>\bmod{q}</math> and 2. application of the Chinese remainder theorem).

See also

  • Topics in cryptography
  • Blum Blum Shub
  • Shanks–Tonelli algorithm
  • Schmidt–Samoa cryptosystem
  • Blum–Goldwasser cryptosystem

Notes

References

  • Buchmann, Johannes. Einführung in die Kryptographie. Second Edition. Berlin: Springer, 2001.
  • Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996.
  • Rabin, Michael. Digitalized Signatures and Public-Key Functions as Intractable as Factorization (in PDF). MIT Laboratory for Computer Science, January 1979.
  • Scott Lindhurst, An analysis of Shank's algorithm for computing square roots in finite fields. in R Gupta and K S Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, vol 19 CRM Proc & Lec Notes, AMS, Aug 1999.
  • R Kumanduri and C Romero, Number Theory w/ Computer Applications, Alg 9.2.9, Prentice Hall, 1997. A probabilistic for square root of a quadratic residue modulo a prime.
  • Menezes, Oorschot, Vanstone, Scott: Handbook of Applied Cryptography (free PDF downloads), see Chapter 8