0
$\begingroup$

Please pardon my question if it seems silly, but I am very keen on knowing: in applied cryptography, there is such a thing as a one-way function, which given an input would generate an output that is unique for that input.

Discrete logarithms and factorials are, as far as my knowledge goes, necessary to create one-way functions.

That being said, is there a way to create random one-way functions, so that:

  • each of them would give the same output for the same input
  • and, each of them would be sufficiently unique to the others?

Many thanks

$\endgroup$
1
  • 1
    $\begingroup$ If all the functions agree on all inputs, how can they be unique. Also discrete log is a candidate for the construction of owf, not a necessity. And I have no idea what factorials are supposed to have to do with anything. $\endgroup$
    – Maeher
    Nov 21, 2020 at 19:33

1 Answer 1

1
$\begingroup$

a one-way function, which given an input would generate an output that is unique for that input.

A one-way function does not guarantee uniqueness of outputs.

The definition of a one-way function gives us that given an output $y = f(x)$, is hard to find any preimage $x^*$ of $y$ for which $f(x^*) = y$ holds.

Discrete logarithms and factorials are, as far as my knowledge goes, necessary to create one-way functions.

Factorials? You probably mean the factoring problem? I haven't head of any crypto that uses factorials.

We don't know if these are necessary. Ciphers like AES are one-way, given that the adversary doesn't have access to the key: it's hard to find any plaintext that encrypts to a given ciphertext. However, we don't have a proof that these symmetric primitives are in fact secure.

Additionally, we don't even know if they are sufficient. If P = NP, one-way functions don't exist. Neither DL nor factoring would be computationally hard problems.

That being said, is there a way to create random one-way functions, so that:

each of them would give the same output for the same input
and, each of them would be sufficiently unique to the others?

Is your first requirement, that the function is indeed a function? I.e. that whenever you supply an input $x$ to the function $f$ you will always obtain the same output?

If so, then yes - all one-way functions are functions.

As for your second constraint - you would have to specify some metric for sufficiently unique. In the random oracle model, it is easy to construct such a function:

Given $H(\cdot)$, a function that behaves like a random function, we can construct a function family $H_s(x) = H(s \| x)$ (where $\|$ is concatenation and $s$ a random string $\in \{0,1\}^n$ for some length $n$). Each of these functions $H_s(\cdot)$ will behave as a random function, is different from every other function, and will be hard to invert.

I'm not sure if I've answered your question fully, let me know if I should elaborate on some part or have misunderstood your question!

$\endgroup$
3
  • $\begingroup$ Thank you very much for your answer, @cisnjxqu! Is there an implementation of what I mentioned in the wild? Namely, a construction of Hs(x) family? $\endgroup$
    – jimmytann
    Nov 22, 2020 at 13:22
  • $\begingroup$ Often we assume hash functions such as SHA2-384 to fulfil the requirements of a random oracle. However we don't know if that assumption is sound: some hash functions (e.g. SHA2-256, or SHA2-512) demonstrably don't behave as a random oracle (see length-extension attacks). $\endgroup$
    – ambiso
    Nov 22, 2020 at 14:54
  • $\begingroup$ You could also use pseudorandom functions (PRFs) - instantiations of these may be AES or ChaCha20, for example. $\endgroup$
    – ambiso
    Nov 22, 2020 at 14:55

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.