# 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 Aug 2 '14 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"? $\;\;\;\;$ –  Ricky Demer Jul 31 '14 at 21:37
By exists it means that there may be no one way functions they may not exists. –  lPlant Jul 31 '14 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. Jul 31 '14 at 21:57