In a description of IND-CPA (indistinguishability under the chosen plaintext attack), I have been reading the following, simple test:

The adversary can generate as many messages as he wants. Then, he chooses two messages $m0$ and $m1$, those messages are encrypted, and one of the ciphertexts is sent back to him. The adversary should not be able to guess which message was used to generate that ciphertext.

Is that really the correct way to do an IND-CPA test?

I would imagine that — if I were the adversary and you the crypto-guru — I would pick and send you a one-liner saying "Hello world" and a copy of the front page of a news-paper article consisting of at least 100 words. Whatever you'll send me back encrypted will allow me to differ and identify the ciphertext as the average encryption won't pad that one-liner to the same length as the news-paper article. There's a pretty good chance that the newspaper article's cryptotext will be bigger than the one-liner's cryptotext.

Following that logic, it would mean that most (if not all) crypto currently used would fail that IND-CPA test.

Is that quoted test wrong or missing something?

  • 1
    $\begingroup$ Where did you see that description of the IND-CPA game? Was there any additional context or notation? $\endgroup$ – pg1989 Oct 1 '13 at 1:51
  • $\begingroup$ @pg1989 I happened to stumble over it here under "Security tests". It's not the usual type of websites I visit when hunting knowledge... so I am currently guessing the "simple test" might be "simply wrong". But I want to be sure of that to avoid missing something important. (Hope you get what I mean - 3am, need my coffee.) $\endgroup$ – e-sushi Oct 1 '13 at 1:55
  • 2
    $\begingroup$ @e-sushi I'm the author of that article. It was not meant to be a really precise definition, just to introduce the concept to beginners (that's also why I did not talk about adaptive CPA). Anyhow, thanks for pointing this out, I fixed the article to mention both messages have to be the same length. Note that sending different plaintexts to encrypt and observing the length of resulting ciphertexts is how the CRIME attack works :) $\endgroup$ – Géal Oct 1 '13 at 13:45

That sounds like an overly succinct description of the 'Find then Guess' (FTG) notion of security, described in the paper "A Concrete Security Treatment of Symmetric Enryption".

And you are correct, there is something the test is missing: the two 'challenge' plaintexts must be the same length ($|m_0| = |m_1|$). Also, the description is so succinct I can't tell whether they meant to give this impression, but it sounds like a 'non-adaptive' approach to FTG-CPA, in that the Adversary only has access to the encryption oracle prior to getting the challenge. In the 'adaptive' FTG-CPA (the version described in the linked paper), the Adversary continues to be able to query the encryption oracle after receiving the challenge (and prior to making its guess).

By the way, the FTG notion is only one variant of IND-CPA. There is also the Left Or Right (LOR) notion, and the Real OR Random (ROR) notions. LOR and ROR are somewhat stronger than FTG, in that there is a tight reduction from a LOR or ROR advantage-bound to a FTG advantage-bound, but the reduction is not as tight going the other way around. So if you prove in the FTG game that any opponent has at most an advantage of $\epsilon$, you can only say that any opponent in the LOR game has an advantage of at most $q_e\epsilon$, where $q_e$ is the number of queries made to the encryption oracle (so opponents might have much larger advantage in the LOR game if there were a lot of queries).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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