Re: Security markings on the ballot

From: David Mertz <voting-project_at_gnosis_dot_cx>
Date: Sat Oct 25 2003 - 19:59:00 CDT

Chris Schaefer <evm@1reality.org> wrote:
|The cryptographic signature would likely be quite long... as long as or
|longer than the vote information itself........

No, no, no! I wrote a mention of this, but I guess you missed it:

  P.S. contra Doug Jones, I don't think the security code has to be all
  that long. Assuming there was a keyed cryptographic function involved
  that made it unfeasable to produce a valid code without the key, six
  or eight digits would be plenty. That gets us down to requiring the
  bad guys to print 10^6-10^8 false ballots to produce a verifiable one.
  I'm happy with that.

Most existing algorithms use long signatures because they want to be
highly resistant to brute force attacks. But the attack model is very
different here. It requires the attacker to produce a valid ballot, not
decrypt a valid one. For that, we just need to make accidentally
producing a valid one UNLIKELY, not "life-of-the-universe" unfeasable.

For example, here's a technique:

    B = Ballot codes (votes, ballot-id, etc)
    K = Secret key
    C = Encrypt(K, B)
    H = Hash(C)

The encryption can be something strong like AES. The hash can be
something cryptographically strong like SHA (160 bits). No one can
produce a valid H unless they know K (life-of-universe type challenge).

What gets STORED on the ballot, however, need not be all 160 bits of H.
It can be the first 4 bits, or the first 32 bits, or the first 100 bits,
or whatever you want. SHA has a uniform distribution, so that knowing B
doesn't help you one whit in guessing those first 4 bits. The only
choice is what probability of a random H[init] being right you want to
accept. In my mind, a couple bytes (e.g. 16 bits) is more than we need
for this purpose.

Yours, David...

--
Keeping medicines from the bloodstreams of the sick; food from the bellies
of the hungry; books from the hands of the uneducated; technology from the
underdeveloped; and putting advocates of freedom in prisons.  Intellectual
property is to the 21st century what the slave trade was to the 16th.
==================================================================
= The content of this message, with the exception of any external 
= quotations under fair use, are released to the Public Domain    
==================================================================
Received on Fri Oct 31 23:17:04 2003

This archive was generated by hypermail 2.1.8 : Fri Oct 31 2003 - 23:17:07 CST