In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, a one-way function is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-orie ...
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-dimensio ...
of a random input. Here, "easy" and "hard" are to be understood in the sense of
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, 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 is not considered sufficient for a function to be called one-way (see
Theoretical definition
A theoretical definition defines a term in an academic discipline, functioning as a proposal to see a phenomenon in a certain way. A theoretical definition is a proposed way of thinking about potentially related events. Theoretical definitions cont ...
, 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 1 ...
. Their existence would prove that the
complexity classes
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
P and NP are not equal, thus resolving the foremost unsolved question of theoretical computer science.
Oded Goldreich
Oded Goldreich ( he, עודד גולדרייך; b. 1957) is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. His research interests lie within the theory of computation ...
(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
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
,
personal identification
An identity document (also called ID or colloquially as papers) is any documentation, document that may be used to prove a person's identity. If issued in a small, standard credit card size form, it is usually called an identity card (IC, ID c ...
,
authentication
Authentication (from ''authentikos'', "real, genuine", from αὐθέντης ''authentes'', "author") is the act of proving an assertion, such as the identity of a computer system user. In contrast with identification, the act of indicat ...
, and other
data security
Data security means protecting digital data, such as those in a database, from destructive forces and from the unwanted actions of unauthorized users, such as a cyberattack or a data breach.
Technologies
Disk encryption
Disk encryption re ...
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
Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than tha ...
s,
e-commerce
E-commerce (electronic commerce) is the activity of electronically buying or selling of products on online services or over the Internet. E-commerce draws on technologies such as mobile commerce, electronic funds transfer, supply chain mana ...
, and
e-banking
Online banking, also known as internet banking, web banking or home banking, is an electronic payment system that enables customers of a bank or other financial institution to conduct a range of financial transactions through the financial insti ...
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 performa ...
that attempts to compute a pseudo-inverse for ''f'' succeeds with