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?

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:

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

-
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.

-
$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.

-
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.

StackExchange Computer Science Q#28844, answer score: 3