XOR Resilient Encoding I am looking for an efficient encoding algorithm $E:\{0,1\}^n\to\{0,1\}^m$ such that given $E(x)\oplus E(y)$ for $x\neq y$, we can reconstruct $x$ and $y$.
One example of such an algorithm would be mapping from $\{0,1\}^n$ to $\{0,1\}^{2^n}$ using a unit vector with $1$ only at the input coordinate. However, this is not an efficient solution in $n$.
I thought of maybe working over $GF(2^n)$ and mapping $x$ to $x^2,x$ or something of the sort, but I do not know if we can reconstruct efficiently and with certainty $x,y$ from $x^2+y^2,x+y$.
What do you think?
Thanks
It turns out that $m=2n$ is possible, and this can be done explicitly in a very related fashion to your idea. It's not hard to see that this is basically optimal. In essence, what you are asking for is an injective map $E:\mathbb{F}_2^n\to \mathbb{F}_2^m$ such that the set of elements $\{E(\mathbf{x})\}_{\mathbf{x}\in \mathbb{F}_2^n}$ forms a Sidon set in the group $(\mathbb{F}^m_2,+)$ (a Sidon set of an abelian group $(G,*)$ is a set of elements $A$ such that $\vert A + A\vert$ is maximal, meaning that for $i\neq j$, $a_i+a_j=a_{i'}+a_{j'}$ if and only if $\{i,j\}=\{i',j'\}$).
It turns out that the size of the largest Sidon set in $\mathbb{F}_2^{2k}$ is at least $2^k$, and can be explicitly obtained from the following construction of Lindström (see also this more recent paper by Sidorenko on related topics): consider all elements of the form $(\mathbf{x},\mathbf{x}^3)$ where we express $\mathbf{x}\in GF(2^k)$ as a $k$-dimensional vector over $\mathbb{F}_2$ with respect to some basis. It turns out that this forms a Sidon set, and moreover, given $(\mathbf{x},\mathbf{x}^3)+(\mathbf{y},\mathbf{y}^3)=(\mathbf{u},\mathbf{v})$, one can solve for $\mathbf{x}$ (and therefore $\mathbf{y}$) by solving a quadratic equation in $GF(2^k)$. I'm guessing this can be done in $\text{poly}(k)$ time if you're principled about the construction/representation of $GF(2^k)$, but note that this isn't super trivial because the field has characteristic two so the quadratic formula won't help (see this for potentially more info).
Moving back to your case, this means that the encoding $\mathbf{x}\mapsto (\mathbf{x},\mathbf{x}^3)$ when interpreting $\mathbf{x}\in GF(2^n)$ should give you what you want.