# Universal One-Way Functions

The Berman-Hartmanis conjecture discusses one-way functions (functions with hard to compute inverse functions).

As a step to solving the conjecture, if one-way functions could be reduced to a canonical or universal one-way function from which all one-way functions could be derived, this would be a major plus...

In a similar way, Turing devised a universal machine and Cook NP-completeness.

The question is then, are there universal one-way functions (discussed in the literature)? Can they be defined through NP-completeness?

• note the "conventional wisdom" in the field is that the conjecture is false as pointed out by wikipedia
– vzn
Commented Aug 2, 2014 at 15:52

That is an interesting question since there is no proof that one way functions exist. There is a lecture about this from Cornell's Cryptography course by Rafael Pass which can be found here

To summarize the lecture:

1. If one way functions exist then $P\neq NP$.

2. There exists a function $f_{UNIV}$ such that if there exists any one-way function, then $f_{UNIV}$ is a one-way function. Thus $f_{UNIV}$ can be considered a universal one-way function.

3. $f_{UNIV}$ works by acting on all Turing machines after $n^2$ steps of execution. It is defined as

$$f_{UNIV}=M_1^{(|x|^2)}(x)||M_2^{(|x|^2)}(x)||\dots M_{|x|}^{(|x|^2)}(x)$$

where $M_{i}^{(|x|^2)}(x)$ denotes the output of Turing machine $M_i$ on input $x$ right after $|x|^2$ steps of computation.

4. If a one way function $f$ exists it can be solved by a Turing machine $M$, which will be polynomial solvable by $f_{UNIV}$.

Caution: the construction of $f_{UNIV}$ is in no way practical. This is about asymptotic complexity, not practical security.

• What do you mean by "$\hspace{.04 in}f_{UNIV}$ exists"? $\:$ What do you mean by "solved"? $\;\;\;\;$
– user12859
Commented Jul 31, 2014 at 21:37
• By exists it means that there may be no one way functions they may not exists. Commented Jul 31, 2014 at 21:40
• I've tried to clean up your answer, but I don't understand what you are saying in point 4 at all. Would you like to try rephrasing that? What do you mean when you say "$f$ can be solved by a Turing machine $M$"? If $f$ is one-way, there is no polynomial-time algorithm to invert it. What do you mean by "polynomial solvable by $f_{UNIV}$"?
– D.W.
Commented Jul 31, 2014 at 21:57
• The constructed function is not necessarily one-way, even if $M_k$ is one-way for some $k$. The reason is that all $M_i$ are evaluated on the same input $x$. Hence, if $M_1$ is easy to invert, the whole function is easy to invert. This problem can be fixed by first partioning the input $x$ into $x_1, \ldots, x_{\sqrt{|x|}}$ and then running $M_i$ on input $x_i$. Commented Jul 14, 2018 at 5:29
• Liu and Pass have another universal one-way function with a more natural construction (time-bound Kolmogorov Complexity) arxiv.org/abs/2009.11514 Commented Apr 25, 2022 at 9:14