In
computer science, a one-way function is a
function that is easy to compute on every input, but hard to
invert given the
image
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
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
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
problems. Not being
one-to-one
One-to-one or one to one may refer to:
Mathematics and communication
*One-to-one function, also called an injective function
*One-to-one correspondence, also called a bijective function
*One-to-one (communication), the act of an individual comm ...
is not considered sufficient for a function to be called one-way (see
Theoretical definition, below).
The existence of such one-way functions is still an open
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 19 ...
. Their existence would prove that the
complexity classes P and NP are not equal, thus resolving the foremost unsolved question of theoretical computer science.
[ Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools,]
draft available
from author's site). Cambridge University Press. . (see als
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.
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
malicious agents". 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
telecommunications,
e-commerce, and
e-banking systems around the world.
Theoretical definition
A function ''f'' :
* →
* is one-way if ''f'' can be computed by a polynomial time algorithm, but any polynomial time
randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
that attempts to compute a pseudo-inverse for ''f'' succeeds with