uniformly random selection algorithms

[Travis H.]

I didn't know about this RFC, but apparently the IETF
has a standard for selecting people randomly for sortition
in a publicly-verifiable way.

References:
http://rfc.sunsite.dk/rfc/rfc3797.html
http://www.isi.edu/in-notes/rfc3797.txt

This got me to thinking about random selection.

They take several publicly-verifiable randomly generated
numbers (such as government-run lotteries), concatenate
them in an unambiguous way, and then hash each one
(with a sequence number prefixed and suffixed), treat the
results as a 128-bit big-endian integer, and take the
remainder after division by the remaining pool size
(i.e. without replacement).

However, there's a slight bias for people towards the
front of the pool; for demonstration, assume we start
with a uniformly random 8-bit number instead of
128-bit, on a pool size of 100.  These numbers are
selected to exaggerate the bias.  The first 55 people
have 3 opportunities to win; person 0 has 0, 100, and
200.  However, person 56 has only two; 56 and 156.

It's a minor point for small pools and 128-bit integers,
but wouldn't it be mathematically more uniform to
create a pseudorandom stream from the hashed
outputs and then apply one of the following algorithms?
Assume a pool size p, lg means binary logarithm,
n=ceil(lg(p)) and x is an unsigned big-endian integer:

1. Trial-and-error:
x = extraction of n bits
If x < p, then return x.
Otherwise, discard and repeat.

2. This algorithm seems to waste fewer bits:

Initialize with c = 0.
x = extraction of n bits.
Let y = x+c
If y < p, then return y
Otherwise, let c = y - p
Go back to the extraction step.

3. This may be more efficient still;

Pick b such that 2^b >> p (e.g. p=100, b=128)
Let q = floor(2^b/p)
y = one of the earlier algorithms with p=pq
Return y mod n

In this last algorithm, b is chosen to be a
computationally-convenient size (e.g. size
of the hash output).

PS: In case anyone doesn't know, Lynn Wheeler's RFC index is amazing.
Best RFC interface ever:
http://www.garlic.com/~lynn/rfcietff.htm
-- 
"If you're not part of the solution, you're part of the precipitate."
Unix "guru" for rent or hire -><- http://www.lightconsulting.com/~travis/
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com