Stuck at another cryptography problem

Cryptography 2018-08-28

I launched my attack on the problem set on chapter 3 of A Graduate Course in Applied Cryptography, just found myself to be stuck at the very first problem¹. I am légume! (That was a pun. If you translate it into Chinese it means “I am not smart”.) The problem was kind of interesting, so I wish to post it here.

Background

To understand the problem, readers should be familiar with the concept of Semantic Security.

The first problem

Suppose you had a cipher $\mathcal{E} = (E, D)$ which is semantically secure for random messages. That is, any adversary $A$ in the following game has negligible advantage.

$C$ generates $k \xleftarrow{R} \mathcal{K}$ , $(m_0,m_1) \xleftarrow{R} \mathcal{M}^2, b \xleftarrow{R} \{0, 1\}, c \leftarrow E(k, m_b)$ and sends them to $A$ .
$A$ outputs a bit $\hat{b}$ and wins iff $\hat{b} = b$ .

This security is apparently weaker than security in ordinary models where messages are chosen by the adversaries. However, part (a) asks you to construct a cipher $\mathcal{E}' = (E', D')$ that is semantically secure in the ordinary sense, from the cipher $\mathcal{E}$ . The new cipher should be defined over $(K', M', C')$ where $K' = K$ and $M' = M = \{0, 1\}^L$ . Part (b) asks the reader to construct a cipher that is secure for random messages but not secure in the ordinary sense.

Solution to (a)

Part (b) can be easily shown by using a construction I made in the past problem set and is left to the blog readers. I stucked on part (a) for most of the time. I believe my first intuition was the correct construction, but I abandoned it before checking its vaildity and moved on to complicated constructions that won’t work. But after struggling a while I still cannot prove the security of it.

The construction ( spoiler alert )
The construction is very similar to ciphers using nonces. For each encryption query, let $n$ be a randomly generated message (as a bit-string), then define $E'(k, m) = (E(k, m \oplus n), n)$ and $D'(k, (c, c')) = D(k, c) \oplus c'$ . It is definitely a well-defined cipher with the required domains.

I wanted to show that it is sematically secure in the ordinary sense, suppose the contrary. Then we had an adversary $A$ attacking this cipher with non-negligible advantage SSAdv $(A, \mathcal{E}')$ . We construct the following adversary $B$ .

From its challenger receive $c, m_0, m_1$ , from $A$ receive $M_0, M_1$ .
Send $(c, m_0 \oplus M_0)$ to $A$ and output $A$ ’s answer.

Then,
$\begin{aligned} \Pr[B\text{ is correct}] = \frac{1}{2}\Pr[A \text{ is correct}| b = 0] + \frac{1}{2}\Pr[A \text{ is correct}| b = 1] \end{aligned}$ .

If we can show that $\Pr[A$ is correct $\vert b = 1] \ge \frac{1}{2}$ then we are done because the first term is at least $\frac{1}{4} + \frac{1}{2} \epsilon$ for some non-negligible $\epsilon$ . But I do not think this can be proven in any way. The core problem seems to be the fact that we did not tight $m_b$ with the corresponding $M_b$ in the ciphertext in a way that is satisfying. Or maybe is the construction just plain wrong?

Updated (But incorrect argument)
It suddenly appeared to me that the above construction was indeed correct! Look at the last equality. The probability that $A$ gets the correct guess is exactly $\frac{1}{2}$ for the second term because the ciphertext sent to A, which is $(E(k, m_1), m_0 \oplus M_0)$ , as seen from the perspective of $A$ is just two random strings. So it gives no information about $b$ and thus the probability is exactly $\frac{1}{2}$ .

Using this fact, the advantage of B turns out to be $\frac{1}{2}(1 + \epsilon)$ which is non-negligible, that completes the proof.

Correct construction

The above argument was wrong because you cannot simply jump to the conclusion that “So it gives no information about $b$ and thus the probability is exactly $\frac{1}{2}$ ”. Indeed, adversary may be able to distinguish ciphertexts random input ( $b = 1$ ) from ciphertexts of a fixed input ( $b = 0$ ).

The original reduction was nearly correct. We only need to modify $B$ such that it flips a coin $\tilde{b}$ to decide which $m_{\tilde{b}} \oplus M_{\tilde{b}}$ to append to the ciphertext before giving to $A$ .

Let $x$ be the probability that given a ciphertext of a random message, $A$ outputs 0.

Then we have $\begin{aligned} \Pr[B\text{ is correct}] &= \Pr[\tilde{b} = b] \Pr[A\text{ is correct}] + \Pr[\tilde{b} = 0 \wedge b = 1](1 - x) + \Pr[\tilde{b} = 1 \wedge b = 0] x\\ &= \frac{1}{2}(1 + \epsilon) \end{aligned}$
The equality is due to the fact that when $\tilde{b} \neq b$ , we are essentially giving a random ciphertext to $A$ .

So $B$ has non-negligible advantage.

Reference

Problem 3.1 of A Graduate Course in Applied Cryptography ↩