@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.
},
}