Is $x^2+x+1 (mod 2)$ a one-way function? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:00:47Z https://cs.stackexchange.com/feeds/question/82847 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/82847 1 Is $x^2+x+1 (mod 2)$ a one-way function? AdC https://cs.stackexchange.com/users/56857 2017-10-22T18:01:45Z 2017-10-25T11:35:05Z <p>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. </p> <p>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)$.</p> <p>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 ? </p> https://cs.stackexchange.com/questions/82847/is-x2x1-mod-2-a-one-way-function/82848#82848 2 Answer by Yuval Filmus for Is $x^2+x+1 (mod 2)$ a one-way function? Yuval Filmus https://cs.stackexchange.com/users/683 2017-10-22T18:37:38Z 2017-10-23T14:37:11Z <p>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.</p> <hr> <p>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.</p>