Assume $\Pi$ is a CPA secure scheme. Let $\Pi'$ be a derived scheme, such that the encryption of a message $M$ is as follows:
$Enc_{\Pi'(k)}(M) = Enc_{\Pi(k)}(M) || LSB(k)$, where
$LSB(k)$ is the least significant bit of the randomly chosen key.
Can someone help me to finish my proof that the $\Pi'$ scheme is also CPA secure?
My proof:
Assume the contrary, $\Pi'$ is not CPA secure. Then the adversary can find two messages $M_0$ and $M_1$, such that whenever a challenger returns him $C'_b = Enc_{\Pi'(k)}(M_b)$, he can guess correctly the randomly chosen bit $b$ with the probability higher than $\frac{1}{2} + 2\epsilon_{fixed}$.
Now the adversary wants to win a game for $\Pi$ against me. He sends me those two messages $M_0$ and $M_1$. He asks me to randomly pick a bit b and return $C_b = Enc_{\Pi(k)}(M_b)$. The adversary then guesses the LSB(k):
With probability $\frac{1}{2}$ he will have guessed the LSB(k) correctly. Thus, he knows the value of $C'_b$ and can guess the bit $b$ with probability higher than $\frac{1}{2} + 2\epsilon_{fixed}$
With probability $\frac{1}{2}$ he will have guessed the LSB(k) incorrectly.
In this case, he will guess the bit b with probability 1/2. // Why?
Hence, the adversary can guess the bit b correctly with probability $p > \frac{1}{2}(\frac{1}{2} + 2\epsilon_{fixed}) + \frac{1}{2}(\frac{1}{2}) = \frac{1}{2} + \epsilon_{fixed}$. This contradicts the assumption that $\Pi$ is CPA secure.
$\square$
The part I struggle to prove is why when the adversary has guessed the wrong $LSB(k)$ bit, he can still guess the correct $b$ with probablity $\frac{1}{2}$. For example, suppose the adversary runs an algorithm $\alpha$ to guess a bit $b$ when being challenged to win a game for $\Pi'$:
If we return him $C$ that equals $Enc_{\Pi'(k)}(M_b)$, then $\alpha$ guesses correct $b$ with probability 0.6
If we return him $C$ that differs from $Enc_{\Pi'(k)}(M_b)$ in the last bit, then $\alpha$ guesses correct $b$ with probability 0.
So now the adversary with the $\alpha$ algorithm would win the CPA game for $\Pi'$, because the game rules force us to send the correct ciphertext $C$. However, $\alpha$ used in the way described in the proof will not win the CPA game for $\Pi$ because $\frac{1}{2} 0.6 + \frac{1}{2} 0 < \frac{1}{2}$
So what I want to ask is why we can always find a better algorithm than $\alpha$?