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.
In the comments you wrote:
.. $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:
