Security of block cipher PRP(k⊕m)⊕k

Question

Let $\mathcal S=\{0,1\}^n$ be the set of bitstrinsg of $n$ bits (for security parameter $n$). Let $P$ be a public Pseudo-Random Permutation of $\mathcal S$, efficiently computable in both directions.

Construct a block cipher $E$ with message and key domains $\mathcal S$ as $$\begin{align} E:\mathcal S\times\mathcal S\to\;&\mathcal S\\ (k,m)\mapsto\;&E(k,m)\underset{\text{def}}=P(k\oplus m)\oplus k\\ \end{align}$$ What can we prove about the security (under Chosen Ciphertext Attack, or orther) of that block cipher?

Update: that's known as the single-key variant of the Even-Mansour scheme. The original scheme has two independent input and output keys. The reference article is Shimon Even and Yishay Mansour's A construction of a cipher from a single pseudorandom permutation, in Journal of Cryptology, 1997, originally in proceedings of Asiacrypt 1991.

^{Note: I still welcome a reference, or better a proof, for the single key variant.}

---

Can one break (find a practical distinguisher of) $E$ for the following candidate instantiation of $P$?

Restrict to $n$ with $p=2^n+3$ prime (see A057732 for values, some multiple of $8$ and even $16$). Let $e$ be $3$ (resp. $5$) for odd (resp. even) $n$, which insures $\gcd(e,p-1)=1$. Assimilate elements of $\mathcal S$ to integers. Define $$\begin{align} Q:S\to\;&\mathcal S\\ m\mapsto\;&Q(m)\underset{\text{def}}=((m+2)^e\bmod p)-2 \end{align}$$ That's a permutation of $\mathcal S$, but not a good enough PRP for the application (that makes an interesting exercise. Hint: What's $Q(m)+Q(2^n-1-m)$ ?)

Let $a$ and $b$ be two $n$-bit nothing-up-my-sleeves constants, e.g. $a=\left\lfloor\pi\,2^{n-2}\right\rfloor$ and $b=\left\lfloor2^{n-1/2}\right\rfloor$. Define $$\begin{align} P:\mathcal S\to\;&\mathcal S\\ m\mapsto\;&P(m)\underset{\text{def}}=Q((Q(m)+a\bmod 2^n)\oplus b)\\ \end{align}$$

Vague rationale: insert the non-linear $x\mapsto (x+a\bmod 2^n)\oplus b$ between two instances of $Q$ providing the diffusion. $a\ne0$ is necessary for security, but so far I have no break for $(a,b)=(1,0)$.

^{Note: I only created a security system so clever that I can't imagine a way of breaking it. The most clueless amateur can, as observed by Bruce Schneier. That second part of the question if thus off-topic, and I'd understand downvotes!}

Answer 1

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: "Minimalism in Cryptography: The Even-Mansour Scheme Revisited" 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.