# 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. – Squeamish Ossifrage 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) – user2505282 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)$ – Mikero Apr 3 '19 at 3:22
• Oops; I messed it up. Thanks – user2505282 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. – Future Security 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. – AleksanderRas 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. – kodlu 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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 4, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.5885385274887085, "perplexity": 881.9190375944478}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-05/segments/1579251671078.88/warc/CC-MAIN-20200125071430-20200125100430-00549.warc.gz"}