Are the following schemes based on a pseudo-random permutation secure?
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.