Re: Constructing a random permutation on the fly
 From: Ilmari Karonen <usenet2@xxxxxxxxxxxxxx>
 Date: 10 Jun 2009 15:32:32 GMT
On 20090609, 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 >= N1. Then
for k < N, represent k as a bbit number. Chop that into two b/2bit
halves. Use a generic Feistel cipher to encrypt the pair of
halfnumbers with a userspecific 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,N1]. 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 wellknown 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 performancecritical, you
could just take any standard cryptographic hash function and truncate
its output to use as your round function.

Ilmari Karonen
To reply by email, please replace ".invalid" with ".net" in address.
.
 FollowUps:
 Re: Constructing a random permutation on the fly
 From: Paul Rubin
 Re: Constructing a random permutation on the fly
 From: Paul Rubin
 Re: Constructing a random permutation on the fly
 References:
 Constructing a random permutation on the fly
 From: Tom Anderson
 Re: Constructing a random permutation on the fly
 From: Paul Rubin
 Constructing a random permutation on the fly
 Prev by Date: Re: Sharing my 256bit 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):
Relevant Pages
