Cryptography-Digest Digest #227, Volume #13 Sun, 26 Nov 00 01:13:01 EST
Contents:
Re: A Simple Voting Procedure (Shawn Willden)
Re: A Simple Voting Procedure (David Schwartz)
Modulo Addition (George)
Re: A Simple Voting Procedure (Darren New)
Re: A Simple Voting Procedure (David Schwartz)
Re: vote buying... (Kat Hopwood)
The AES MixColumn transform (Brian R. Bullock)
Re: The AES MixColumn transform (Dido Sevilla)
Re: Modulo Addition (Dido Sevilla)
Re: PLEASE DON'T HELP Re: How to find celebrity (David A Molnar)
Re: A Simple Voting Procedure ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Sat, 25 Nov 2000 16:40:04 -0700
David Schwartz wrote:
> Darren New wrote:
> >
> > David Schwartz wrote:
> > > This can happen in *ANY* voting scheme.
> >
> > Not really. The dictator cannot torture you until you prove who you voted
> > for in the current scheme, because there's no way to prove right now.
>
> Sure there is. You sneak a camera into the voting room with you and
> photograph yourself voting.
Photograph yourself voting for one candidate, take the photo home and alter it to
show yourself voting for another candidate. Photographs are not proof of
anything.
Shawn.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Sat, 25 Nov 2000 15:58:38 -0800
Shawn Willden wrote:
>
> David Schwartz wrote:
>
> > Darren New wrote:
> > >
> > > David Schwartz wrote:
> > > > This can happen in *ANY* voting scheme.
> > >
> > > Not really. The dictator cannot torture you until you prove who you voted
> > > for in the current scheme, because there's no way to prove right now.
> >
> > Sure there is. You sneak a camera into the voting room with you and
> > photograph yourself voting.
>
> Photograph yourself voting for one candidate, take the photo home and alter it to
> show yourself voting for another candidate. Photographs are not proof of
> anything.
Exactly. In the scheme I presented, there's no way to absolutely prove
you voted one way or another. In fact, I doubt any practical scheme
could ever be developed where it's possible for someone to prove with
absolulte certainty how they voted. Pretty much anything can be tampered
with if you go to enough trouble.
That's why requirements should be stated in terms of relative
difficulty. For some things, it's very important that it be as close to
impossible as we can make them (for example, figuring out how a
particular person voted after the election). For some things, we don't
need to make it quite that difficult, but we don't want it to be easy
(for example, proving you voted a particular way if you try to break the
rules to make this possible).
DS
------------------------------
From: George <[EMAIL PROTECTED]>
Subject: Modulo Addition
Reply-To: [EMAIL PROTECTED]
Date: Sat, 25 Nov 2000 18:25:35 -0600
Sorry to ask such a simple question in this newsgroup, but I'm having
problems with addition modulo 2^32. I'm trying to implement SHA 256 right
now, and I can't get the right results when adding words because of an error
in my modulo addition. Could someone please give me an example of adding 5
32-bit words using modulo addition? If not, could I please be dirrected to a
web page that has a tutorial on this information? I've done some research,
and I have using posting in this ng as a last resort. Thank you for you
time.
-George
[EMAIL PROTECTED]
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Sun, 26 Nov 2000 00:26:02 GMT
David Schwartz wrote:
> You can never
> prove to anyone that you voted any particular way (which is fine, since
> you *know* you voted and it's nobody else's business).
Alright, then you don't hav P1. Of course, the problem remains one of
terminology. If you say "You have to be able to prove your vote was counted
correctly", that implies convincing someone else that it was counted
incorrectly. If you just mean "you want to confirm it was counted correctly"
then that's a different problem. I'll agree that it's possible to have a
system that you can confirm to yourself whether or not your vote was
correctly counted without being able to be coerced into revealing how you
voted.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
Both democracy and capitalism are attempts to make
greed and selfishness work for the greater good.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Sat, 25 Nov 2000 16:58:41 -0800
Darren New wrote:
>
> David Schwartz wrote:
> > You can never
> > prove to anyone that you voted any particular way (which is fine, since
> > you *know* you voted and it's nobody else's business).
>
> Alright, then you don't hav P1. Of course, the problem remains one of
> terminology. If you say "You have to be able to prove your vote was counted
> correctly", that implies convincing someone else that it was counted
> incorrectly.
That's a different problem, and for that problem I have an alternate
solution wherein your GUID and vote are signed by an 'election key'.
That way if your GUID does appear in the wrong column, and you kept your
GUID and signature, you can do this.
> If you just mean "you want to confirm it was counted correctly"
> then that's a different problem. I'll agree that it's possible to have a
> system that you can confirm to yourself whether or not your vote was
> correctly counted without being able to be coerced into revealing how you
> voted.
P1 was stated:
p1) voter can prove, by himself alone, at his sole option, that his vote
is or is not correctly counted.
If you want a system where the voter can prove it to anyone, you need
to do the following:
1) voter is shown a random GUID before he votes
2) voter may or may not record the GUID
3) voter votes
4) voter is presented a signature the confirms that his GUID voted as
he claimed it did
5) voter may or may not record the signature
6) voter may request to be shown any number of other GUIDs/signatures
for any candidates he pleases
7) voters are encouraged to upload their GUIDs/signatures to a public
pool immediately after voting.
8) immediately after election, all GUIDs and signatures are made public
In this case, if the voter presents a GUID and signature, and the GUID
is not counted correctly, this means that someone's vote was incorrectly
tallied. An official should fix it, since the signature is presumptive
evidence that the vote should have been counted. Nobody can really prove
whose vite it was, but that's not really important. In fact, that's
precisely what you _don't_ want.
If you worry about the GUIDs being selected out of a small pool, you
can show the voter his GUID and then allow him to either vote or reject
the GUID. If he rejects the GUID, the following happens:
1) The voter picks who the rejected GUID will be voted for.
2) The voter gets a signature for the rejected GUID (which he can
record if he wants to allow him to "prove" he voted for Gore even if he
didn't).
3) Counterbalancing votes are issued for each other candidate with new
GUIDs. Incudling one vote for a 'marker candidate' who serves simply to
count the number of rejected votes.
4) The voter is presented a new GUID and the process starts over.
5) When the final results are tallied, the number of votes cast for the
'marker candidate' is subtracted from the vote tally for each official
candidate to get the true tally.
Note that I'm not actually adovocating this scheme. It's just to
demonstrate that certain goals can be achieved.
DS
------------------------------
Date: Sun, 26 Nov 2000 01:15:22 +0000
From: Kat Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: vote buying...
=====BEGIN PGP SIGNED MESSAGE=====
David A Molnar wrote:
> David Hopwood <[EMAIL PROTECTED]> wrote:
>
> > All the attempted solutions I've seen fail to solve the problem that
> > voters' authentication credentials can be bought.
Someone pointed out that absentee ballots already have this problem.
That's true, and it is one reason why the proportion of the vote that
is done using absentee ballots should be minimised, IMHO.
> > (Authentication
> > credentials are whatever a voter knows or has that proves that they
> > are eligible to vote, and that distinguishes them from another voter -
> > e.g. keys or smartcards.)
>
> What do you think of making the credentials sufficiently important for
> other things as well that they're too expensive to buy in bulk? e.g. the
> credential allows voting, but it also allows access to a bank account, so
> you need to pay someone his bank balance or more before he'll give it up.
> This is only a partial solution, but it seems better than nothing.
I don't see any way to enforce this without introducing more security
problems. Credentials can be compromised unintentionally, so a protocol
that deliberately tries to maximise the loss when they are compromised
is unlikely to get much support. (This applies more generally, not just
to voting protocols.)
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOiBj9zkCAxeYt5gVAQECaAf9EncnO048pTIwL3FJe8J7UWV2BDpdaXG5
NK8lnQyN71cUvDT1fuWJq2lxDOObWKsA3GzToCq2/1uwxTpLVuBPkah9oZRryRyp
xTINhHrxjfqgpqWL7RdKdI+uv04IehBzfPsWSOc7BwufVX+ZlVpozpQuAy4x2A6n
pfArQjA54Gi3hVPY1DrEItFoIeQM+B4M70PY3ukrM893LLZKmAmtFxrKfnZfOclc
trXUONYH7IHQE2SAXgS5BK1SRNEywp16maKd+ws14ycSmrM6ATQJN3Hzdg/Bsk3w
WOXOtC/yNObR4ReaGlvAnWOq+Ii3x6+0tKtc6oVAQittQ+i+AE3m9Q==
=g5Dr
=====END PGP SIGNATURE=====
------------------------------
From: brian@@@wwwebweaver.com (Brian R. Bullock)
Subject: The AES MixColumn transform
Date: Sun, 26 Nov 2000 01:38:14 GMT
I'm having trouble understanding how to accomplish the AES (Rijndael)
MixColumn transform without using log table lookups. Anyone with a
simple explanation?
Thanks.
Brian R. Bullock
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: The AES MixColumn transform
Date: Sun, 26 Nov 2000 12:02:05 +0800
"Brian R. Bullock" wrote:
>
> I'm having trouble understanding how to accomplish the AES (Rijndael)
> MixColumn transform without using log table lookups. Anyone with a
> simple explanation?
>
Hopefully you have some sort of understanding of arithmetic in Galois
Fields in the representation chosen for Rijndael. One way you can
perform the mixcolumn transform without using log table lookups is by
using the xtime function, which multiplies its argument by 2 in
GF(2^8). I take it you understand that the mixcolumn, which is a
polynomial multiplication, can be represented as multiplication of each
column of the cipher state by a circulant matrix with coefficients 02,
03, 01, and 01 in GF(2^8). Note that x*02 is just xtime(x). x*03 =
xtime(x) + x. All you need is a function that computes xtime, for which
you can keep either a lookup table (if you want to avoid timing
attacks), or use this C function:
unsigned char xtime(unsigned char x)
{
x <<= 1;
return((x & 0x80) ? x ^ 0x1b : x);
}
It seems to me that you haven't read, or at the very least, not quite
understood the Rijndael specification paper. Go read it more carefully,
as it doesn't even use log tables at all in its implementation remarks
for mixcolumn. Xtime is also more completely explained there too.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: Modulo Addition
Date: Sun, 26 Nov 2000 12:11:16 +0800
George wrote:
>
> Sorry to ask such a simple question in this newsgroup, but I'm having
> problems with addition modulo 2^32. I'm trying to implement SHA 256 right
> now, and I can't get the right results when adding words because of an error
> in my modulo addition. Could someone please give me an example of adding 5
> 32-bit words using modulo addition? If not, could I please be dirrected to a
> web page that has a tutorial on this information? I've done some research,
> and I have using posting in this ng as a last resort. Thank you for you
> time.
>
I think you're having problems with your computer's integer
representation. If your computer is a 32-bit machine (as is typical),
and you're trying to do this in C, then any addition you perform with
unsigned ints is already addition modulo 2^32. If you have a DEC Alpha
or some other 64-bit computer, you'll have to discard all of the high
bits by performing an AND with 0x00000000ffffffff. In general, you can
perform arithmetic modulo 2^n by performing the arithmetic operation,
and then getting the bitwise AND of the result with 2^n - 1.
I suppose you know what it means to do addition modulo 2^32. In
general, the sum of two 32-bit numbers is 33 bits long, but in this
arithmetic, we discard the extra bit. To take a simple example, say we
want to find the sum of the two values 0xffffffff and 0x00000010. The
result is 0x0000000f...one way of thinking about it is the result
overflowed, and only the low 32 bits of what should have been the result
were kept. The actual sum of 0xffffffff and 0x00000010 is of course
0x10000000f, but this result is 33 bits. We chop off the extra bit and
keep that as the result.
Frankly, I don't think that your problem in implementing SHA-256 is
this, though...
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: PLEASE DON'T HELP Re: How to find celebrity
Date: 26 Nov 2000 04:48:34 GMT
Alex Chacha <[EMAIL PROTECTED]> wrote:
> student. Sort of like doing 2+2 via for(s=0,i=0;i<1;++i) s+=2; It would be
> obvious that if a student is asked the problem (of 2+2), they are not
> capable of producing a simplfication of a much more complex solution.
This reminds me of "50 ways to take a midterm you're sure to fail" --
work pi and complex numbers into every proof.
-David
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: A Simple Voting Procedure
Date: Sun, 26 Nov 2000 05:07:54 GMT
This is an interesting proposition because it attempts to leap over
the top of the main problem with moving to online voting - that the
process is invisible and so not trusted. What you are proposing is a
a lateral thinking solution - ie dont focus on how to secure the
process - instead provide a way to demosntrate that the outcome is
correct.
Unfortunately, as debated in the long following thread, there are
undesirable outcomes from the approach you propose - either a person
can prove their vote (which leads to vote buying), or they cant (which
means the accuracy of the online electoral process remains in doubt).
If this is accepted then perhaps we have to go back to implementing in
an online electoral process the same sorts of controls that we
currently rely on for the not-online (since we actually trust the
current process even though we dont literally see our ballot going
through it). These include controlled printing of ballot papers;
countersigning of ballots at the polling station by electoral
officials when they are issued to the voter so that even if someone
gets their hands on some unused ballot papers, they need to also be
able to forge the signature of an electoral official; etc.
The following sketch is provided as a starting point so that
weaknesses can be identified, discussed and addressed, not as a
finished solution.
Lets suppose that an electronic ballot is a certificate signed by the
electoral commission, which is further countersigned by an issuing
electorate server (the online equivalent of the polling station) when
issued to a voter in that electorate. This provides the beginnings of
an audit trail for the validity of the ballot, without identifying the
voter or how they voted. It prevents ballot box stuffing using either
forged ballot papers (certificates), or copies of genuine certificates
but not issued to a specific voter.
To vote online, the voter must authenticate their identity as a voter
to get their name crossed off the role and be issued with a ballot
paper (certificate). This would be done similar to the current
approach - that is they would enrol on a register. At time of
enrolment they would be provided with a userid and password combo with
which to vote.
Come voting time, they log on to the main electoral server using their
userid/password combination. Teh main electoral server then freezes
their id on the roll so no-one else can vote under that id, then
redirects them to the relevant electorate server based on their
enrolment, but does so without passing their id to the electoral
server - rather it passes a random one-time session id and the ballot
certificate. From the electoral server's point of view the voter is
now anonymous, but has the right to vote in that electorate with a
valid ballot certificate.
The electoral server signs the ballot cerificate prior to voting so
that the ballot cannot be used in another electorate, and the voter
then records their vote. The electoral server uses the doubly signed
(by the main electoral server and the electorate server)
certificate/session id to also verify that the ballot is a valid one
when the voters sends it back after completing their vote. The
session id is split from the vote and sent back to the main electoral
server to confirm that the vote was completed (in case the client's
computer crashes during the vote and the process has to be
reinitiated).
If the voter turns up again at the main electoral server, *before* the
session id is returned from the electoral server, then the main server
notifies the electorate server that the previous session id is
cancelled and reissues a new ballot certifcate and session id, and
redirects the voter to the electorate server. ie oif you mak a mess of
your ballot, it is cancelled and you get a new one, as in the current
system.
The votes are counted at the electoral server which then returns only
the aggregate returns for that electorate to the main electoral
server. So the vote cannot be associated with the identifying
information on the electoral role. Voters might be given a unique
receipt number, however, for having been crossed off the rolls, but it
would have no relationship to how they voted. This is may be relevant
in countries where attendance to vote is compulsory (eg Australia),
and people are fined for not attending to vote. It would provide an
audit trail for who voted, but not how they voted, and may be useful
if there were accusations of people voting using other people's
identities.
All code to run the election is open source so that any flaws can be
identified by lots of independent scrutiny. All source is digitally
signed, as is the compiled code, so that these signatures can be used
to verify that the compiled code used on election day has not been
tampered with. Compiled code is installed on the main and electorate
servers under the scrutiny of nominated party scrutineers and half a
dozen (court appointed?) independent witnesses.
The client software is also digitally signed, compiled, open source
code which is available for download from secure (SSL) electoral
servers to avoid MITM attacks.
The client software is configured to not use virtual memory, and to
encrypt all data written temporarily to RAM. All communication between
the client and the servers happens over encrypted links (SSL).
Problems this approach doesn't solve is how to guarantee that a person
is not being coerced as they make their vote (eg by their abusive
spouse at home). This is currently addressed by not allowing anyone
else into the polling booth with them. How this can be ensured when
they are voting from home or elsewhere is not clear, and is a major
challenge to online voting which doesn't require people to come to a
polling station. Perhaps for this reason, voting online wwill still
have to be done from polling stations. This has the added advantage
that the machines are ubnder the control of the electoral office
electoral so minimising the likelihood of trojans etc.
Anyway, this may serve as a staring point for discussion...
cheers
On Mon, 20 Nov 2000 20:17:22 -0500, Kevin A. Roll <[EMAIL PROTECTED]>
wrote:
>
>
>I'm not sure that cryptography is even necessary for a perfectly secure
>vote... consider the following scenario:
>
>1. At the time of voting, a random key number is generated (long enough
>to guarantee uniqueness amongst the pool of voters). This key is
>associated with the voter's selections, and provided to the voter. For
>example, you vote and are given back the key 'CBFGPGKWJH'.
>
>2. When the election is complete, the entire list of votes and keys is
>published/made available online.
>
>* Any person can tabulate the election votes themselves and verify the
>count.
>* Any particular individual can locate their votes using their unique key
>and verify that their vote is correctly recorded.
>* No person can identify another person's vote without knowing their
>unique key.
>
>3. To solve the other half of the problem, a separate list of equal size
>is published which details every indivual who voted. Anyone can verify
>the credentials of a given voter, eliminating dead voters, etc.
>
>4. If it is desired to be able to disqualify particular, individual
>votes, then a link between the two lists is necessary. This is where
>encryption would come into play... only a trusted authority would be able
>to decrypt the identity of a particular voter. However, I think step 2 is
>the crucial part of the process that is missing today... a way for the
>public to observe the results directly.
>
>Comments?
>
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
