Are the following schemes based on a pseudo-random permutation secure? I am currently working on the following task:

Let F be a pseudorandom permutation.

Consider the encryption scheme for the message space $\{0, 1\}^n$ defined as follows: $Gen(1^n)$ chooses two random keys $k_1 , k_2  \in \{0, 1\}^n$. Encryption is done as $Enc_{k_1,k_2}(m) = F_{k1}( k_2 \oplus m)$  (Decryption is done in the natural way)

Does this scheme have indistinguishable encryptions in the presence of an eavesdropper? Is this scheme CPA-secure?

Consider the encryption scheme where the message space is $\{0, 1\}^{n/2}$ and encryption of a message $m$ is done by choosing random $r \leftarrow \{0, 1\}^{n/2}$ , and then outputting the ciphertext $F_k(r ||m)$. (Decryption is done in the natural way)

Does this scheme have indistinguishable encryptions in the presence of an eavesdropper? Is this scheme CPA-secure?

My current answers are:

This scheme has indistinguishable encryptions in the presence of an eavesdropper since $F$ is a PRP, and therefore $F_{k1}( k_2 \oplus m)$ will give a pseudorandom string. However I am not sure whether my intuition is correct.
The scheme should not be IND-CPA secure since encryption is deterministic.

This scheme is both IND-COA as well as IND-CPA secure. IND-COA since (as in 1.) $F$ is a PRP, and therefore $F_k(r ||m)$ will give a pseudorandom string. It's also IND-CPA secure as a random $r$ is used every time a message in encrypted.


Since I am not too confident about my solutions I appreciate any comments and/or corrections.
Looks rather OK to me.



As for the first question, XOR with a value won't introduce any duplicate values and now $F$ is a PRP the first part of the answer should be correct. It's clearly deterministic, so no IND-COA or CPA security.



As for the second question $F_k(r ||m)$ seems to me identical to a single block encrypt with CTR mode. However, for CTR mode you require quite a large block size.

You could well distinguish between $m=0$ and $m=1$ given enough ciphertext; you'd get a lot of 00 and 10 results if $m=0$ is prevalent, which would be different from the 01 and 11 results. Concatenation in general should be considered dangerous.

So I think it could be CPA secure, but only when $n$ is somewhere around 128 bits or higher and/or the amount of messages is restricted. Without additional restrictions the answer should be no IND-COA or CPA security. Learning that a particular value is prevalent is already enough to break IND-COA:

e.g from Wikipedia about ciphertext-only attacks:


  The ability to obtain any information at all about the underlying plaintext beyond what was pre-known to the attacker is still considered a success.