Is the function defined by $\operatorname{Enc}(k_1,k_2,m) = E(k_1, m)\ \operatorname{XOR}\ E(k_2,m)$ guaranteed to have an inverse function $\operatorname{Dec}$?
We have a definition problem for "inverse function". In the form stated, $\operatorname{Enc}: K \times K \times M \rightarrow C$, and since for a block cipher $|M|=|C|$, the source set for $\operatorname{Enc}$ is larger by a factor $|K|^2$ than the destination set, thus $\operatorname{Enc}$ could be invertible only if $K$ had 1 or no element.
Thus we want to change the question to: does it hold that for all (or is it for some) fixed $(k_1,k_2)$, the function $\operatorname{Enc}_{(k_1,k_2)}: M \rightarrow C$ defined by $\operatorname{Enc}_{(k_1,k_2)}(m)=\operatorname{Enc}(k_1,k_2,m)$ is guaranteed to have an inverse function?
NO in general.
In the "for all" reading, a simple counterexample is $k_1=k_2$: in this case $\operatorname{Enc}_{(k_1,k_2)}(m)$ is always the same element (the all-zero bit vector), thus (unless $M$ has 1 or 0 elements) $\operatorname{Enc}_{(k_1,k_2)}$ is not injective, thus has no inverse function.
Even if we excluded $k_1=k_2$, the answer is still no when $E$ is an arbitrary block cipher. Proof sketch: for a block cipher $E$ construct another $E'$ with a key one bit wider, that ignores the rightmost key bit. Then for any key $k$ for $E$, the couple of keys $(k'_1,k'_2)=(k\mathbin\|0,k\mathbin\|1)$ for $E'$ is a counterexample for $E'$.
If we change "for all" to "for some", then the answer depends on $E$.
- It's possible to exhibit an $E$ such that there's no $(k_1,k_2)$ making $\operatorname{Enc}_{(k_1,k_2)}$ invertible.
- It's also possible to exhibit an $E$ and a $(k_1,k_2)$ such that $\operatorname{Enc}_{(k_1,k_2)}$ is invertible, at least if we make no security claim on $E$.
Remark: If we model $E_{k_1}$ and $E_{k_2}$ as pseudo-random permutations, then for fixed $(k_1,k_2)$ the probability that $\operatorname{Enc}_{(k_1,k_2)}$ is invertible decreases exponentially with $|M|$. Thus if $\log_2|K|$ and $\log_2|M|$ grow in proportion (e.g. the key is at most twice as large as the block size, as in all variants of AES), the probability that any $(k_1,k_2)$ makes $\operatorname{Enc}_{(k_1,k_2)}$ invertible is vanishingly small.
The title asks something significantly different:
Is the XOR two block ciphers still a block cipher?
The difference is that we now consider two block ciphers rather than one. The answer is still NO in general; NO with "for all" $(k_1,k_2)$; and it depends on the block ciphers but no for practical ones with "for some".
The second part of the question thus is:
If $\operatorname{Enc}_{(k_1,k_2)}$ has an inverse function, then what is $\operatorname{Dec}(k_1,k_2,c)$?
For the natural definition of $\operatorname{Dec}$, the quantity $\operatorname{Dec}(k_1,k_2,c)$ is the element $m$ of $M$ such that $E(k_1, m)\ \operatorname{XOR}\ E(k_2,m)$ equals $c$. The hypothesis "has an inverse function" makes such $m$ defined and unique.
And how would we compute $m$ knowing $k_1$, $k_2$, and $c$?
When seeing $E$ as a black box, one way is to try all values of $m$ in $M$ (say, incrementally) until finding one that fits (which is unique under the hypothesis that $\operatorname{Enc}_{(k_1,k_2)}$ has an inverse). This search of $m$ has cost linear in $|M|$, thus is possible only for relatively small message space (e.g. a 32-bit or 48-bit block cipher). Although practical block ciphers with such small block size have been proposed (e.g. Simon, Speck), the remark above would make it a surprise that a $(k_1,k_2)$ exists making $\operatorname{Enc}_{(k_1,k_2)}$ invertible for such block ciphers, and finding one would be tantamount to a break of the block cipher.
I conjecture that it can be proven that even with black box access to both the encryption $E$ and matching decryption function $D$, there's no sub-exponential algorithm to find $m$ such that $\operatorname{Enc}_{(k_1,k_2)}=c$ when there's such $m$, which is for a sizable fraction of $c$.
