What does it mean for something to be a one way function?

Question

According to wikipedia: "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 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."

What does "easy" and "hard" mean? Also, please explain why this isn't one way: $f(x) = x^x$. Thanks in advance.

Answer 1

The product of two integers is the best-known candidate for one-way function. It's fast to compute the product of two integers. However, it is not known whether integer factorization can be solved in polynomial time (even though primality testing is in P).

In complexity theory it is common to call easy those computations that can be carried out in time that is bounded by a polynomial in the size of the input by a deterministic algorithm. Here, the size of the of the input is the sum of the number of digits of the two numbers to multiply or the number of digits of the number to be factored.

In practice, an algorithm whose runtime grows with the cube of the size of the imput may already be impractical, whereas an algorithm whose worst-case run time is exponential in the size of the input may find extensive application.

In discussing one-way functions, however, one usually sticks to the simple criterion that identifies easy with polynomial-time. There is one additional detail, though: computing the input from the output of a one-way function should be hard on average---not just in the worst case.

If we knew a polynomial-time algorithm that returns the factorization of an integer with some constant positive probability, then we would rule out integer multiplication as one-way function.

Another well-known possibly-one-way function is modular exponentiation, whose inverse, the discrete logarithm, computes $x$ such that $b^x \equiv y \pmod n$, given $y$.

The fact that $x^x$, as a function from $\mathbb{Z}^+$ to $\mathbb{Z}^+$, is monotonically increasing makes finding $x$ from $x^x$ relatively easy.

Answer 2

"Easy", roughly speaking, means a computer can do it efficiently, and "hard" means a computer can't do it efficiently. Usually the threshold for "efficiently" is that the problem is solvable in polynomial time; i.e. there exists some algorithm that, given an input of size $n$, solves the problem in $O(n^p)$ steps for some $p$. (Essentially, that means for all $n$, the algorithm takes up to $kn^p$ steps for some $k$.)

For instance, as Fabio explained, we think integer multiplication is a one-way function. It's easy to multiply two numbers (the grade-school algorithm is $O(n^2)$ for an $n$-digit number), but hard to find the factors of an arbitrary integer.

Edit: As @KCd points out, we actually don't know if multiplication is a one-way function. It could be, and we don't know an easy way to reverse it, but we haven't proved that one doesn't exist. In fact, we haven't proved that one-way functions exist at all. We just have things that we think are one-way functions, and so we use them as such. It might seem scary that all of cryptography rests on such a shaky mathematical foundation, but it's the best we have at this point.

As Fabio points out, $f : \mathbb{Z}^+ \to \mathbb{Z}^+, x \mapsto x^x$ is easy enough to invert because it is monotonically increasing; binary search could be an approach, for instance, plus some initial computations to set an upper bound for the search. However, taken as a function of the real numbers, $f$ actually doesn't have an inverse, since $1/4^{1/4}$ = $1/2^{1/2}$.

Answer 3

Also, please explain why this isn't one way: $f(x) = x^x$. Thanks in advance.

The definition of a one-way function is that is easy to perform on every input but hard to invert knowing only the calculations on inputs (images). In your case the calculation on every input becomes impractical when $x$ grows. Or is it easy to calculate $10000^{10000}$ in few steps and in a decent amount of time? Also from a point of memory storage when $x=10000$ the amount of memory needed to save that value is $\log_2(10000)\cdot 10000=132877$ bits and that number will have $40000$ digits ($\log_{10}(10000)\cdot10000$). In this case I consider $10000$ as a small value.

I mainly use Mathematics for Cryptography research purposes so I can tell you some examples of one way functions that are "easy" of perform on inputs but hard to "guess" what is "behind" of those.

It is easy to perform modular exponentiation:

$c \equiv a^x \pmod b$ but if an observer only knows $(a,b,c)$ then it has to guess $x$ by solving $x^{th}$ roots by $a^x = bk +c$ which is impractical when ($c,x$) are chosen to be large. This is known as the discrete logarithm problem. Though there are other techniques to solve this kind of problem (index calculation).

Other problem as been said is the integer factorization:

given $n=p.q$ where $(p,q)$ are primes and $1\equiv ed \pmod{(p-1)(q-1)}$ where $e=65537$. The observer only knows $(e,n)$ and he wants to guess $d$. Then he needs to factorize $n$ into prime factors for "guessing" the private key $d$ in order to solve the underlying problem.

There are a lot of more problems like in lattice theory (closest vector problem, short vector problem), in non-commutative groups (conjugate search) etc.