Hashing/encrypting an integer to produce an unique integer in the same range

Question

I'm looking for a function or set of functions that can produce a pseudo-random permutation on an input set of arbitrary size.

Given a set of $M$ values in range $0..M-1$, where $M$ is positive integer, I need a function $I' = F(K,M,I)$, where $I$ is a value in range $0..M-1$, $K$ a key (to be determined) and $I'$ a value in range $0..M-1$. For each value $I$, there must be only one $I'$ value, and for each $I'$ value, only one $I$ value.

Having the reverse function $I = F'(K,M,I')$ is not strictly needed, but it seems implied by requirement.

So this looks like an encryption function.

If $M$ was $2^{128}$ or $2^{256}$, I could use a block cipher. If $M$ was a multiple of $256$, I could use a stream cipher (byte oriented). But $M$ could be any value, without any special properties: it's not required to be odd, even, prime, power of two,...

I'm not aware of such encryption or hash function. Could you help me to formalize what I need and give me some hints to find an encryption/hash scheme that suits my needs?

I seem to have found what I was looking for: Format Preserving Encryption (FPE), but I need some help to sort this out.

EDIT: In order to be strong, I think it's important the function should not be self-inverse, e.g., given $I' = F(K,M,I)$, $F(K,M,I')$ should not return $I$.

Answer 1

You indeed need Format-Preserving Encryption. It is a pretty easy concept, and this paper by Black and Rogaway should be readable for non-specialists. The simplest method you should be satisfied with is to use a cycle-walking cipher. Suppose :

• Take $I'\leftarrow E_K(I)$;
• Repeat until $I'\in [0\ldots M-1]$,

where $E_K$ is a conventional cipher with key $K$. However, the block size $n$ of $E$ should only slightly exceed $\log M$, otherwise the procedure would take too long.

If a cipher with such block length is not available, the following construction, known as Swap-or-not cipher, should help:

$E_K(X):$

for $i\leftarrow 1$ to $8 \log M$

• $K_i \leftarrow AES_K(i) \pmod{M}$;
• $X' \leftarrow K_i-X \pmod{M}$;
• $X'' \leftarrow \max(X,X')$;
• if ($F_i(K,X'')=1$) then $X \leftarrow X'$.

Here $F_i$ is some key-dependent predicate of $X''$. It must have algebraic degree or higher. For instance, it can be a polynomial of degree 2 over $F_2$, whose coefficients are encryptions of some constants by AES on the key $K$ (similarly to $K_i$).