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

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$$.

• I realise this is almost certainly unhelpful but $F(K,M,I)=I$ works fine. Could you clarify your question to explain what criteria you have that invalidates this solution? Nov 21, 2013 at 12:16
• If the reverse is not needed this is like a one way function like a hash function and not an encryption function. Nov 21, 2013 at 12:39
• @curious I don't need a reverse, but if I found an encryption function that fullfil my needs, I will use it. Nov 21, 2013 at 12:46
• @user8911 The output should be considered as random in the range. While $F(K,M,I) = I$ for some few $I$ values could be legal, it must be avoided Nov 21, 2013 at 12:48
• @user8911 I want to randomize entries in array, eg. entry order must look random from an eavesdropper. Nov 21, 2013 at 12:50

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$).

• The cycle-walking cipher from FPE paper by Black and Rogaway is indeed easy to understand ... but even if it's bounded, it's not a $O(1)$ operation. I will have a look to the Swap-or-not cipher. Thanks Nov 21, 2013 at 14:12