I have a question on the disprove of the CCA-security given in Katz & Lindell's textbook (2nd edition) in chapter 3.7 on page 97. It works like this:

  1. Consider our construction based on PRFs: $\text{Enc}(k, m) := (r , s) = (r , F (k, r ) \oplus m)$
  2. Set $m_0 = 0^n$ and $m_1 = 1^n$
  3. Adversary A gets $(r , s)$ and flips the first bit of s. Denote the ciphertext by $(r , s' )$
  4. A sends $(r , s' )$ to his decryption oracle
  5. A obtains either $0\mathbin\|1^{n−1}$ or $1\mathbin\|0^{n−1}$ which allows him to win the game

My question: Why does A not obtain $0\mathbin\|1^{n−1}$ and $1\mathbin\|1^{n−1}$ or $0\mathbin\|0^{n−1}$ and $1\mathbin\|0^{n−1}$ and can therefore still distinguish the messages, if $n>2$?


1 Answer 1


When the oracle gets $(r,s')$ this means that it gets $m' = 0\mathbin\|1^{n−1}$ or $m' = 1\mathbin\|0^{n−1}$ because the oracle sent the adverary either the encryption of $m_0$ or $m_1$ that is $(r,s)$.

$0\mathbin\|0^{n−1}$ or $1\mathbin\|1^{n−1}$ is not the case since the bit flipping doesn't affect the $F$. The oracle will get $(r,s')$ then it will calculate $F(k,r)$, then the stream will be x-ored with $s'$. If we represent the bits by sub-indexes

$$F(k,r) \oplus s' = \left[F(k,r)_0 \oplus \color{red}{s'_0},F(k,r)_1 \oplus s'_1, \ldots, F(k,r)_{n-1} \oplus s'_{n-1}\right]$$ then we have

$$F(k,r) \oplus s' = \left[F(k,r)_0 \oplus \color{red}{\overline{s_0}},F(k,r)_1 \oplus s_1, \ldots, F(k,r)_{n-1} \oplus s_{n-1}\right]$$

As we can see, only one position has affected, the first position.

  • 1
    $\begingroup$ Ahhh I see where I'm wrong. I was thinking about the ciphertext, not the message. It makes sense: Flipping one bit is like XOR with $1||0^{n-1}$. After decryption the PRF negates itself, leaving the message with one flipped bit. Because there are only 2 messages, only 2 messages with flipped bits are possible. Thank you for the fast answer! $\endgroup$
    – Titanlord
    Mar 9, 2021 at 12:20
  • $\begingroup$ @Titanlord Math is hard. To make it easy, always write down the equations. This is what CTR does. The bit flipping doesn't affect the keystream, it affects the message. $\endgroup$
    – kelalaka
    Mar 9, 2021 at 13:00

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.