4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Factoring large semiprimes only seems to be hard too. $\endgroup$
    – Squeamish Ossifrage
    Apr 1, 2019 at 15:08
  • $\begingroup$ @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) $\endgroup$
    – user2505282
    Apr 3, 2019 at 1:42
  • $\begingroup$ The example in your edit is backwards. $f(p,q) = p*q$ is one-way, not $f(N) = (p,q)$ $\endgroup$
    – Mikero
    Apr 3, 2019 at 3:22

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Future Security
    Apr 1, 2019 at 19:42
  • $\begingroup$ @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. $\endgroup$
    – AleksanderCH
    Apr 2, 2019 at 8:33
  • 1
    $\begingroup$ @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. $\endgroup$
    – kodlu
    Apr 3, 2019 at 6:08
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.