Random 1-to-1 hash function

Question

I came upon an interesting problem today, and scoured the internet looking for a solution but didn't find any. The problem is this:

A user creates an account and he is given a unique ID number, say 123, to represent his account. When another user creates an account, I could just add 1 to the most recently created ID number and assign it to him, 124. However, this doesn't completely anonymize everybody as he now knows that user 123 registered before him. A very small problem to have, but in some conceivable situations this could cause much larger problems.

A better solution would be to have IDs random but unique so that nobody can tell who came first.

To solve this problem, one might use a standard hash function or random number generator to create a unique ID for each person, but then you run into the possibility of collisions. This can be avoided by checking for collisions and running again, but let's say for this example that this will slow down the system too much. Or it could be that the generator is running on incomplete information and cannot check to see if there are collisions.

A different idea that I came up with is to basically have a shuffled deck of cards that you store and take one off the top any time you need a new ID. When you run out of cards in the deck, you take a new deck continuing at the highest card in your last deck and shuffle that one. Downsides to this are that you must store this deck of cards and if you somehow accidentally lose the deck, you run into many problems trying to recreate it or continuing on without it.

A very similar solution to this one is to recreate this shuffled deck based off a fixed seed every time, and take the nth card of the deck instead of the top one. The problem that this has is it can be expensive to shuffle this deck every time you need a new card.

Other mathematical models that I have tried to come up with all have the problem of the next number in the sequence being predictable (each number is a fixed amount apart from the previous one). A lot of them have the problem of having collisions as well.

So my question is: Is there some mathematical model I can plug numbers into to get unique IDs that doesn't require the use of a "deck" (read: array) stored in memory or recomputed on every function call.

For example

randomID(number, seed, range)
randomID(1,123,1000) = 284
randomID(2,123,1000) = 739
randomId(3,123,1000) = 088
randomId(3,888,1000) = 912

I have looked up https://code.google.com/p/smhasher/wiki/MurmurHash3 which seems to be promising, but I don't think it applies over an arbitrary range of numbers, and only over 32bits or 64bits.

Answer 1

You can use a block cipher to achieve this. When you encrypt a block (a fixed number of bits), the cypher maps it to a different block with the same number of bits. The decryption step undoes this. No two different blocks are ever mapped to the same block.

So take your user id of let's say 64 bits and encrypt it with a 64 bit block cipher and a secret key, and you have your randomized user id. To get the original user id back, just decrypt with the same key.

If you use a well-known algorithm like Blowfish or AES, the results will be cryptographically as secure as you can get.

Answer 2

You could select a pseudorandom number generator with a period larger than the maximum number of users you would ever need to support, then you just need to seed the PRNG with the last-used value in order to generate the next. If you somehow lose track of the last-used value, you can use the initial seed then generate further values based on the number of already registered users. You'd probably want to avoid PRNG with excessively large values (e.g. perhaps find a 16 bit one 2^16 period if you'll have less than 65536 users), so the numbers are practical to remember.