<p>It turns out that <span class="math-container">$m=2n$</span> 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 <span class="math-container">$E:\mathbb{F}_2^n\to \mathbb{F}_2^m$</span> such that the set of elements <span class="math-container">$\{E(\mathbf{x})\}_{\mathbf{x}\in \mathbb{F}_2^n}$</span> forms a <em>Sidon set</em> in the group <span class="math-container">$(\mathbb{F}^m_2,+)$</span> (a Sidon set of an abelian group <span class="math-container">$(G,*)$</span> is a set of elements <span class="math-container">$A$</span> such that <span class="math-container">$\vert A + A\vert$</span> is maximal, meaning that for <span class="math-container">$i\neq j$</span>, <span class="math-container">$a_i+a_j=a_{i'}+a_{j'}$</span> if and only if <span class="math-container">$\{i,j\}=\{i',j'\}$</span>).</p>
<p>It turns out that the size of the largest Sidon set in <span class="math-container">$\mathbb{F}_2^{2k}$</span> is at least <span class="math-container">$2^k$</span>, and can be explicitly obtained from the following construction of <a href="https://core.ac.uk/download/pdf/82054677.pdf" rel="noreferrer">Lindström</a> (see also this more recent paper by <a href="https://arxiv.org/pdf/1710.08228.pdf" rel="noreferrer">Sidorenko</a> on related topics): consider all elements of the form <span class="math-container">$(\mathbf{x},\mathbf{x}^3)$</span> where we express <span class="math-container">$\mathbf{x}\in GF(2^k)$</span> as a <span class="math-container">$k$</span>-dimensional vector over <span class="math-container">$\mathbb{F}_2$</span> with respect to some basis. It turns out that this forms a Sidon set, and moreover, given <span class="math-container">$(\mathbf{x},\mathbf{x}^3)+(\mathbf{y},\mathbf{y}^3)=(\mathbf{u},\mathbf{v})$</span>, one can solve for <span class="math-container">$\mathbf{x}$</span> (and therefore <span class="math-container">$\mathbf{y}$</span>) by solving a quadratic equation in <span class="math-container">$GF(2^k)$</span>. I'm <em>guessing</em> this can be done in <span class="math-container">$\text{poly}(k)$</span> time if you're principled about the construction/representation of <span class="math-container">$GF(2^k)$</span>, but note that this isn't super trivial because the field has characteristic two so the quadratic formula won't help (see <a href="https://www.staff.uni-mainz.de/pommeren/MathMisc/QuGlChar2.pdf" rel="noreferrer">this</a> for potentially more info).</p>
<p>Moving back to your case, this means that the encoding <span class="math-container">$\mathbf{x}\mapsto (\mathbf{x},\mathbf{x}^3)$</span> when interpreting <span class="math-container">$\mathbf{x}\in GF(2^n)$</span> should give you what you want.</p>

CC BY-SA 4.0
2021-03-18T23:35:18.970Z
2021-03-18T23:35:18.970Z
Jason Gaitonde
<p>Thank you <a href="https://cstheory.stackexchange.com/users/53196/j-g">J.G</a> for your answer. For the sake of completeness and to make sure I am not missing anything, I decided to explicitly describe the decoding process. Please feel free to correct me if anything is wrong.</p>
<p>First of all, my suggestion earlier to map <span class="math-container">$x\to\left(x,x^2\right)$</span> could not possibly work since <span class="math-container">$\left(x+y\right)^2=x^2+y^2$</span> over <span class="math-container">$GF(2^n)$</span>, thus <span class="math-container">$x^2+y^2$</span> adds no new information over <span class="math-container">$x+y$</span>.</p>
<p>Now say that <span class="math-container">$(x+y,x^3+y^3)=(u,v)$</span>, then <span class="math-container">$u^3=(x+y)^3=x^3+x^2y+y^2x+y^3=v+u\cdot xy$</span>, namely, <span class="math-container">$xy=u^2-v/u$</span>. It follows that <span class="math-container">$x(u-x)=u^2-v/u$</span>, and thus <span class="math-container">$x^2+ux+(u^2+v/u)=0$</span>, which is our quadratic equation.<br />
To solve it, let us divide by <span class="math-container">$u^2$</span> and substitute <span class="math-container">$t:=x/u$</span> to get <span class="math-container">$t^2+t=(1+v/u^3)$</span>. Finally, note that <span class="math-container">$t\to t^2+t$</span> is a linear transformation since <span class="math-container">$(a+b)^2=a^2+b^2$</span>, hence we only need to solve a set of linear equations, which can be done efficiently. It should also be mentioned that all arithmetic in <span class="math-container">$GF(2^n)$</span> is efficiently computable.</p>

