6
$\begingroup$

In the private key CPA game, the attacker has access to an encryption oracle anytime during the attack.

However, I have seen this statement in lecture notes I downloaded "You can prove that for every polynomial time attacker that uses the encryption oracle after receiving the challenge cyphertext, you can construct another polynomial attacker that also breaks the encryption scheme only querying the oracle before receiving the challenge cyphertext."

I have tried to do reductions but I don't see how I could use the first type of attacker to build the second type, since the first requires oracle queries after knowing the challenge cyphertext.

I have also tried to search this but was unable to find.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

"You can prove that for every polynomial time attacker that uses the encryption oracle after receiving the challenge cyphertext, you can construct another polynomial attacker that also breaks the encryption scheme only querying the oracle before receiving the challenge cyphertext."

Actually, that is not true in general; you need to make further assumptions on the encryption method. Presumably, the lecture gave these further assumptions.

One counterexample to the general statement is a self-inverse cipher, that is, one for which $E_k(E_k(M)) = M$. It is obvious, given $E_k(M)$ and an encryption oracle, how to recover $M$ with a single query. However, if there are no further weaknesses, there is no useful way to generate queries before you see the challenge ciphertext $E_k(M)$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Actually, your counterexample is insecure even when oracle queries are allowed only before receiving the challenge ciphertext. Let's say I make oracle queries for $m_0$ and $m_1$, and receive the the ciphertexts as $c_0$ and $c_1$. At this point, I choose to make the challenge with $c_0$ and $c_1$ as the messages. This is allowed because ciphertexts are also in the message space for self-inverse ciphers. I can now easily distinguish between these two messages without making further queries. $\endgroup$
    – thegreat2
    Dec 13, 2015 at 5:34
  • $\begingroup$ @thegreat2: if we allow that there's only a polynomial number of possible challenge plaintexts, then the statement is trivial (because the attacker can simulate the attack for each possible challenge plaintexts, making the queries required for each attack, multiplying the total number of queries by that amount). On the other hand, unless there was an unlisted assumption otherwise, the statement appears to apply to any attacker, even one that works against a superpolynomial number of possible texts. $\endgroup$
    – poncho
    Dec 13, 2015 at 17:56
  • $\begingroup$ I am not sure if I understand you right. There are still an exponential number of possible challenge plaintexts that are not known ciphertexts of the the self-inverse cipher, in addition to the ciphertexts of the self-inverse cipher. Essentially, for a self-inverse cipher, the plaintext space and the ciphertext space have to be the same - and it can be exponential. $\endgroup$
    – thegreat2
    Dec 13, 2015 at 18:01
  • $\begingroup$ @poncho The only explicit assumption was that it was a stateless encryption scheme $\endgroup$
    – hsgubert
    Dec 13, 2015 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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