How to rigorously prove that $Enc_{\Pi'(k)}(M) = Enc_{\Pi(k)}(M) || LSB(k)$ is CPA secure assuming $\Pi$ is?

Question

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

Answer 1

For your question: In this case, he will guess the bit b with probability 1/2. // Why?, I guess this is the point of your proof which is making you doubt it?

This is simply the probability to guess correctly the value of $b$ when you are doing it completely at random: the bit $b$ can only take two values, $0$ and $1$, so if you try a "wild guess" you have probability $\frac{1}{2}$ to get the correct answer, that's it.

So you are correct, you have probability $\frac{1}{2}$ to have an advantage and probability $\frac{1}{2}$ to not have any advantage, which in the end translates in an advantage thanks to the law of total probability, as you described.

Now for your edited question: you say that then α guesses correct b with probability 0 but if this is the case, then the algorithm outputing $\neg\alpha$ would have probability $1-\frac{1}{2}0.6+\frac{1}{2}0 = \frac{1}{2}0.4+\frac{1}{2}1 >\frac{1}{2}$ to find the correct value.
Thus, in practice, the "best" algorithm to win the CPA game will not have probability $0$ to output the correct $b$, since otherwise we could construct a better algorithm (excepted if it had proba 1 to find the correct value in the "equals" case).

---

Now I prefer personally, like tylo, to look at the advantage of the adversary, when dealing with something which is assumed not IND-CPA.

Here I would show that any efficient IND-CPA adversary $\mathcal{A}_{LSB}$ in the LSB case with an advantage of $\epsilon$ can be translated into an IND-CPA adversary $\mathcal{A}$ with polynomially similar efficiency and an advantage of $\frac{\epsilon}{2}$ in the non-LSB case.

This is exactly the same idea as behind Tylo's answer excepted that I formulate it a bit differently:

1. $\mathcal{A}$ poses as a LSB-Challenger, so $\mathcal{A}_{LSB}$ can send him two message $(m_0,m_1)$, as if it were the LSB-Challenger;
2. $\mathcal{A}$ would then send them to the normal Challenger;
3. The Challenger sends back the value $\mathcal{C}=Enc_{\Pi(k)}(m_b)$ to $\mathcal{A}$;
4. $\mathcal{A}$ now flip a coin and get a value $b'$;
5. $\mathcal{A}$ can now pass the value $\mathcal{C}|b'$ as if it were the answer of the LSB-challenger to $\mathcal{A}_{LSB}$;
6. $\mathcal{A}$ returns the same answer as $\mathcal{A}_{LSB}$.

So, $\mathcal{A}_{LSB}$ would have advantage $\epsilon$ to win the game if $b'=LSB(k)$ and would have no specific advantage if $b'\neq LSB(k)$, we have:

$$ \begin{aligned} Adv(\mathcal{A}) =& |P(\mathcal{A}_{LSB} \text{ wins})- P(\mathcal{A}_{LSB} \text{ looses})| \\\geq& P(\mathcal{A}_{LSB} \text{ wins})- P(\mathcal{A}_{LSB} \text{ looses}) \\ =& P(\mathcal{A}_{LSB} \text{ wins} | b'=LSB(k))P[b'=LSB(k)] \\ -& P(\mathcal{A}_{LSB} \text{ looses} | b'=LSB(k))P[b'=LSB(k)] \\ +& P(\mathcal{A}_{LSB} \text{ wins} | b'\neq LSB(k))P[b'\neq LSB(k)] \\ -& P(\mathcal{A}_{LSB} \text{ looses} | b'\neq LSB(k))P[b'\neq LSB(k)] \end{aligned} $$

Coming directly from the law of total probability, too.

But both $b'$ and the key $k$ are chosen uniformly at random from $\{0, 1\}$, so $P(b'\neq LSB(k)) = P(b'= LSB(k)) = \frac{1}{2}$. Now, when the adversary is in the case $b'\neq LSB(k)$ it can at worse try to guess at random, and has proba $\frac{1}{2}$ to both win and loose. This is a valid assumption, since if it were to have the exact inverse probability to win/loose than in the case $b'= LSB(k)$, then we could construct a polynomial adversary trying multiple queries against different $b'$ with fixed $b$ (i.e. our $\mathcal{A}$ would forward $(m_b,m_b)$ for $b$ a bit of its choosing) and determining which $b'$ has the most often correct answers, thus our adversary would have an advantage bigger than $\frac{1}{2}$.

Finally we know that $$|P(\mathcal{A}_{LSB} \text{ wins} | b'=LSB(k))P[b'=LSB(k)] \\ - P(\mathcal{A}_{LSB} \text{ looses} | b'=LSB(k))P[b'=LSB(k)]| = \epsilon$$ by assumption, so we end up with:

$Adv(\mathcal{A}) \geq \epsilon\frac{1}{2} + 0\frac{1}{2} = \frac{\epsilon}{2} $

So if there exists such an adversary for the second scheme, the first scheme would also be broken.

Answer 2

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:

1. $\mathcal{A}$ receives $m_0$ and $m_1$ from $\mathcal{A'}$.
2. $\mathcal{A}$ sends both messages to the encryption oracle of $\Pi$.
3. $\mathcal{A}$ receives a ciphertext $c_b = Enc_{\Pi(k)}(M)$.
4. $\mathcal{A}$ chose a random bit $b_k$ and send $c_b||b_k$ to $\mathcal{A'}$.
5. $\mathcal{A}$ receives a guess $b'$ from $\mathcal{A'}$.
6. $\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$.

Answer 3

In your proof it's not clear (and I can only guess there is an error) which messages you send:

• You can't produce the value $Enc_{\Pi(k)}(M_b)$ yourself
• You need to answer the oracle to win your game (with some advantage).

Your argument is flawed in the sense that you want the original adversary to win the other game and calculate that probability. That doesn't work, because the adversary expects a challenge of the form $Enc_{\Pi(k)}(M_b)||LSB(k)$ and not $Enc_{\Pi(k)}(M_b)$ - and you don't know if there is a different $k'$, s.t. $Enc_{\Pi(k)}(M_b) = Enc_{\Pi(k')}(M_b)||LSB(k')$.

Here's the idea with adversary $\mathcal{A}$ for $\Pi'$ and the challenger $\mathcal{C}$ for $\Pi$ - we act as adversary for $\Pi$ and as challenger for $\Pi'$:

• $\mathcal{A}$ chooses $m_1,m_2$ and sends them to you. We relay those to $\mathcal{C}$.
• We get a challenge of the form $Enc_{\Pi(k)}(M_b)$. We choose a single bit $b'$ randomly, and send $Enc_{\Pi(k)}(M_b)||b'$ to $\mathcal{A}$.
• $\mathcal{A}$ guesses $b$, and we just relay that guess to $\mathcal{C}$.

With probability $1/2$ we guesses $b'$ correctly, s.t. $b' = LSB(k)$. In the other case, the adversary can't do worse than having no advantage. Then we can actually use the formula at the bottom of the question to calculate our advantage - based on the advantage of $\mathcal{A}$.

Answer 4

I'm writing another answer, because it doesn't answer the question asked - it adresses the possible confusion I noticed between the lines.

You wrote

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

I suspect, there is a misconception in the understanding of the advantage. If an algorithm is able to always output the wrong result, then this has exactly the same advantage as an alorithm, which always outputs the correct result. The advantage is not equal to the probability of outputting the correct result (or winning the game). It is a measure about actually finding some hidden information which tips the scales. If an algorithm can reliably find $\bar{b}$, then it's really trivial to adapt this algorithm to find $b$ instead (just invert the output) and vice versa.

It is also really simple to generate a trivial adversary for any algorithm with the lowest possible advantage:

• You know by the definition of the securitay game, some bit $b$ is drawn from a uniform distribution
• The adversary $\mathcal{A}$ ignores any input he gets
• The adversary $\mathcal{A}$ outputs a bit from a fixed distribution (regardless which one). If the adversary always outputs $0,1$ or a randomly drawn bit - it doesn't matter.
• The advantage of this adversary is always $0$: If $b$ is dawn uniformly and $b'$ from any distribution, then $b=b'$ happens with probability $1/2$. The proof is equal to perfect secrecy of OTP.

So when we assume some algorithm $A$ with a non-negligible advantage and generate some algorithm $B$ using $A$ and the advantage is some polynomial of the advantage of $A$, then $B$ also has non-negligible advantage. This is easily explained/ proven by the fact that polynomials are closed under composition (and in most proofs it's even a linear in the original advantage). Formally this can be said as:

• Polynomial functions are not negligible (easy to prove with the definition of negligible functions) - keep in mind, the definition of negligible already includes taking the absolute value, so it doesn't matter if the range is positive or negative. But if you want to be precise, you need to exclude the polynomial $f(x) = 0$
• Polynomials are closed under function composition (if $f(x)$ is a polynomial of degree $k$, g(x) is a polynomial of degree $l$, then $f(g(x))$ is a polynomial of degree $kl$)
• Thus we can state: If some advantage/function $f(x)$ is non-negligible, then for any polynomial g(x) we have that $g(f(x))$ is also non-negligible. In this case $x$ would be the security parameter obviously (you can also use $\lambda$ instead).

Answer 5

This is a very interesting question. I think the answers here reflect the intuition that in real life, if revealing a bit of the secret key were to break an encryption scheme, that encryption scheme would necessarily exhibit a visible bias that revealed that bit, and thereby be unconditionally broken. So if the original scheme is secure, the scheme with a revealed bit must be.

However, the IND-CPA game does not directly allow detection of key biases like this because there is only one key for the entire game, and only one challenge. So the solutions which take a single adversary $\mathcal{A}'$ and feed them a random bit as "LSB(k)" run the risk that they are hurting $\mathcal{A}'$ by getting the bit wrong just as much as they'd help it by getting the bit right -- and since they are in one of these two cases with 50% probability, they can't then infer anything about $\mathcal{A}'s$ behaviour!

(By the way, it is not stated whether we are working with asymmetric or symmetric encryption. I assume the symmetric case because it's hard to define revealing one bit of the key like this in the asymmetric case. The difference is simply that the symmetric case allows $\mathcal{A}'$ to make encryption queries.)

With all this said, here is my solution. We have a probabilistic polynomial time (p.p.t.) adversary $\mathcal{A}'$ which can break $\Pi'$ and we produce a p.p.t. simulator $\mathcal{A}$ which can break $\Pi$ using it. $\mathcal{A}$ works as follows, and can break $\Pi$ with the same probability $\epsilon$ as $\mathcal{A}'$ can break $\Pi'$.

1. Immediately $\mathcal{A}$ forks $\mathcal{A}'$ into $2n$ copies $\mathcal{A}'_n$, where $n$ is some positive integer.

2. For all $i$, $\mathcal{A}$ responds to encryption queries from $\mathcal{A}'_i$ by forwarding them to its IND-CPA challenger. For even $i$ it appends a zero bit to the response and for odd $i$ it appends a one bit, and forwards it to $\mathcal{A}'_i$.

3. For $i>2$, when $\mathcal{A}'_i$ makes a challenge query $(m_0, m_1)$, $\mathcal{A}$ flips a random bit $b$, queries its IND-CPA challenger for an encryption of $m_b$, appends the appropriate bit to the response according to the parity of $i$, and gives this to $\mathcal{A}'_i$. Then $\mathcal{A}'_i$ replies with a guess for $b$ and $\mathcal{A}$ notes whether this is correct.

4. For $i\in\{1,2\}$, if $\mathcal{A}'_i$ gives a challenge query $(m_0, m_1)$, $\mathcal{A}$ responds as follows.

   • $\mathcal{A}$ waits first for all $\mathcal{A}_i'$, $i>2$, to make their challenge queries, and replies as in step (3).
   • If the odd $\mathcal{A}_i$'s were correct with higher frequency than the evens, it sets $k' = 1$. Otherwise it sets $k' = 0$. If the odds and evens were tied it chooses $k'$ randomly.
   • If $i = k'$ it responds by forwarding the challenge to the IND-CPA challenger, appending $k'$ to the reply, and forwarding this to $\mathcal{A}'_i$. It forwards the reply bit to the IND-CPA challenger.
   • Otherwise it aborts $\mathcal{A}'_i$ and waits for the other one to make a challenge.

The intuition here is that we're first doing a majority-rules of the adversaries to which we're claiming $LSB(k) = 0$ and those to which we're claiming $LSB(k) = 1$, then using the winning bit for our "real" challenge.

The reason this scheme works is simple, though it uses some heavy machinery, and I haven't followed through to get exact numbers.

First, suppose that $\mathcal{A}'$ wins with probability $\frac12+\alpha$ when given the correct bit and probability $\frac12+\beta$ when given the wrong one. By hypothesis, since $\mathcal{A}'$ can break $\Pi'$, one of $\{\alpha,\beta\}$ is non-negligible, and since $\Pi$ is IND-CPA, $\alpha + \beta = negl$ (otherwise you coud break $\Pi$ by just appending a random bit to its ciphertexts and giving the result to $\mathcal{A}'$). We conclude that $\epsilon = \max\{\alpha,\beta\}$ is positive and non-negligible.

By the central limit theorem, for $n$ large enough, can can get the number of wins by the correct parity arbitrarily close (percentage-wise) to $2n(1/2 + \alpha)$ and the number of wins by the incorrect parity arbitrarily close to $2n(1/2 + \beta)$. So the majority winner will, with probability close to 1, be the one with advantage $\epsilon$. The result then follows.

Addendum: We observe critically that $n$ must be at least 1, which by construction means that $\mathcal{A}$ does twice as much work as $\mathcal{A}'$. I initially worried about getting same probability $\epsilon$, because doesn't that imply inductively that you could reveal the whole key without changing the attacker's advantage, leading to a reductio ad absurdum? The answer is no, because the above algorithm applied to a variant $\Pi'$ that exposed $n$ bits would need to do $2^n$ work, and therefore not be probabilistic polynomial time.