How to rigorously prove that $Enc_{\Pi'(k)}(M) = Enc_{\Pi(k)}(M) || LSB(k)$ is CPA secure assuming $\Pi$ is? 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 &gt; \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 &lt; \frac{1}{2}$

So what I want to ask is why we can always find a better algorithm than $\alpha$?
We want to prove that 

$\Pi$ is CPA secure $\Rightarrow$ $\Pi'$ is CPA secure.

So, let's prove it using the equivalent contrapositive proposition:

$\Pi'$ isn't CPA secure $\Rightarrow$ $\Pi$ isn't CPA secure.

So, it means we have to suppose that there is an adversary $\mathcal{A'}$ that can win the CPA-game of $\Pi'$ with non negligible probability and then construct some adversary $\mathcal{A}$ to break the CPA security of $\Pi$, in other words,  $\mathcal{A}$ must win the CPA game of $\Pi$. (This is the point you seem to be missing, since you are not interacting with $\Pi$ at all).

So, we construct  $\mathcal{A}$ as follows:


$\mathcal{A}$ receives $m_0$ and $m_1$ from  $\mathcal{A'}$.
$\mathcal{A}$ sends both messages to the encryption oracle of $\Pi$.
$\mathcal{A}$ receives a ciphertext $c_b = Enc_{\Pi(k)}(M)$.
$\mathcal{A}$ chose a random bit $b_k$ and send $c_b||b_k$ to  $\mathcal{A'}$.
$\mathcal{A}$ receives a guess $b'$ from $\mathcal{A'}$.
$\mathcal{A}$ outputs $b'$.


Now, what is the chance that  $\mathcal{A}$ wins CPA game against $\Pi$? It is 
$Pr[b' = b]$, that is equal to 

(i) $Pr[b' = b | b_k = LSB(K)] \cdot Pr[b_k = LSB(K)]$

plus

(ii) $Pr[b' = b | b_k \not =LSB(K)] \cdot Pr[b_k \not = LSB(K)]$

But $Pr[b' = b | b_k = LSB(K)] \ge \frac{1}{2} + \alpha$ for some non-negligible function $\alpha$ (because $\mathcal{A'}$ can breaks $\Pi$). Therefore, (i) is greater than or equal to $(\frac{1}{2} + \alpha)\frac{1}{2}$.

And if $\mathcal{A}$ didn't guess the least significant bit of $K$ correctly, we don't know how $\mathcal{A'}$ would proceed, so, let's say that $Pr[b' = b | b_k \not =LSB(K)]$ is $ \frac{1}{2} + \beta$ some function $\beta$, then, we have that (ii) is equal to $( \frac{1}{2} + \beta ) \frac{1}{2}$.

Therefore,

(i) + (ii) $\ge  \frac{1}{4} + \frac{\alpha}{2} +  \frac{1}{4} + \frac{\beta}{2} = \frac{1}{2} + \frac{\alpha}{2} +  \frac{\beta}{2}$.

If $\beta$ is negligible, then $\alpha \ge \beta$ and then (i) + (ii) $\ge \frac{1}{2} + \frac{\alpha}{2} +  \frac{\alpha}{2} = \frac{1}{2} + \alpha$.

If  $\beta$ is non-negligible, then take $\gamma$ to be the minimun between  $\alpha$ and $\beta$. That way, we get (i) + (ii) $ \ge  \frac{1}{2} + \frac{\gamma}{2} +  \frac{\gamma}{2} = \frac{1}{2} + \gamma$.

In both cases, $\mathcal{A}$ can guess the bit $b$ output by the oracle to $\Pi$ with non-negligible probability, i.e., $\mathcal{A}$ breaks the CPA security of $\Pi$.