# Is $x^2+x+1 (mod 2)$ a one-way function?

Given that $x^2+x+1 (mod 2) = 1$ and $x^2+x (mod 2) = 0$ for ${|x\rangle}_{x=0,1} \xrightarrow{F} \frac{1}{\sqrt{2}}[(-1)^{x}|x \rangle + |1-x \rangle]$ (Fourier transform). So, the 1-1 correspondence $x^2+x+1 = NOT(x^2+x)$ holds over $F_{2^3}$, where the input is the zero polynomial $x^2+x$ and the output is the positive polynomial $x^2+x+1$ (arXiv:1609.01541, eprint.iacr.org/2017/681). Notice that the bijection $x^2+x+1 (mod 2)$ = $x^2 \oplus x \oplus 1$ = $x \land x \oplus x \oplus 1$ = $x \oplus x \oplus 1$ = $x \oplus NOT(x)$, which corresponds to a coin toss.

It is important to note that the construction works for bit strings of any length because any positive polynomial is reduced to $x^2+x+1(mod2)$ and any zero polynomial is reduced to $x^2+x(mod2)$.

Considering that pseudorandom generators exist if and only if one-way functions exist (pseudorandom generator theorem) is $x^2+x+1 (mod 2)$ a one-way function ?

• The concept of one-way functions is usually defined in an asymptotic setting: it doesn't apply to what you have defined since it's a function from {0, 1} into {0, 1}. You should define a family of functions for arbitrarily high size of input. – quicksort Oct 22 '17 at 18:30
• Thanks. But, it is important to note that the construction works for bit strings (inputs) of any length because any positive polynomial is reduced to $x^2+x+1(mod2)$ and any zero polynomial is reduced to $x^2+x(mod2)$. – AdC Oct 23 '17 at 12:43

A one-way function is a function from $\{0,1\}^*$ to $\{0,1\}^*$ which satisfies certain properties. Your function only accepts a single bit as input, so in particular isn't a one-way function.
We don't know whether one-way functions exist, though many people conjecture that they do. Proving that one-way functions exist is harder than proving $\mathsf{P} \neq \mathsf{NP}$, that is, if one-way functions exist then $\mathsf{P} \neq \mathsf{NP}$. Therefore proving that a given function is one-way is expected to be very difficult, though some candidates do exist.
• Thanks. But, it is important to note that the construction works for bit strings (inputs) of any length because any positive polynomial is reduced to $x^2+x+1(mod2)$ and any zero polynomial is reduced to $x^2+x(mod2)$. – AdC Oct 23 '17 at 12:42