one way function from a set of unique numbers to another set of unique numbers

Question

I am looking for a function (hash function? not sure) that maps a set of (unique) numbers to another set of (unique) numbers. I had a look at perfect hashing -and the fact that it's impossible to do :( - and it seems quite close to what I am after.

In detail, I want the following:

• Map any given 12 digit number to another number, 12 digit or more (I don't care about the resulting size but it must fit in a Java long).
• Must be able to guarantee that the same 12 digit number maps to the same number every time.
• Must be able to guarantee that a different 12 digit number always maps to a different number, i.e. there are no collisions in the result set.
• Must be able to guarantee that the function is one way, which (in my mind anyway) means that you cannot compute the number you started from given the result of the function.

Something like minimal hashing function would not work in my case, as each number has to be computed on a different computer, meaning that the function itself has to guarantee these features without checking for collisions in the results and or having any centralized control of the result set.

An example of such a function would just be a simple: take number, add 1, output number. The only problem with that is that you can easily get first number just by subtracting one. I want it to be very difficult, or preferably impossible to get the previous number back.

Any thoughts ?

Translating the function from math to java I don't mind doing on my own. Unless you can suggest an already existing java library.

Answer 1

You are looking for Format-preserving encription algorithms.

Answer 2

It looks a cryptography problem for me. If you want to map a String to other String and must be able to guarantee that is one way and has no collisions, you need encrypt the input String. For example you can use DES.

If the output must be digits you can interpret the bytes of the output as hexadecimal and then convert to base 10.

Answer 3

What you want is a cipher. A good old fashioned symmetric cipher. Like AES.

Imagine for a second that instead of 12 digits, your numbers were 128 bits long. Let's say you set up an AES cipher with a key of your choosing, and use it to encrypt numbers. What is the outcome?

• You will map any given 128-bit number to another number, of exactly 128 bits (AES's block size is 128 bits)
• You can guarantee that the same 128-bit number maps to the same number every time (encryption is deterministic)
• You can guarantee that two different 128-bit numbers always map to different numbers (encryption is reversible - there are no two plaintexts which encrypt to the same ciphertext, otherwise how could you decrypt them?)
• You can guarantee that, for someone who doesn't have the key, the function is one way (encryption is not reversible without they key - it would be less useful if it was)

Now, 128 bits is bigger than you want, so AES is not the right cipher for you. All you need to do is choose a cipher which has a 12-digit block size.

There aren't any conventional ciphers which have a 12-digit block size. But it's actually pretty easy to construct one. You can use the Feistel construction to take a hash function and construct a block cipher. You can either build a binary cipher of a suitable size (40 bits in your case) and then use the "hasty pudding trick" to restrict its domain to 12 digits, or construct a cipher that works directly in decimal (more or less).

I wrote an answer to another question a while ago that explained this in some more detail; i even wrote some code to implement the idea, although looking at it now, i don't know how comprehensible it is. The key classes in it are TinyCipher, which implements a cipher with a block size of up to 32 bits (and could easily be extended up to 64 bits), and TrickCipher, which uses the hasty pudding trick to implement a cipher over an arbitrary-sized set (such as all 12-digit numbers).