One-way function: Difference between revisions

Revision as of 17:36, 18 September 2024

Revision as of 18:13, 18 September 2024

Line 72:

There is an explicit function ''f'' that has been proved to be one-way, if and only if one-way functions exist.<ref name="HCPred">{{Cite journal |first=Leonid A. |last=Levin |author-link=Leonid Levin |title=The Tale of One-Way Functions |journal=Problems of Information Transmission |issue=39 |date=January 2003 |pages=92–103 |arxiv=cs.CR/0012023 |doi=10.1023/A:1023634616182}}</ref> In other words, if any function is one-way, then so is ''f''. Since this function was the first combinatorial complete one-way function to be demonstrated, it is known as the "universal one-way function". The problem of finding a one-way function is thus reduced to proving{{emdash}}perhaps non-constructively{{emdash}}that one such function exists.

There also exists a function that is one-way if polynomial-time bounded [[Kolmogorov complexity]] is mildly hard on average. Since the existence of one-way functions implies that polynomial-time bounded [[Kolmogorov complexity]] is mildly hard on average, the function is a universal one-way function.<ref>{{Citation |last=Liu |first=Yanyi |title=On One-way Functions and Kolmogorov Complexity |date=2020-09-24 |url=https://arxiv.org/abs/2009.11514 |access-date=2024-09-18 |doi=10.48550/arXiv.2009.11514 |last2=Pass |first2=Rafael}}</ref> Since the existence of one-way functions implies that polynomial-time bounded [[Kolmogorov complexity]] is mildly hard on average, the function is a universal one-way function.

==See also==