@Unpublished{Riv08a, author = { Ronald L. Rivest }, title = { A "Sum of Square Roots" (SSR) Pseudorandom Sampling Method for Election Audits }, date = { 2008-04-25 }, OPTyear = { 2008 }, OPTmonth = { April 25, }, note = { Unpublished draft. }, keywords = { pseudo-random number, pseudo-random function, dice, sampling, post-election audit, square-root, sum of square roots }, abstract = { This note proposes a cute little heuristic method of generating a uniformly distributed pseudo-random number between 0 and 1 for each precinct in an election, for use in selecting a sample of precincts for a post-election audit. A function \$f\$ is described that takes as input a 15-digit ``seed'' \$S\$ and a six-digit precinct number \$i\$, and produces a pseudo-random output \$x_i= f_S(i)\$ between 0 and 1. The seed \$S\$ is obtained by rolling fifteen dice in a public ceremony. For a 5\% audit, precinct \$i\$ will be audited if \$x_i \le 0.05\$. This approach also works well for auditing methods, such as \negexp{}, that set different auditing probabilities for different precincts. \par We call the proposed method the ``SSR'' method, as it is based on taking the fractional part of a sum of three square roots. One of the nice features of this method is that it can be performed on the simplest of pocket calculators (assuming it has a square-root button). Thus, local election officials and/or election observers can easily determine and/or verify whether or not each particular precinct should be audited, once the seed \$S\$ has been determined at headquarters. \par The SSR method should be highly unpredictable to an adversary---an adversary who does not know the seed should have no advantage in determining which precincts to corrupt. The SSR method is also highly efficient, since only 15 dice rolls need to be done, instead of thousands. Finally, it is easily verifiable on a simple calculator. }, }