# Generate collision resistant identifiers with two-way hashing

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

• 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. – Raphael Nov 8 '16 at 0:02
• 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? – Gilles 'SO- stop being evil' Nov 8 '16 at 12:00
• 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 – Erwan Aaron Nov 8 '16 at 14:36

• 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. – Yuval Filmus Nov 7 '16 at 20:53