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 ?

Improve this question
$\endgroup$
2
  • 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
    Commented Oct 22, 2017 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
    Commented Oct 23, 2017 at 12:43

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
8
  • $\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
    Commented Oct 23, 2017 at 12:42
  • $\begingroup$ It's still not one-way. No function with finite range can be one-way (exercise). $\endgroup$
    – Yuval Filmus
    Commented Oct 23, 2017 at 13:46
  • $\begingroup$ I wrote: "any length" $\endgroup$
    – AdC
    Commented Oct 23, 2017 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
    Commented Oct 23, 2017 at 14:09
  • $\begingroup$ Ok Thank you. I now included the continuum range. $\endgroup$
    – AdC
    Commented Oct 23, 2017 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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