1
$\begingroup$

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 ?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – quicksort Oct 22 '17 at 18:30
  • $\begingroup$ 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)$. $\endgroup$ – AdC Oct 23 '17 at 12:43
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – AdC Oct 23 '17 at 12:42
  • $\begingroup$ It's still not one-way. No function with finite range can be one-way (exercise). $\endgroup$ – Yuval Filmus Oct 23 '17 at 13:46
  • $\begingroup$ I wrote: "any length" $\endgroup$ – AdC Oct 23 '17 at 14:03
  • $\begingroup$ You haven't really explained what your function is - what is the input and what is the output. Please edit your question to include this information. $\endgroup$ – Yuval Filmus Oct 23 '17 at 14:09
  • $\begingroup$ Ok Thank you. I now included the continuum range. $\endgroup$ – AdC Oct 23 '17 at 14:25

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.