We have several candidates for OWF, like multiplication/factoring and discrete exponencial/logarithm. What I am asking is:

Does the existence of one way functions imply that our candidate functions are indeed one way functions?

Is there a candidate one way function whose one wayness is directly tied to the existance of OWF?


Yes, you are looking for the notion of a universal one-way function. Rafael Pass/abhi shelat's notes contain a construction on page 49. The construction is "unnatural" in the sense that it involves parsing the input to the OWF $y$ as a pair $\langle M\rangle || x$, where $\langle M\rangle$ is interpreted as the description of a Turing machine. Then you simulate $M(x)$'s executation for a bounded number of steps.

This is fairly typical of "universal" constructions (others exist, namely Levin's universal search). It is far from being feasible in practice though. The notes mention that a "natural" universal OWF construction is a very open problem (circa 2008-ish).

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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