The one-way function is one of the most fundamental concept in cryptography. It is the basis of the construction of other crypographic algorithms.

Informally, if $f$ is a one-way function, then it’s easy to compute $f(x)$ from $x$, but it’s hard to guess $x$ from $f(x)$.

### Formal Definition

The formal definition is that:

**\(f:D\to R\) is a one-way function (OWF) if, for any probabilistic polynomial time (PPT) adversary \(A\), and for any \(x\) uniformly randomly sampled from \(D\), the probability that \(f(A(y))=y\) is negligible, where \(y=f(x)\).**

The definition can be written in the math language as: For all PPT \(A\), \[Pr[x\xleftarrow{$}D, y=f(x), x’=A(y): f(x’)=f(x)] \le negl(n)\]

The **adversary** is an algorithm that aims at inverting the one-way function. It can be **probabilistic** (i.e. not deterministic). But the running time must be bound to polynomial time. We demand the one-way function not to be secure against *some* adversaries, but *all* adversaries.