# Re: Constructing a random permutation on the fly

*From*: Ilmari Karonen <usenet2@xxxxxxxxxxxxxx>*Date*: 10 Jun 2009 15:32:32 GMT

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.

.

**Follow-Ups**:**Re: Constructing a random permutation on the fly***From:*Paul Rubin

**Re: Constructing a random permutation on the fly***From:*Paul Rubin

**References**:**Constructing a random permutation on the fly***From:*Tom Anderson

**Re: Constructing a random permutation on the fly***From:*Paul Rubin

- Prev by Date:
**Re: Sharing my 256-bit ECC library** - Next by Date:
**Re: Constructing a random permutation on the fly** - Previous by thread:
**Re: Constructing a random permutation on the fly** - Next by thread:
**Re: Constructing a random permutation on the fly** - Index(es):