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