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 look 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 my need and give me some hint to find an encryption/hash scheme that suit my needs?

I've found what I seems to be looking for is 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, eg. 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$).