Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

We have a game $G0$ for which an adversary $A$ has access to a certain amount of ressources. Let us suppose that the maximum advantage for the adversary to win this game is $Adv_{G0}$.

If we modify slightly the game $G0$ into the game $G1$ in such way that we give an additional information (useful or not) to this adversary.

Can we state that $Adv_{G0} \le Adv_{G_1}$ ?

If we consider indistinguishability games for encryption, the first one with CPA attack, the second one with CCA attack. Can we state that $Adv^{CPA} \le Adv^{CCA}$ ?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Can we state that $Adv_{G0} \le Adv_{G_1}$ ?

Absolutely. Let us call $S0$ the strategy that $A$ can use in game $G0$ to achieve advantage $Adv_{G0}$; we notice that $A$ can also use strategy $S0$ to achieve that exact same advantage in $G1$, and hence we see that the maximum advantage he can achieve in $G1$ must be at least as large as in $G0$

Can we state that $Adv^{CPA} \le Adv^{CCA}$ ?

No (unless we assume that, in the CCA case, the attacker is also allowed to submit chosen plaintexts as well).

To demonstrate this, construct an encryption method that is secure, except that if the plaintext was the specific message "Open Sesame", it outputs a ciphertext that is the encryption key.

In this case, $Adv^{CPA}$ is quite large (the attacker submits two plaintexts, one "Open Sesame" and one something else, and see if the key he got from the "Open Sesame" message encrypts the other message in the ciphertext he got).

However, there is no obvious way that the attacker can use chosen ciphertexts; he knows that if he submits a ciphertext that happens to be key, he'll get the plaintext "Open Sesame"; however that doesn't help him, as there are other ways to verify a guess on the key.

Hence, in this artificial example, we have $Adv^{CPA} > Adv^{CCA}$

share|improve this answer
    
Thank you poncho. You say "No (unless we assume that, in the CCA case, the attacker is also allowed to submit chosen plaintexts as well)." It seems to me that for a CCA attack, the attacker can submit chosen plaintexts and chosen ciphertexts (except the challenge messages to encrypt for CCA2). No ? –  Dingo13 Nov 14 '13 at 17:36
2  
@Dingo13: that would depend on the exact definition of "CCA"; I've heard various definitions, and so I threw in the cavaet. If we assume that CCA also includes chosen plaintext, then obviously we have $Adv^{CPA} \le Adv^{CCA}$ –  poncho Nov 14 '13 at 18:39
1  
From my experience CCA definitions that do not allow encryption queries are extremely uncommon. So a better way of putting that might be "Yes, unless you are using an uncommon definition of CCA that does not allow encryption queries." –  Maeher Nov 15 '13 at 12:19
1  
The CCA security is intentionally a stronger requirement compared to the CPA security. If you do not give access to the encryption oracle in the CCA setting, then you seemingly evaluate the CPA security of the decryption function. –  Dmitry Khovratovich Nov 17 '13 at 11:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.