Editing Rabin cryptosystem (section)

{{Short description|Public-key encryption scheme}}
{{about|the textbook public-key encryption scheme|the digital signature scheme it was based on|Rabin signature}}
The '''Rabin cryptosystem''' is a family of [[public-key encryption]] schemes
based on a [[trapdoor function]] whose security, like that of [[RSA (algorithm)|RSA]], is related to the difficulty of [[integer factorization]].<ref name="galbraith2012mathpkc">{{cite book
|author1-last=Galbraith
|author1-first=Steven D.
|title=Mathematics of Public Key Cryptography
|publisher=Cambridge University Press
|year=2012
|isbn=978-1-10701392-6
|section=§24.2: The textbook Rabin cryptosystem
|pages=491–494
}}</ref><ref name="bellare-goldwasser-rabin-trapdoor">{{cite book
|title=Lecture Notes on Cryptography
|first1=Mihir
|last1=Bellare
|author-link1=Mihir Bellare
|first2=Shafi
|last2=Goldwasser
|author-link2=Shafi Goldwasser
|date=July 2008
|url=https://cseweb.ucsd.edu/~mihir/papers/gb.pdf#page=29
|section=§2.3.4 The Squaring Trapdoor Function Candidate by Rabin
|pages=29–32
}}</ref>

The Rabin trapdoor function has the advantage that inverting it has been [[Mathematics|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.<ref name="galbraith2012mathpkc"/>

Public-key encryption schemes based on the Rabin trapdoor function are used mainly for examples in textbooks.
In contrast, RSA is the basis of standard public-key encryption schemes such as [[PKCS 1|RSAES-PKCS1-v1_5]] and [[Optimal asymmetric encryption padding|RSAES-OAEP]] that are used widely in practice.