Re: Auditing subcommittee meeting at clerk convention in Colorado

[Neal McBurnett <neal@xxxxxxxxxxxxxxxxx>]

On Thu, Jan 15, 2009 at 11:45:50AM -0700, Paul E Condon wrote:
> On Thu, Jan 15, 2009 at 07:17:28AM -0700, Neal McBurnett wrote:
> > > > > re. the footnote:
> > > > > "If a computer pseudo-random number generator is used to help select
> > > > > the audit units, initial values or "seeds" for the generator should be
> > > > > chosen using a publicly observed, physical source of randomness, such
> > > > > as rolls of fair dice; also, the generator's algorithm must be
> > > > > published so that the public can verify that a valid algorithm was
> > > > > used."
> > > > 
> > > > Re: your suggestion to use times stamps for randomness: if you read the
> > > > references cited for the procedure we used in Boulder's audit:
> > > 
> > > SSUE is, of course, not random. But it is unfudgable, which is good
> > > for fending off conspiracy theorists. But there are other ideas. OK. I
> > 
> > But anything predictable is very unsuitable, since the person choosing
> > exactly when the times stamp is generated can thus choose a possibly
> > significant aspect of the outcome, like "this batch won't be audited".
> > 
> 
> But the attacher is not free to choose any 32bit number.  He is
> limited to a small selection of numbers centered around the one when
> the work was purported to be done. And consider my suggestion of using
> the product of time stamps from emails from two independent senders. In
> this case the range of values for each number is small but to
> precalculate all possible outcomes in order to choose a desired one is
> a very big computational problem. If the two emails calculation is not
> big enough, choose to require three emails, or four.
> 
> If part of the process of choosing were to assign a random number to
> each precinct and then choosing among these random numbers to choose
> which precincts to audit, I think the task of precomputing a preferred
> choice of time would be enormous. If there is a requirement that the
> actual SSEU values be published soon after the close of polls, there
> would be no possibility of post-election fudging.
> 
> Other countermeasures to your objection abound, this are just two.

Remember that it is essential that before the verifiable random
selection is done, everything is published so that everyone knows what
would be selected based on the random seed.  All the results are
published, all the weights for all the precincts, etc.  Nothing must
be left to the discretion of the officials except the random seed, or
else once again the whole thing is not verifiable or can be
manipulated.

Now suppose the attacker just needs to make sure that one particular
precinct is not audited, for some odd reason.  All they have to do is
calculate for each random number whether that precinct is audited or
not.  If it is just a time stamp, they just have to wait until a time
which results in no audit for the one they have to cover up.  If it is
a product of timestamps, then the last person to go, who might well
know what all the other timestamps were, simply again pre-calculates
the results and chooses a favorable one.

While it may still be hard to use that to do a whole lot of mischief
if you can only choose a few bits of the random number, the point is
that there are far better methods than timestamps, whether or not you
like ceremonies.

> But the issue of civil ceremony remains. If civil ceremony is needed,
> the dice throwing ceremony is, IMHO, quite appropriate. 
> 
> And it might be appropriate, as part of the public discourse, to
> assert that it is logically required to combat fraud. But count me an
> honest skeptic.
> 
> On further thought: I wonder what would be the goal of the attacker. I
> suppose there in no point in biasing the selection unless the attacker
> has also arranged to have had ordinary detectable fraud perpetrated
> in several precincts. Presumably enough precincts to swing the
> election.  If this is the situation, then he wants to bias the
> selection so that none of the precincts that were fraudulently
> reported are selected for audit. It does seem to me that it is
> possible to add sufficient tweaks to the SSUE idea to make the
> probability of attacker vanishingly small. The attacker works under
> his own set of constraints. We only need to make his problem
> impossibly hard, in the same way that public key cracking is believed
> to be impossibly hard. But comments on civil ceremony still apply.

For the other issues where you say that Rivest implies something in
the paper, I remain puzzled, since that's not how I read it.  Page
numbers would be helpful.

Thanks again for the dialog,

Neal McBurnett                 http://neal.mcburnett.org/

> > > read Rivest's paper. I think the suggestion that using hand
> > > calculators for the actual selection of precincts is --- crazy.
> > > 
> > > It is nice to have a calculation that can be repeated by a paranoid
> > > person, but to do the actual work that way is only OK when the process
> > > is still highly experimental and provisional. Later it should be
> > > reduced to computer code. There exist suitable software emulations of
> > > eight digit calculators.
> > 
> > No one suggests doing the actual calculations that way.  My open source
> > ElectionAudits code does it in python.  The calculator description is
> > indeed only for folks to be able to check it, which reduces the
> > "magic" aura of the randomness.
> > 
> 
> OK. But I got a serious impression that Rivest was suggesting this.
> Such an authority contradicting you, worries me. You are right, but
> you may not be heard.

...
> > > > you'll see that we really do want more than time stamps in order to get
> > > > secure, publically verifiable random numbers.  And it is important to
> > > > have evidence that folks from different parties, etc generate the
> > > > numbers privately and unveil them at the same time as described there,
> > > > so email won't do.
> > > > 
> > > > And the PRNG that we used (Rivest's SSR) is less complicated and can
> > > > easily be verified by calculator which again makes it well suited to
> > > > what we need.
> > > 
> > > Random numbers for statistical analysis are very different from random
> > > numbers for generating secure encryption keys. 
> > > 
> > > Rivest has some hand waving about how to get the right total number of
> > > precincts chosen to properly use the total level of effort that has
> ...
> > > The code for this sort of thing can be written in C++ and published.
> > > The seeds that are used are also published. The whole thing can be
> > > checked by the paranoids. Things that involve humans keeping paper
> > > records of what they did, or merely think they did, can't be checked
> > > so well. 
> > 
> > I wouldn't call it hand waving - it is quite specific, and varies for
> > PPEBWR vs NEGEXP in terms of whether you have to pick again or not.
> > 
> > Your description is is pretty similar to my code for choosing which
> > contests to audit.  It uses the python "bisect" module.  It is
> > published as open source in ElectionAudits - the
> > electionaudits/erandom.py file.  Check it out.
> 
> I was thinking on the basis of my understanding of Rivest's paper.

...

> > > > > Consider also a computer based seed: 
> > > > > Use the number of seconds since the Unix Epoch at the time of
> ...
> > > > > My preferred PRNG is the one published by Press, et. al., "Numerical
> > > > > Recipes ,,, ". Read this book when it comes time to make a selection.
> > > > > 
> > > 
> > > I don't see the need to make the audit decision at the precinct, as
> > > Rivest seems to want. Workers at the precinct are unlikely to be able
> > > to do an audit after a 14 hour day supervising the conduct of the
> > > vote. But maybe this is something that is really important to someone.
> > 
> > I don't know where you get that impression.  This mostly happens days
> > later at the state level or the county level, after all the
> > preliminary results are published for the entire contest.
> 
> Again, from the Rivest paper.