2
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$ Nov 21, 2013 at 12:16
  • $\begingroup$ If the reverse is not needed this is like a one way function like a hash function and not an encryption function. $\endgroup$
    – curious
    Nov 21, 2013 at 12:39
  • $\begingroup$ @curious I don't need a reverse, but if I found an encryption function that fullfil my needs, I will use it. $\endgroup$ Nov 21, 2013 at 12:46
  • $\begingroup$ @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 $\endgroup$ Nov 21, 2013 at 12:48
  • $\begingroup$ @user8911 I want to randomize entries in array, eg. entry order must look random from an eavesdropper. $\endgroup$ Nov 21, 2013 at 12:50

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ Nov 21, 2013 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.