Re: Constructing a random permutation on the fly

On Jun 12, 3:31 pm, David Eather <eat...@xxxxxxxxxx> wrote:
Tom Anderson wrote:
Hello!

This question is not really about cryptography, but it has a
cryptographyish flavour, so i thought i'd ask it here. If there's a
better place to ask it, please let me know.

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. I only need to
go through each user's randomised list of items one by one, rather than
having random access into the list, but the process of going through
them could take days, weeks, perhaps even months.

I could put all the items in an array, shuffle them, and go through them
from first to last, storing the shuffled array for as long as it's
needed. Or i could put the numbers 0 ... N-1 in an array, shuffle and
store that, and go through that, using the numbers and indices into a
master list of items. However, i would like to avoid having to store
great big lists of numbers if at all possible.

So, what can i do?

My thinking is that i need three things. First, a counter for each user,
which starts at 0 and goes up to N-1. Secondly, a random(ish) key K, of
some form. Thirdly, a function which goes from a number in the range 0
... N-1 and a key to another number in the range 0 ... N-1, with the
three properties that (i) for any fixed value of the key, the mapping
between numbers is bijective, (ii) that mapping looks random (for some
vague but suitable definition of 'random'), and (iii) that for different
values of the key, the mapping looks different (for some vague but
suitable definition of 'different'). Then, when i need an item, i just
put the counter and the key through the function to get an index into a
master list of items, and then increment the counter. Thus, i can
construct a permutation of the items on the fly, storing only the
counter and the key.

The problem is that i have no idea how to construct the function. Any
suggestions?

A simple one would be f(counter, key) = (counter + key) mod N, but that
fails criterion (ii), and possibly (iii) as well. If N+1 was prime, i
could do f(counter, key) = (((counter + 1) * (key + 1)) mod (N+1)) - 1,
which would be a bit better. If N was 2^64, i could use a block cipher
with a 64-bit block, which would be great.

But i'd really like a function that would work for any N.

The best i've come up with so far is something like (apologies if this
explanation is bad, or if the idea is bogus):

- Find the prime factors of N

- Express them as powers of primes (so 50 is 2^1 * 5^2)

- Construct Galois fields of order p^n for each

- Construct the Cartesian product of the Galois fields; note that the
  order of this is N (right?)

- Define a reversible mapping from the numbers 0 ... N-1 to elements of
  the Cartesian product set; it doesn't matter what it is, so do it by
  going through the constituent Galois fields one by one, picking the
element x
  mod p^n for that field, and updating x to be x / p^n (like the fields
  were digits in some really trippy positional digital notation)

- Choose a key from the range 0 ... N-1

- Combine two numbers in the range 0 ... N-1 by converting them to
  elements of the Cartesian product, combining them by elementwise
  addition, and converting the result back to a number

I started that description thinking i'd be able to use multiplication in
GF(p^n) at the climax, but then realised that that wouldn't be bijective
because of the zeroes. So i've used addition, which is much less
avalanchey. As it stands, that function would be stunningly bad for
numbers of the form p^n - it would reduce to the (counter + key) mod N
function i dismissed above.

Okay, so can i factorise N (mostly) into subprime factors, and then use
elementwise modular multiplication with a +1/-1 shimmy to avoid zeroes,
also as above? Does that sentence make any sense at all to anyone?

Anyway, as you can see, i've got nothing. Any and all suggestions welcome!

tom

It seems to me that you know the elements, you know the way to randomly
shuffle them, so all you need to keep is the seed of a suitable CSPRNG
to recreate the list and hence a particular element whenever desired.

(Knuth has an algorithm for creating random permutations, but you could
also derive his method from the key setup of RC-4)

I did post to this thread concerning making a permutation using a
random number generator but there is a better way, easy to use, an
uses the strengths of any set as a base.

You say..here we go again...but read carefully and you might learn
something.

A number of years ago, I ran across discussion of an old ACA algorithm
that hinted of its use as a stream cipher. Being prior computer, its
promise was too difficult and subject to clerical errors. The idea
was that a stream of characters previously assigned places in a
character set could be used to produce a subsequent series. I
wondered it that was to be a recursive series and it proved to be so.
This all predated binary emphasis.

The idea is simple in a set of 0 to n-1 characters, add the place
values of the last two characters mod n to produce a following
character. The next step would be to work with that last character
and the preceeding one to build a string that would ultimately repeat
itself. The earliest character is dropped from the current list to
keep it a constant length. You must start with at least two
characters

To improve matters, add a numeric constant of 0 to n-1 to the
formula. I tend to make the default value 3 from experience but
others might be as good, but not 0 or 2.

Before going into the next steps of permutation building, look at next
posted examples of series as I have them up and running. The base set
for convenience is the plain alphabet, n=3, and the starting series
seed remain constant length.


.

Relevant Pages

  • Re: Constructing a random permutation on the fly
    ... great big lists of numbers if at all possible. ... Construct the Cartesian product of the Galois fields; ... The idea is simple in a set of 0 to n-1 characters, ... Before going into the next steps of permutation building, ...
    (sci.crypt)
  • Re: Warhammer Armies - Tilea
    ... and GW doesn't normally arbitrarily remove an army from the game ... >> other lists, just not as a single clumsy aggregate unit. ... >>>Because they're inherently Characters, not Units? ... you can take WE Core as mercenaries" you're ...
    (rec.games.miniatures.warhammer)
  • Re: NEWSWEEK article on Gail Simone
    ... mostly mistreated just like male characters, ... For instance, the list lists ... child too; unless the mother is Queen Hippolyta, ...
    (rec.arts.comics.dc.universe)
  • Re: NEWSWEEK article on Gail Simone
    ... mostly mistreated just like male characters, ... For instance, the list lists ... -- listing things that were stupid ideas shown by one writer for a short ...
    (rec.arts.comics.dc.universe)
  • Re: NEWSWEEK article on Gail Simone
    ... mostly mistreated just like male characters, ... For instance, the list lists ... -- listing things that were stupid ideas shown by one writer for a short ...
    (rec.arts.comics.dc.universe)
Loading