Re: Constructing a random permutation on the fly

On 2009-06-09, Paul Rubin <http> wrote:
Tom Anderson <twic@xxxxxxxxxxxxxxx> writes:
I have a list of N items, where N is about 100 000, and a few thousand
or more users. I would like to present each user with all the items in
a random order, where the order is different for each user.

Short answer: look up "Hasty Pudding cipher".

Longer answer: let b = smallest even number so that 2**b >= N-1. Then
for k < N, represent k as a b-bit number. Chop that into two b/2-bit
halves. Use a generic Feistel cipher to encrypt the pair of
half-numbers with a user-specific key. Use a bunch of rounds to
ensure uniformity. Use the Hasty Pudding trick (look it up) to ensure
the result is in the range [0,N-1]. Use the encrypted number as
an index into your table of items. For each user, you have to
remember the user key (maybe derived from the user ID) and the
index of the last item sent.

Ding! We have a winner! :)

Seriously, this was the answer I was going to post. To expand a
little on it, the "Hasty Pudding trick" is to start with a number in
the desired range and iterate the encryption function until you get a
result that is also in the range. The fact that a block cipher is a
permutation guarantees that this procedure will terminate, and the
average number of iterations needed is simply B/N, where B (= 2**b
above) is the number of possible cipher outputs and N is size of the
desired range.

As for the number of rounds, there's a well-known result by Luby and
Rackoff saying that four rounds are enough (even for crypto purposes,
which your use case isn't) if your round function is random enough.
Since your application presumably isn't performance-critical, you
could just take any standard cryptographic hash function and truncate
its output to use as your round function.

Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.