Let $\mathcal{E} = (G, E, D)$ be a CCA-secure public-key encryption scheme defined over $(\mathcal{M, C})$ where $\mathcal{C} := \{0, 1\}^\ell$.

Let $\mathcal{E'} = (G, E', D')$ be a scheme (over $(\mathcal{M, C'})$ where $\mathcal{C'} := \{0, 1\}^{\ell + 1}$) where:

  • $E'(pk, m) = E(pk,m) \Vert 0$
  • $D'(sk, c) = D(sk, c[0...\ell - 1])$

That is, $E'$ always puts a $0$ in the ciphertext and $D'$ ignores the last bit of the ciphertext.

How can an attacker, with just $1$ query, break $\mathcal{E}'$ CCA security?

Additional information:

The query can be one of these:

Encryption query: the attacker sends a pair os messages $(m_0, m_1)$ and gets a ciphertext $c_i$ of one of them.

Decryption query: the attacker sends a ciphertext $c$ and gets its corresponding message.


1 Answer 1


So let's go through the CCA(2) game and see where things fall apart, shall we?

  1. Challenger: Generates keys.
  2. Adversary: Calls the encryption or decryption oracles a polynomial amount of times. We don't need this here.
  3. Adversary: Picks two messages, eg $m_0=0$ and $m_1=1$.
  4. Challenger: Chooses a bit $b$ uniformly at random, ie $b\in\{0,1\}$
  5. Challenger: Encrypts $m_b$ and sends the result to the adversary as $C$, the challenge ciphertext.
  6. Adversay: Perform a polynomial amount of operations including encryption or decryption oracle calls, e.g. to decrypt $C$ with the last bit flipped.
  7. Adversary: Output a guess $b'$ for the bit $b$, eg the result of the decryption query in the last step.
  8. If $b=b'$ the adversary wins. If the probability of this happening is not negligbly higher than $1/2$, the scheme is broken.

Do you see now how CCA security is broken using 1 query?

  • $\begingroup$ Not yet, but this answer lightened my mind. Say the adversary has an ciphertext $c \in \mathcal{C'}$. If he queries $c$ to the oracle, he will get its corresponding $m$, so he can be sure that if he queries $c$ with the last bit flipped, he will get $m$ as well. Does this break the CCA(1) game? $\endgroup$
    – Daniel
    Jul 3, 2018 at 19:16
  • $\begingroup$ @Daniel please note that I wrote CCA(2) to mean "CCA security, also known as CCA2 security", CCA1 is strictly weaker and I think the scheme at hand is secure under CCA1. Also you may want to note that this bit-flip-preservation-property is useful only because normally the adversary may not query the challenge ciphertext itself to the decryption oracle, but the one with the flipped bit isn't that one of course... $\endgroup$
    – SEJPM
    Jul 4, 2018 at 8:10

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.