3
$\begingroup$

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

$\endgroup$
0
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Thank you 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.