0
$\begingroup$

Is a perfect hash function always bijective ? In Wiki "In mathematical terms, it is a total injective function" but it does not mean, that it is bijective.

$\endgroup$
2
  • $\begingroup$ If the input domain is larger than the output, how could it be bijective? $\endgroup$
    – mikeazo
    Commented Oct 4, 2015 at 23:38
  • 2
    $\begingroup$ Please note, that what you refer as a perfect hash is not a perfect hash in a cryptographic sense. A perfect cryptographic hash is random oracle and that is almost never injective. The Wikipedia article refers to hashing for non cryptographic purposes, e.g. database lookup. And that is a complete different story. $\endgroup$
    – user27950
    Commented Oct 5, 2015 at 7:48

3 Answers 3

2
$\begingroup$

No, it is not always bijective.

A perfect hash guarantees that no two inputs (from the set of valid inputs) collides, so it is clearly a 1 to 1 mapping. However, in the case where the output range contains more possible values than there were valid inputs, there will be outputs which do not map back to inputs. hence it is not bijective.

If you restrain the problem dramatically, and define the range of the outputs to be "the set of outputs attained from valid inputs," then you could argue it is bijective because you have constrained the output sufficiently to make such a claim. However, it would be up to you to explain why this very particular output range is a valid one for whatever topic is being discussed at that time.

$\endgroup$
1
$\begingroup$

The injective hash function wikipedia referes to is not a secure hash function for cryptographic purposes. It is a hash function used for fast database access.
An ideal secure hash function is a random oracle and a random oracle is not injective with very high probability.

$\endgroup$
1
  • $\begingroup$ It sounds like you're referring to an ECB-mode encryption of data for quick lookups, but this still has all the pitfalls of ECB (identical plaintext maps to the same ciphertext). Using a simple cryptographically-secure keyed hash of data for this would likely be more secure: security.stackexchange.com/a/239565/25009 $\endgroup$
    – ManRow
    Commented Apr 13, 2023 at 21:59
0
$\begingroup$

Depends on how you define the function. A perfect hash function is a bijection from an input set onto a set of integers. However, that set of integers is not necessarily a continuous range, unless you have a minimal perfect hash function.

So if you define the function as mapping a particular set to e.g. $\mathbb{N}$ or $[1, n]$ where $n$ is larger than the size of the set, it is not a bijection.

$\endgroup$

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.