Security of block cipher PRP(k⊕m)⊕k
What can we prove about the security (under Chosen Ciphertext Attack, or orther) of that block cipher?

This is the single-key Even-Mansour construction as was already noted in the comments of the question. The latest analysis I could find of this construction is by Orr Dunkelman, Nathan Keller, and Adi Shamir: &quot;Minimalism in Cryptography: The Even-Mansour Scheme Revisited&quot; where they argue that any successful attack satisfies $DT=\Omega(2^n)$ with $D$ being the number of queries to the encryption oracle and $T$ being the number of queries to the permutation itself. This means that the product of these two numbers of queries scales exponentially in the width of the permutation for any attack with constant success probability. This result was also proven in the original work by Even and Mansour for the two-key case.
As for the candidate construction for a public random permutation, one should first note that this model is very close to the random oracle model (but with a permutation instead of a function). This means that any candidate construction can only offer (indirect) heuristic security. I don't have an attack on the permutation at hand though. However this is a model that is sometimes used in cryptography, e.g. in MPC applications, where one would use AES with a fixed key for such needs.