0
$\begingroup$

This PDF supposedly gives a construction of a universal one-way function, i.e. a function which is one-way as long as there exists a one-way function:

Recall that there are only countably many Turing machines (for any fixed alphabet). Let $M_1,M_2,M_3,\dots$ be a list of all the Turing machines such that the length of the description of $M_n$ is bounded by some polynomial in $n$. Now, let

$$f_\text{univ}(x) = M^{(|x|^2)}_1(x)||M^{(|x|^2)}_2(x)|| \cdots||M^{(|x|^2)}_{|x|}(x)$$

where $M^{(|x|^2)}_{i}(x)$ denotes the output of $M_i$ on input $x$ right after $|x|^2$ steps of computation. One can verify that $f_\text{univ}$ can be computed in polynomial time. Now, suppose there exists a one-way function $f$. Then, there exists a Turing machine in our list, say $M_K$, that computes $f$. We note that for $x \in \left\{0,1\right\}^∗$ such that $|x| \geq K$, $f_\text{univ}(x)$ contains $M_K(x) = f(x)$. One can finish the proof using standard reduction techniques.

My question is, is this really a one-way function? What if, say, $M_1$ was the identity function? Then given $f_\text{univ}(x)$, wouldn’t it be trivial to get $x$, by taking the first however many bits of the output?

$\endgroup$
4
  • $\begingroup$ One difficulty in the proof is with "Let $M_1,M_2,M_3,\dots$ be a list of all the Turing machines such that the length of the description of $M_n$ is bounded by some polynomial in $n$". In this, "such" can't apply to "Turing machines" (the condition for belonging to the list would depend on the list). Therefore, "such" applies to "list". And then there's the issue of the existence of such a list that we posit in the rest of the proof. This is where "there are only countably many Turing machines" seems to be needed. I'm not sure... $\endgroup$
    – fgrieu
    Oct 30, 2020 at 20:41
  • 1
    $\begingroup$ I would say that you're indeed right, the construction is incorrect. It's invertible if any of the functions are invertible. The input needs to be split in independent inputs for the individual Turing machines. $\endgroup$
    – Maeher
    Oct 30, 2020 at 20:44
  • 1
    $\begingroup$ @fgrieu Apart from that part (i.e. if we assume that such a complete list of Turing machines of bounded length exists), do you think that the rest of the proof is valid? If so can you post an answer proving that it’s valid? Also, is it your position that only $M_1$ cannot be the identity function? What if $K = 1$ and $M_2$ is the identity function? Isn’t that equally problematic? $\endgroup$ Oct 30, 2020 at 20:44
  • $\begingroup$ I now lean towards @Maher and incorrectness of the proof: if any of the $M_i$ in the list other than $M_K$ is the identity function, or otherwise invertible, then knowing $f_\text{univ}(x)$ as defined in the reference we can find $x$. Maher's fix to the proof seems to work, even though it makes $|x|$ polynomial in $n$. Also correcting a lesser typo in the index of the right $M_{|x|}$, we'd want$$f_\text{univ}(x_1\mathbin\|x_2\mathbin\|⋯\mathbin\|x_n)=M^{(|x_1|^2)}_1(x_1)\mathbin\|M^{(|x_2|^2)}_2(x_2)\mathbin\|⋯||M^{(|x_n|^2)}_n(x_n)$$but I'm too far of my comfort zone to make this an answer. $\endgroup$
    – fgrieu
    Oct 30, 2020 at 22:22

0

Your Answer

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

Browse other questions tagged or ask your own question.