1
$\begingroup$

Objective: We want to generate a unique and reproducible identifier for a given slice of bytes and avoid collisions.

High-level idea: Compute $$fK := hash(k_1)\; and\; sK := hash(k_1^{-1})\; where\; k_i^{-1}\; is\; the\; reversed\; bitstring\; k_i$$

We then proceed to set, our identifier to be: $$<value\_of\_fK>\_<value\_of\_sK>$$

Assumption:

For two keys $$k_1\; and\; k_2,\; if\; hash(k_1) = hash(k_2)\; and\; hash(k_1^{-1}) = hashs(k_2^{-1})\; then\; k_1 = k_2$$

where our hash function is FNV1a.

Hypothesis: For any given input bitstring, we will have a unique identifier and no collisions.

I would like to have your input on this

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ What is your question? This platform does not serve well as discussion board; you'd be better served by getting people in front of a whiteboard. $\endgroup$
    – Raphael
    Commented Nov 8, 2016 at 0:02
  • $\begingroup$ What is your question? Is “For any given input bitstring, we will have a unique identifier and no collisions” a conjecture that you would like us to prove or disprove? $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Nov 8, 2016 at 12:00
  • $\begingroup$ It's a conjecture that I have clearly labeled as such, when I ask about input this is a, perhaps convoluted, way to ask whether this sounds like a reasonable assertion or not $\endgroup$
    – Erwan Aaron
    Commented Nov 8, 2016 at 14:36

1 Answer 1

Reset to default
2
$\begingroup$

Your assumption is probably false. It can only be true if the size of the hash is at least half the size of the key.

If you want to generate an absolutely unique identifier, why not use the key itself? Another option, if you want an alphanumeric identifier, is to use Base64 (which also uses a few punctuation marks).

If you just want a practically unique identifier, you can just use a hash function – any industry-standard one would do. That's exactly their goal. Since it doesn't seem you care about cryptographic security, you can just use MD5 or SHA1.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the quick reply! I would like to bind values to keys without having to store the key itself (there are no upper bounds on the size of a key or value). Therefore I need to find a way to create a unique signature for any given key to which I can match a value. The size constraint hence rules out storing the whole key as an identifier. $\endgroup$
    – Erwan Aaron
    Commented Nov 7, 2016 at 20:52
  • $\begingroup$ If the keys have unbounded length but the signature has bounded length then you cannot avoid collisions. However, you can make them very unlikely. If you expect to have $2^n$ keys, then your signature needs to be somewhat larger than $2n$ bits. $\endgroup$
    – Yuval Filmus
    Commented Nov 7, 2016 at 20:53
  • $\begingroup$ Got it. Thanks, this perfectly answer the question! $\endgroup$
    – Erwan Aaron
    Commented Nov 8, 2016 at 5:14

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.