# For public-key encryption, why does COA resistance imply CPA resistance?

My professor told me:

If a public-key crypto-system is secure against ciphertext-only attacks, then it is also secure against a chosen-plaintext attack.

Why is this true? Is there a proof that confirms this?

-
It's perhaps more helpful to rephrase this statement as "every public-key cryptosystem that is insecure against a chosen-plaintext attack is also insecure against ciphertext-only attacks." Can you see why this is? – Ilmari Karonen Nov 13 '11 at 5:05

I was/am assuming that for public key encryption, COA means "other than the public key, ciphertext only". Otherwise, any secure symmetric cipher with the key published becomes a "COA resistant" PKE scheme. With that in mind, access to an encryption oracle cannot possibly help an attacker, since the attacker can already encrypt any plaintext using the public key. $\:$ Therefore, COA resistance implies CPA resistance. $\:$ (for public-key encryption, with my assumption on the definition of COA)

-
I agree, can someone please explain the logic behind this? – Bobby S Nov 14 '11 at 17:54

I have a definition of COA-security in my head but I cannot find this definition (applied to public key cryptography) in the literature or reference books.

Under it, textbook RSA is an example of a public key cryptosystem that is COA-secure but not CPA-secure. To be CPA-secure, a necessary but not sufficient property is that encrypting the same message twice does not give you the same ciphertext both times. For this, the encryption function should be randomized. RSA with OAEP is CPA-secure as is Elgamal. To be COA-secure, you basically only need to ensure the private key is not easily computed from the public key.

In any event, the question really comes down to definitions and without providing a definition of COA-security for PKC, it was rash of me to say the statement is true or false (the latter, I did initially, before I edited this answer).

If the only difference between a COA and CPA security game is whether the adversary has access to an encryption oracle, then providing the public key to the adversary gives the adversary all the powers on an encryption oracle. In this case, COA and CPA are equivalent.

However the challenge in the CPA security game based on the adversary choosing a pair of messages for encryption, being given an encryption of one of them (selected at random), and being challenged to state which one. I don't believe the challenge in a COA-secure game for PKC would be the same, as the challenge is premised on the adversary choosing (or at least knowing) the two potential plaintexts candidates.

If the challenges are different in COA and CPA, they are not necessary equivalent.

-
Does "ciphertext-only attack" mean that the attacker doesn't know the public key? – Paŭlo Ebermann Nov 13 '11 at 18:53
The attacker does not know the key, the attacker has a set of ciphertexts and the set of corresponding plaintexts. – Bobby S Nov 13 '11 at 20:42
That is actually a known plaintext attack which is sandwiched between COA and CPA in terms of security. I checked Lindell-Katz, and contrary to my previous (deleted) comment, in CPA, the adversary is given the public key. They show that an "eavesdropping" security definition is equivalent to CPA-security, and perhaps this is what was meant in the original question. – PulpSpy Nov 14 '11 at 16:33