Prove that the following private-key encryption scheme is not CPA-secure

Consider the following private-key encryption scheme : The shared key is k $\in$ {0,1}n. To encrypt the message m $\in$ {0,1}n, choose random r $\in$ {0,1}n and output $(r, F_r(k)\oplus \overline{m})$, where $F$ is a block cipher and $\overline{m}$ is the bit-wise compliment of m. Is this scheme CPA secure?

What is the importance of bit-wise compliment in this question?

Also, it does seem that the scheme is CPA secure because one is performing a $\oplus$ of a message string and a random string (it would change for every message as we pick a random r for each m)

As aventurin pointed out, the scheme as written is not CPA secure.

As poncho's comment pointes out, it is not even secure against known plaintext attacks:

Knowing any pair $(m,c)$ with $c = (c_1,c_2) = (r,F_r(k)\oplus \bar{m})$ gives the attacker $k$ directly:

$$k = F^{-1}_{c_1}(c_2 \oplus \bar{m})$$

What is the importance of bit-wise compliment in this question?

Nothing. Bitwise complement is a fixed bijective mapping, which everyone can evaluate on every input and in either direction. With regards to security, (in this context) this is as useful as the identity function.

.. $F$ being an OWF ... PRF, apologies ...

In the original question $F$ was a block cipher. If we consider $F$ as a PRP (common model for block ciphers), the above still holds: An attacker on a PRP usually gets an oracle for both $F(x)$ and $F^{-1}(x)$.

However, if we assume a PRF the attacker does not get the oracle for $F^{-1}$, so the above attack doesn't work any more. But the construction can not be reduced to the security definition of a PRF either: Usually you would assume an attacker for your scheme and then show that this attacker could also break the PRF property. But:

• In the PRF game, the attacker is allowed to query the function on arbitrary input $x$ for $F(x)$. The answer is always either from a truly random function or $F_k(x)$ for a fixed $k$.
• In your scheme the attacker could request multiple ciphertexts for the same $k$, but that would result in multiple queries of the form of $F_r(x)$ with $x = k$ fixed.

That just does not fit, and it's unlikely we could prove or disprove the claim - without making further assumptions.

If we consider $k$ and $x$ as two inputs to the function and the random function just doesn't use $k$, then the stanard PRF only allows queries on the second input. What you need in your case would be a dual PRF, where the attacker is given oracle access to changes in both inputs. You can find more information about this:

• Thank You for the detailed explanation. I asked the Professor and it turns out that it was indeed a block cipher - which is a PRP. I had wrongly assumed that a block cipher is based on a PRF, as in his lecture, he'd taught modes of operation just right after PRFs. Mar 13 '17 at 20:45

If you choose $m = (1, \ldots, 1)_n$ then

$$(r, F_r(k) \oplus \overline{m}) = (r, F_r(k) \oplus (0, \ldots, 0)_n) = (r, F_r(k))$$

what reveals $k$.

• Actually, this works as a known plaintext attack Feb 8 '17 at 23:35
• Does this mean that we have to try all possible combinations of n bit strings and see which one gives $F_r(k)$ (and since n is small, this is possible)? Feb 9 '17 at 7:07
• If I understand the formula in your question right, we have $r$ and $F_r(k)$ in the output, whereby $F_r(k)$ is the shared key encrypted with the random value $r$. Therefore you can use $r$ to decrypt $F_r(k)$ and get $k$. Feb 9 '17 at 16:31
• 'r to decrypt $F_r(k)$' - We know r, We know $F_r(.)$ - i.e. whatever input we give to the function $F$ with the key $r$, we'll get the output. And $F$ being an OWF, need not be invertible. So to get the shared key $k$, the only way is to perform $F_r(({0,1})^n)$ and see which of these is equal to $F_r(k)$. But isn't this exponential in $n$ - There would be $2^n$ combinations to try out. Or is there any other way? Feb 10 '17 at 5:04
• You wrote that $F$ is a block cipher. So I assumed that it could be inverted. Feb 10 '17 at 21:34