3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How is this a cryptographical question? $\endgroup$
    – poncho
    May 15, 2015 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, 2015 at 4:35

1 Answer 1

4
$\begingroup$

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.

Almost all higher level cryptographic functions are defined on bits so in that case only the number of bits is of importance. As indicated, the input size is generally not an issue for hash algorithms, but it could be for other functions such as block ciphers or algorithms build upon block ciphers (KDF's).

$\endgroup$
4
  • $\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, 2015 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, 2015 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$ May 19, 2015 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, 2015 at 3:16

Your Answer

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

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