CC BY-SA 4.0
2021-03-20T12:32:27.683Z
2021-03-20T12:32:27.683Z
Nathan
<p>I am looking for an efficient encoding algorithm <span class="math-container">$E:\{0,1\}^n\to\{0,1\}^m$</span> such that given <span class="math-container">$E(x)\oplus E(y)$</span> for <span class="math-container">$x\neq y$</span>, we can reconstruct <span class="math-container">$x$</span> and <span class="math-container">$y$</span>.<br />
One example of such an algorithm would be mapping from <span class="math-container">$\{0,1\}^n$</span> to <span class="math-container">$\{0,1\}^{2^n}$</span> using a unit vector with <span class="math-container">$1$</span> only at the input coordinate. However, this is not an efficient solution in <span class="math-container">$n$</span>.<br />
I thought of maybe working over <span class="math-container">$GF(2^n)$</span> and mapping <span class="math-container">$x$</span> to <span class="math-container">$x^2,x$</span> or something of the sort, but I do not know if we can reconstruct efficiently and with certainty <span class="math-container">$x,y$</span> from <span class="math-container">$x^2+y^2,x+y$</span>.</p>
<p>What do you think?<br />
Thanks</p>

<co.combinatorics>
XOR Resilient Encoding
Nathan
# XOR Resilient Encoding

(Asked by: username_0 on 2021-03-18)

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

**Tags:** co.combinatorics


---

## 2 answers

### Answer by username_1 on 2021-03-18. Score: 5 | Accepted answer

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](https://core.ac.uk/download/pdf/82054677.pdf) (see also this more recent paper by [Sidorenko](https://arxiv.org/pdf/1710.08228.pdf) 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](https://www.staff.uni-mainz.de/pommeren/MathMisc/QuGlChar2.pdf) 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.


---

### Answer by username_0 on 2021-03-20. Score: 0

Thank you [J.G](https://cstheory.stackexchange.com/users/53196/j-g) for your answer. For the sake of completeness and to make sure I am not missing anything, I decided to explicitly describe the decoding process. Please feel free to correct me if anything is wrong.

First of all, my suggestion earlier to map $x\to\left(x,x^2\right)$ could not possibly work since $\left(x+y\right)^2=x^2+y^2$ over $GF(2^n)$, thus $x^2+y^2$ adds no new information over $x+y$.

Now say that $(x+y,x^3+y^3)=(u,v)$, then $u^3=(x+y)^3=x^3+x^2y+y^2x+y^3=v+u\cdot xy$, namely, $xy=u^2-v/u$. It follows that $x(u-x)=u^2-v/u$, and thus $x^2+ux+(u^2+v/u)=0$, which is our quadratic equation.  
To solve it, let us divide by $u^2$ and substitute $t:=x/u$ to get $t^2+t=(1+v/u^3)$. Finally, note that $t\to t^2+t$ is a linear transformation since $(a+b)^2=a^2+b^2$, hence we only need to solve a set of linear equations, which can be done efficiently. It should also be mentioned that all arithmetic in $GF(2^n)$ is efficiently computable.


---

