Suppose we have some one-way function $h$. Without further specification of $h$, how can we be sure that we can define another function $g(n) = h(h(n))$?

That is, how do we know the range of $h$ is a subset of the domain of $h$?

Relevance to Cryptography: One-way functions are minimal assumptions for the constructing pseudorandom generators. Thus, one-way functions are fundamental to theoretical cryptography (perhaps not for applied cryptography)....but cryptography all the same.

  • $\begingroup$ How is this a cryptographical question? $\endgroup$ – poncho May 15 '15 at 19:42
  • 1
    $\begingroup$ One part of the definition of one-way functions as I know it is that the domain of a one-way function is the set of all finite strings (or, at least, the set of all finite strings with length in an infinite and efficiently computable subset of N, in which case the function can efficiently be transformed in a one-way function defined on all finite strings). $\endgroup$ – fkraiem May 16 '15 at 4:35

We cannot - we might need another function to adjust the value to be acceptable. Assuming however that $h$ is a hash - this is the crypto site - then it should accept any size of input in bits; up to a seriously high limit anyway.

| improve this answer | |
  • $\begingroup$ You would of course need an encoding function in that case. For generic libraries the ASN.1 DER format is relatively popular. Generally it is possible to map non-infinite parameters to a (canonical) bit string. $\endgroup$ – Maarten Bodewes May 16 '15 at 0:44
  • $\begingroup$ @James "From a purely theoretical perspective", a function's input and output are binary strings, not integers or "decimals" (whatever you mean by that). $\endgroup$ – fkraiem May 16 '15 at 5:55
  • 1
    $\begingroup$ @fkraiem in a general mathematical point of view, both "input" and "output" of a function can elements of some arbitrary sets. Nothing stringy here. The set of (finite) bit-strings and its subsets are important examples, but not really exclusive ones. $\endgroup$ – Paŭlo Ebermann May 19 '15 at 20:42
  • $\begingroup$ Well, the "theory" we are dealing here is complexity theory, not general mathematics. And unless you use some exotic model of computation, your functions must be defined on strings over some alphabet, which without loss of generality can be $\{0,1\}$. $\endgroup$ – fkraiem May 20 '15 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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