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.
.



Relevant Pages

  • Re: Generation of range permutations?
    ... > I've located and simplified a code fragment that seems to do what I ... This code's purpose is to make a permutation on range. ... cipher operating on N bits of plaintext/ciphertext. ... The cipher iterates thru a number (ROUNDS) of rounds. ...
    (sci.crypt)
  • Re: Weakness of Feistel ciphers
    ... I am talking about computationally limited algorithmic information theory. ... The simplest algorithm implementing the cipher is more ... rounds to make the attack complexity high enough. ... if this is for some product or something use proper crypto. ...
    (sci.crypt)
  • Re: F-functions for Feistel block ciphers
    ... In other words, these two rounds are applied in one direction only, 16 ... times during the execution of the cipher. ... mixing operations (a bit like whitening in a Feistel block cipher). ... tmp = f; ...
    (sci.crypt)
  • Re: Posting encryption UserRPL illegal?
    ... I guess I'll have to go back to my slower programs. ... When a cryptosystem works by repeating "rounds" ... as one after another "attack on somewhat reduced-round ... the single "symmetric cipher" used in some basic PGP versions) ...
    (comp.sys.hp48)
  • Re: New RUIX cipher
    ... >a matrix of 8x8 is filled with plain data ... >Rounds are calculated taking 3 bits of the key expansion and computing ... Therefore, if an attacker can break 3 rounds of your cipher, an attacker ...
    (sci.crypt)