One-way function: Difference between revisions

Revision as of 08:17, 30 October 2022

Revision as of 03:35, 20 December 2022

Line 1:

{{Short description|Function used in computer cryptography}}

{{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).

The existence of such one-way functions is still an open [[conjecture]]. Their existence would prove that the [[complexity classes]] [[P = NP problem|P and NP are not equal]], thus resolving the foremost unsolved question of theoretical computer science.<ref name=Goldreich>[[Oded Goldreich]] (2001). Foundations of Cryptography: Volume 1, Basic Tools, ([http://www.wisdom.weizmann.ac.il/~oded/PSBookFrag/part2N.ps draft available] from author's site). Cambridge University Press. {{isbn|0-521-79172-3}}. (see also [http://www.wisdom.weizmann.ac.il/~oded/foc-book.html wisdom.weizmann.ac.il])</ref>{{rp|ex. 2.2, page 70}} The converse is not known to be true, i.e. the existence of a proof that P≠NP would not directly imply the existence of one-way functions.<ref>[[Shafi Goldwasser|Goldwasser, S.]] and Bellare, M. [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"]. Summer course on cryptography, MIT, 1996–2001</ref>

In applied contexts, the terms "easy" and "hard" are usually interpreted relative to some specific computing entity; typically "cheap enough for the legitimate users" and "prohibitively expensive for any [[Black hat hacking|malicious agent]]s". One-way functions, in this sense, are fundamental tools for [[cryptography]], [[personal identification]], [[authentication]], and other [[data security]] applications. While the existence of one-way functions in this sense is also an open conjecture, there are several candidates that have withstood decades of intense scrutiny. Some of them are essential ingredients of most [[telecommunication]]s, [[e-commerce]], and [[Online banking|e-banking]] systems around the world.where is my crypto currency since 2018.[[pi cryptocurrancy]] [[original owner]] Ambassador 2018/11/11. [[Network node's and wallet]]copies of history.My.Emails ((kellyconner1012003yahoo.com))last seen with Robert L Conner [phone] in year2020/06/06 .Taken from linked computers

==Theoretical definition==