# One Way Function

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.

Why must the computation power of the adversary be bound to **polynomial time**?

If the advesary has unbound computation power, then it can easily invert any one-way function by enumerating all the values in the domain and testing if the result is the same as the given \(y\).

**Negligible** means that the success probability must be asymptotically smaller than \(\frac{1}{p(n)}\) where \(p\) is any polynomial function and \(n\) is the *security parameter*. Another way to say it is that the reciprocal must grow faster than any polynomial function.

The **security parameter** determines how secure the algorithm is. For example, if the domain is \({\{0,1\}}^n\), then the security parameter is \(n\). The larger \(n\) is, the harder inverting \(f\) is.

Here are some negligible functions: \(\frac{1}{2^n}\), \(\frac{1}{1.0001^n}\).

From the definition of one-way function, we know that **for any PPT adversary, we can always make it almost impossible to invert the one-way function by increasing $n$ to a large enough number**.

The condition that decides if the adversary succeeds is $f(A(y))=y$, which means the adversary succeeds as long as it finds a pre-image $x’$ such that $f(x’)=f(x)$. The pre-image $x’$ can be different from the original $x$.

The reason why we don’t demand $A$ to find the exact $x$ is because we want to rule out those trivially “one-way” functions such as $f(x)=0$. They are “perfectly one-way” but not useful.

### Information Leaking

The definition of one-way function says **nothing about information leaking**. In fact, we can construct a one-way function that leaks half of the pre-image yet still secure.

Here is an information-leaking OWF:

**Given some secure one-way function $f$, we can construct $g(x)=(f(x_1),x_2)$ where $x_1$ is the first half of $x$ and $x_2$ the second half.**

It always leaks the second half, but it is secure by definition.

### 1-1 One-way Function

If the one-way function is *injective* (if $f(x_1)=f(x_2)$, then $x_1=x_2$), then we say it is an injective one-way function, or more commonly, **1-1 one-way function**.

We can construct 1-1 one-way functions from a known one-way function by appending more information to the image.

Assuming we want to construct 1-1 OWF $g$ from a known OWF $f$, the construction usually looks like $g(x)=(f(x),signal(x))$, where $signal(x)$ is a function that generates a **signal string** from $x$, whose purpose is to ensure there is no other pre-image producing the same image. The signal string usually *leaks some information of x*.

### Construction From Factoring

We can construct a OWF from the *factoring* problem.

The **factoring** problem says, given the product $pq$ of two primes $p$ and $q$, it is hard to compute $p$ and $q$.

So the domain of our OWF is $D=\{(p,q) | p, q \in P\}$ where $P$ is the set of $n$-bit prime numbers. The range is $R=\{pq | p, q \in P\}$.

Let $f(p,q)=pq$.

By the factoring assumption, we know $f$ is indeed one-way.

However, $f$ is not injective, since $f(p,q)=f(q,p)$.

To make it a 1-1 OWF, we let $f(p,q)=(pq,I_{p<q})$ where $I_{p<q}$ is 1 if $p<q$, 0 otherwise.

Observe that $I_{p<q}$ leaks some information about the pre-image (i.e. which one is larger), but the information is insufficient for an adversary to invert the function.

### General Construction Possible?

We can construct one-way functions from *some* assumptions, but can we construct a one-way function from no assumptions? This is still an open question. But it might still remain open for a long time, because we have shown that **if $P=NP$, then there exists no one-way function**. That being said, if we constructed a one-way function from nowhere, we would essentially prove that $P\not=NP$.