Content deleted Content added
Citation bot (talk | contribs) Altered template type. Add: eprint, volume, authors 1-1. Removed URL that duplicated identifier. Removed access-date with no URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar |
cs.CC |
||
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 |volume=39 |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>{{cite arXiv |last1=Liu |first1=Yanyi |title=On One-way Functions and Kolmogorov Complexity |date=2020-09-24 |eprint=2009.11514 |class=cs.CC |last2=Pass |first2=Rafael}}</ref>
==See also==
| |||