Efficient calculation of nth item in a random permutation

Question

Imagine I was able to shuffle all numbers between 0 and 2^32 using something like the Knuth shuffle and a seeded random number generator seeded with a key.

Conceptually, I would need two arrays (using Z₅ instead of Z_2³² for brevity):

[2, 0, 1, 4, 3] // perm
[1, 2, 0, 4, 3] // inv === p^-1

If I had these arrays, I could efficiently look up the nth element in the permutation as well as find out with element in the purmutation value v;

v = perm[n];
n == inv[v]; // true

I don't want to store two 16 GB arrays of uint representing this shuffled set because I am never interested in the entire shuffled sequence at any time. I am only ever interested in the value of the nth element.

I ideally want to write two pure functions that work like this:

uint nthShuffled = permutate<uint>(key, n); // O(log n)
uint n == invert<uint>(key, nthShuffled); // O(log n)

Requirements:

• Every 32 bit value maps to a unique different 32 bit value.
• Knowldedge of the first 100 elements in the permutation provides no information on what might be the 101st element in the permutation.

I understand that in theory there must be at least 2³²! unique keys in order to represent any possible permutation, but I believe I can hide that problem in practice behind a good hashing function.

Is there anything out there that comes close to this?

Answer 1

Any block cipher is actually a pseudo-random permutation. A 32-bit block cipher permutates the integers between 0 and 2 ^ 32 - 1.

Given a secret key, encrypting N with this key gives the N-th pseudo-random number.

The only problem would be finding a good 32-bit block cipher. The only one I know is SKIP32, but I do not know anything about its strength.

SKIP32's key size is 80 bits. If it is a good cipher, that would be enough.

But again, I do not know the cipher.

If increasing the range to 2 ^ 64 - 1 integers is an option for you, you could simpply use a well-known 64-bit block cipher like Triple-DES or Blowfish.