One-way function: Difference between revisions

Revision as of 21:44, 26 March 2024

Revision as of 09:25, 9 April 2024

Line 70:

==Universal one-way function==

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

| author = Leonid Levin

| author-link = Leonid Levin

| title = The Tale of One-Way Functions

| publisher = ACM

| year = 2003

| arxiv = cs.CR/0012023

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

==See also==