Question on the disprove of CCA security

Question

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

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.