Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
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? –  figlesquidge Nov 21 '13 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. –  curious Nov 21 '13 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. –  ydroneaud Nov 21 '13 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 –  ydroneaud Nov 21 '13 at 12:48
    
@user8911 I want to randomize entries in array, eg. entry order must look random from an eavesdropper. –  ydroneaud Nov 21 '13 at 12:50
show 4 more comments

1 Answer

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

share|improve this answer
    
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 –  ydroneaud Nov 21 '13 at 14:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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