One-way function: Difference between revisions

Revision as of 21:14, 26 November 2020

Revision as of 19:05, 19 December 2020

Line 1:

{{shortShort description|Function that is easy to compute on every input, but hard to invert given the image of a random input}}

{{unsolved|computer science|Do one-way functions exist?}}

In [[computer science]], a '''one-way function''' is a [[function (mathematics)|function]] that is easy to compute on every input, but hard to [[Inverse function|invert]] given the [[image (mathematics)|image]] of a random input. Here, "easy" and "hard" are to be understood in the sense of [[computational complexity theory]], specifically the theory of [[polynomial time]] problems. Not being [[One-to-one function|one-to-one]] is not considered sufficient for a function to be called one-way (see [[#Theoretical definition|Theoretical definition]], below).

Line 74:

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

| author = [[Leonid Levin]]

| author-link = Leonid Levin

| title = The Tale of One-Way Functions

| publisher = ACM

Line 92 ⟶ 93:

==Further reading==

* Jonathan Katz and Yehuda Lindell (2007). ''Introduction to Modern Cryptography''. CRC Press. {{isbn|1-58488-551-3}}.

* {{Cite book | author = [[Michael Sipser]] | author-link = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 978-0-534-94728-6 | url-access = registration | url = https://archive.org/details/introductiontoth00sips }} Section 10.6.3: One-way functions, pp.&nbsp;374&ndash;376.

* {{Cite book|author = [[Christos Papadimitriou]]|author-link = Christos Papadimitriou| year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 978-0-201-53082-7}} Section 12.1: One-way functions, pp.&nbsp;279&ndash;298.

{{DEFAULTSORT:One-Way Function}}