# How do we know one-way functions can be iterated?

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.

• How is this a cryptographical question? May 15, 2015 at 19:42
• 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). May 16, 2015 at 4:35

We cannot - we may 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.
• 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\}$. May 20, 2015 at 3:16