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.
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:
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:
"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 [EMAIL PROTECTED]