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