Is there any block cipher which is also a pseudo-random-permutation over the key

Question

As block ciphers are defined as a pseudo-random-permutation over the data (keyed with the key), I was wondering, if there are also constructions for which key and data can be switched and the cipher is a permutation over the key space for a fixed (data) input?

So the question is, if the output space of $E_k(a)$ for all possible $k$ covers the entire space of $\{0,1\}^n$

More formally:

$E_k$ is a block cipher with key size equal to block size: $\{ 0, 1 \}^n \times \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^n $

and $\exists a \forall k_1, k_2: E_{k_1}(a) = E_{k_2}(a) \Rightarrow k_1 = k_2$

Or more generally: with $f$ a function $\{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^n$

$\forall k_1, k_2: E_{k_1}(f(k_1)) = E_{k_2}(f(k_2)) \Rightarrow k_1 = k_2$

Or is this even true for every block cipher?

Answer 1

I am not sure about the "more generally" since in the latter definition you are applying a function of the key. This now makes it related to circular security. Regarding the basic question, this is not true in general, and I don't know if it's possible to build such a construction. What I can say is that there is a construction where the pseudorandomness property holds if the key is random OR if the data is random. This notion is studied in the paper Symmetric and Dual PRFs from Standard Assumptions: A Generic Validation of an HMAC Assumption by Mihir Bellare and Anna Lysyanskaya. This paper would be a good starting point for research.