Let the following game be given:


  1. Prepare a key k <- KeyGen(1^Kappa)
  2. Choose a hidden bit h <- {0, 1} uniformly random
  3. Prepare a decryption oracle O_Dec. Given a cipher text c, it returns the decryption m
  4. Prepare a one-time oracle O_Test. When called with m_0, m_1, it will return the encryption of m_h. Call it c*
  5. Call the attacker with input 1^Kappa, O_Dec, O_Test and await a guess h'.
  6. If O_Dec was ever called with the output of O_Test, randomly accept or reject.
  7. If h = h' then accept else reject

My lecturer claims that there exists a polynomial time attacker with a non-negligible advantage for AES.

We have seen that obviously, a deterministic scheme is never IND-CPA secure since you can just ask for the encryption of both m_0 and m_1. But since we don't have access to an encryption oracle, we have to find cipher texts != c* that somehow reveal information when being decrypted.

I just don't see any structure in the encryption/decryption that might help us.

Since there is no mode of operation given. Just textbook AES for one block


1 Answer 1


Someone gave me the solution:

Attacker A:

  1. Decrypt a random Bitstring c using O_Dec and get m
  2. Call O_test with m and another random bitstring m'
  3. Return 1

If the hidden h = 0 (which happens 50% of the time), we win/lose randomly since O_Dec was called with the value returned by O_test. If h = 1, we always win. So all in all, we win 75% of the time, which is obviously non-negligible


Your Answer

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

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