# Question on the disprove of CCA security

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$$?

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]$$
• 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! Mar 9, 2021 at 12:20