# Assumptions on one-way functions

What are the assumptions we make to propose a one-way function? I only know of some number theoretic assumptions, but what are the other assumptions you can possibly make, which if true, would imply that $$f$$ is a one-way function?

(Considering pre-image resistant hash functions, what is the assumption there? Hashes as far as I know do not rely on any assumption other than the fact that it seems to be hard)

Edit:

Example: Say we assume factoring a semiprime $$N = pq$$ is hard. Then we can say that the function $$f(p,q) = p*q$$ is one-way. What other assumptions exist?

• Factoring large semiprimes only seems to be hard too. Apr 1 '19 at 15:08
• @SqueamishOssifrage Yes, but that assumption is necessary and sufficient to prove that a one-way function exists. (I'm not sure if there exists such a concrete assumption for hashes) Apr 3 '19 at 1:42
• The example in your edit is backwards. $f(p,q) = p*q$ is one-way, not $f(N) = (p,q)$ Apr 3 '19 at 3:22
• Oops; I messed it up. Thanks Apr 4 '19 at 8:43

### General

The existence of a "perfect" one-way function is not proven. Such a function would prove that P $$\ne$$ NP, which is still an unsolved problem in mathematics / computer science.

One-way functions are per definition hard to invert, but easy to check. One example, that are assumed that they are one-way, are hash-functions:

You can easily create a hash of a given input, but you can't get the input from a given hash in a reasonable amount of time, assuming the input is long enough.

Some properties of a one-way function:

• Easy to compute, but infeasible to compute the inverse of the function in the average case
• Preimage resistant

### Hashes

We assume that there exists a perfect one-way hash function: Hash functions are a special kind of one-way functions, since they reduce a possible large input to a fixed length smaller hash value, the term is a one-way compression function. This means that there is a data-loss and also means that mulitple different inputs can have the same hash value (pigeonhole principle). Data-loss here means, that it's impossible to retrieve the unknown original input from a given hash-value.

• No. Data-loss is irrelevant. $f(x) = x \operatorname{mod} 11$ is an example with a lot of "data-loss" which is not one-way. To qualify as a OWF, there must be no way to efficiently find any input which results in a given output. Apr 1 '19 at 19:42
• @FutureSecurity I know, a perfect one-way hash function would be exactly that, because there wouldn't exist a better method than brute-force. I didn't say that data-loss is a property of one-way functions, I only explained a little bit further how hashes work in general. Apr 2 '19 at 8:33
• @user2505282 your notation is backwards from the standard notation. It is not $f(N)=(p,q)$ that is hard, that's the inverse of the one way function, under the semiprime factoring difficulty assumption. Apr 3 '19 at 6:08

I'd recommend reading Barak's recent survey titled "The Complexity of Public-Key Cryptography". The survey explores the assumptions required for one-way functions and public-key cryptography (loosely speaking, the latter requires more structured assumptions compared to the former). There (in §2) you can find several candidate constructions of one-way functions from diverse problems arising from cryptography (e.g., stream ciphers, hash functions), complexity theory (e.g., the planted SAT and planted Clique problem), combinatorics (e.g., Goldreich's one-way function) and learning theory, and he argues why these are plausibly one-way.