Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Do I understand correctly that the textbook Rabin encryption scheme, where there is no random padding (as is also required in RSA for it to be CPA secure), is not CPA secure? (it is deterministic without such padding), or am I missing something?
My confusion arises from the wikipedia article which states that it is CPA secure, but the description and example provided do not mention anything about random padding.
Thanks.
Do I understand correctly that the textbook Rabin encryption scheme, where there is no random padding, is not CPA secure?
Yes, textbook Rabin encryption is not CPA secure for the modern meaning of that. No deterministic public-key encryption scheme can be CPA-secure. The adversary wins the basic IND-CPA experiment by choosing any two distinct plaintexts, enciphering them with the public key handed by the challenger, and can recognize which plaintext corresponds to the ciphertext handed by the challenger, by mere comparison.
Further, textbook Rabin (and RSA) encryption has the multiplicative property $E(m\,m'\bmod n)=E(m)\,E(m')\bmod n$, which under CPA allows to find $n$ and the public exponent then build a distinguisher even if the public key is initially unknown and uses a secret exponent, thus even a symmetric variant of these encryption methods are not IND-CPA.
Textbook Rabin encryption is demonstrably secure under known random plaintext attack assuming hardness of factorization, when there is no known proof that RSA has such property. But to get security against Choosen Plaintext Attack, we need some randomness in the encoding of the message representative. And to make such security demonstrable, it seems that we need elaborate padding like OAEP or OAEP+. Such proofs are not easy, see Victor Shoup's OAEP Reconsidered.
Update: I edited the Wikipedia article, but my edit (of "chosen-plaintext" to "known random plaintext") was initially reverted on the grounds that "This directly contradicts the source, so at least needs another source". It turns out "the source" is Cryptography Theory and Practice by Douglas R. Stinson. It's 2019 (fourth) edition (with Maura B. Paterson) still states:
the Rabin Cryptosystem is provably secure against a chosen plaintext attack
following a proof of something different: that ability to solve any arbitrary instance of the Rabin problem implies ability to factor. This can be extended to prove that the Rabin Cryptosystem discussed is provably secure against an attack with random known plaintext, but this is a far cry from a chosen plaintext attack.
