Transform any string into the shortest coherent/unique numeric identifiant

Question

Is there some algorithm that can transform any string input (of any length) into a shortest possible coherent/unique numeric identifiant.

By "coherent", I mean that the same input will always give the same output consistently. Similar to a hash function.

By "unique", I mean that the generated value will not be generated for a different input, in other terms : there is no collision in the output domain.

By "shortest", I mean that the output length should be proportional to the input length, and with a minimal factor. Let's say, one answer produce a length that is, on average 5 times the length of the input, and another answer produce a length that is 3 times the length of the input => I will pick the second one.

The output should only contains digits and can be any length (shortest possible).

A cryptographic hash (like sha256) will respond to the problem, but maybe not in the most satisfaying manner, because of the produced length.

Answer 1

Use any cryptographic (collision-resistant) hash function, such as SHA2. Compute the hash of the string input and use that as your identifier. If needed, treat the identifier as a number in binary, then convert it to decimal and use the resulting digits as your output.

Because the hash function is a deterministic function, it will be coherent. Because cryptographic hash functions are collision-resistant, the identifier will in practice be unique (there will be no collisions*).

It is not reasonable to expect a solution with a significantly shorter output. A hash function with a significantly shorter output is unlikely to be collision-resistant, due to the birthday paradox.

If you allow variable-length outputs, here is another variation on the above: if the input is shorter than 256 bits, then use the input as the identifier (convert to decimal as needed). If the input is 256 bits or longer, compute its SHA2 hash, prepend a single 1 bit, and use that as the identifier (again, convert to decimal if needed). You can change 256 bits to a smaller value, like 160 bits (truncate the SHA2 hash to 160 bits). But you can't make it too much smaller: if you make it too much smaller, it will be possible to find collisions.

---

Footnote [*]: Strictly speaking, this isn't 100% right. Collision-resistant implies that you are unlikely to encounter collisions in your life, because they are hard/infeasible to find. It does not imply that collisions are impossible or that collisions don't exist. From an engineering perspective, as long as the hash length is long enough, you can basically ignore the possibility of collisions and you'll be fine.

Answer 2

For completeness, I will answer my own question to share the solution I end up with.

The idea is first to use cSHAKE256, because :

• it has high collision resistance = 2^(N/2)
• it can produce a variable output length, actually you choose whatever length

Then to convert the output in a different base number, where you can choose the digits.

So there is a compromise to find between :

• the probability of collision
• the complexity of the ID generated
• the length of the ID generated

By setting different values for N (hash output length) and the chosen domain output, the user can reduce the probability of collision and the maximum length to an acceptable level.

Here is live example you can try here !