Effective calculation of the nth element in random permutation

Question

Imagine that I managed to shuffle all numbers between 0 and 2 ^ 32, using something like a Knuth shuffle and a sowing random number generator, seeded with a key.

Conceptually, I need two arrays (using Z ₅ instead of Z _{2 ³²} for short):

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

If I had these arrays, I could efficiently look for the nth element in the permutation, and also discover the purmutation v value with the element;

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

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

Ideally, I want to write two pure functions that work as follows:

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

Requirements:

• Each 32-bit value displays a unique 32-bit value.
• Knowldedge of the first 100 elements in the permutation does not contain information about what may be the 101st element in the permutation.

I understand that theoretically there should be at least 2 ³² ! unique keys to represent any possible permutation, but I believe that I can hide this problem in practice behind a good hash function.

Is there anything close to this?

Answer 1

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

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

The only problem is finding a good 32-bit block cipher. The only thing I know is SKIP32 , but I don't know anything about its strength.

The SKIP32 key size is 80 bits. If this is a good cipher, that will be enough.

But then again, I don’t know the code.

If increasing the range to 2 ^ 64 - 1 integers is an option for you, you can simply use the well-known 64-bit block cipher, such as Triple-DES or Blowfish.

Answer 2

"Knowldedge of the first 100 elements in the permutation does not contain information about what could be the 101st element in the permutation."

You need to save the whole array in memory. I suggest using stxxl, which is designed for large data types, saving most of the container to disk. By the very nature of random permutation, you cannot extrapolate the value [n-1] or [n + 1] given [n]. Thus, it does not look like space can be optimized.

Answer 3

From a cryptographic point of view, you need a block cipher with 32-bit blocks.

The problem of encryption (the so-called "permutation of keys") over arbitrary (and often small) domains is what is "Formatting security . "

There is a general “ideal” solution for this particular problem, but the calculation involves sampling through a hypergeometric distribution, which implies a lot of floating point rejection and arbitrary precision numbers, which is expensive.

There are also “approximate” solutions in which the permutation is not, strictly speaking, uniformly chosen among all possible permutations, but the difference can be made arbitrarily small, to such an extent that it is impossible to distinguish between the implemented permutation and the really randomly chosen permutation. See, in particular, Thorp shuffle .

There is no standard and secure 32-bit block encryption, since 32 bits are not enough to provide security in situations where block ciphers are usually used (encryption of long data streams, for example, as part of SSL); 64-bit blocks are already disapproved. So you are a little on your own here.

Answer 4

Hashing doesn’t solve sequences of random numbers.

Store 2 ^ 32 bits. This is .5 GB.

Launch Shiscle Fischer-Yates and cross out the beat as you go forward. If you want to know the contents of the 5th element, you will select 4, and the 5th random value will be your number.

To get the nth permutation, you need to retreat. Run the algorithm n times and get numbers like:

 Find 5th index after 4 permutations: First iteration: 1st : skip (run through the RNG) 2nd : skip 3rd : skip 4th : 7th index to 5th index Second iteration: (run using same seed as 1st iteration) 1st : skip 2nd : skip 3rd : 3rd index to 7th index 4th : 7th index to 5th index Third iteration: 1st : skip 2nd : 4th index to 7th index 3rd : 3rd index to 7th index 4th : 7th index to 5th index Fourth iteration: 1st : 8th index to 4th index 2nd : 4th index to 7th index 3rd : 3rd index to 7th index 4th : 7th index to 5th index 

From the last iteration, you know that the eighth index leads to the 5th index.

EDIT: I wrote a quick program for checking speed. It takes a few minutes per permutation. It is slow but still used.