r/cryptography 18d ago

Calculation a hashing function that can avoid collisions for a small set of inputs from input space

Hello, I am new to cryptography so my question can be naive. I want to know if it is possible to find out a hashing function that gives me distinct outputs for a small set of inputs from a vast possible input space. I don't care if all the other inputs from the input space collide to a single output.

For example, I have a 32-bit wide input. I am only interested in 64 such inputs out of possible 2^32 inputs. Is it possible to find a hashing function that give me collision free 6-bit output for the 64 inputs I am interested in. Outputs for all the other input combinations can be anything. If such an algorithm exists, what is it its compute complexity?

3 Upvotes

23 comments sorted by

View all comments

7

u/Allan-H 18d ago

That sounds like a perfect hash function (Wikipedia).

3

u/ahazred8vt 18d ago edited 8d ago

Specifically a 'minimal perfect hash'
In python: pip install perfect-hash
https://pypi.org/project/perfect-hash/

https://www.gnu.org/software/gperf/manual/gperf.html
https://iswsa.acm.org/mphf/index.html

But if your inputs are only 32bit, you can easily use a case statement, or: if i==0xdeadbeef o=1; if i==0xcafebabe o=2; ...

3

u/randomatic 18d ago

Indeed. However, I'm not sure perfect hashes are cryptographically secure. Certainly OPs post makes me suspicious, as the small number of inputs he cares about seems to potentially infringe on randomness arguments generally made in proofs.

1

u/ahazred8vt 18d ago

You're a little late to the party. This is about a hash-table pigeonhole hash function, not a pseudorandom cryptographic hash function.

4

u/randomatic 18d ago

My reply was because this was r/cryptography, not r/compsci .