Cryptography-Digest Digest #139, Volume #13 Fri, 10 Nov 00 23:13:01 EST
Contents:
Re: voting through pgp (Eric Lee Green)
Re: voting through pgp (David Schwartz)
Re: voting through pgp (David Wagner)
Re: voting through pgp (David Schwartz)
Re: Calculating the redudancy of english? (Bill Unruh)
Re: Photons, polarization and quantum crypto (Bill Unruh)
Re: voting through pgp (SCOTT19U.ZIP_GUY)
Re: voting through pgp (David Wagner)
hardness of monoid word problem? (David A Molnar)
Re: voting through pgp (David Wagner)
Re: voting through pgp (SCOTT19U.ZIP_GUY)
Re: Q: Computations in a Galois Field (Paul Crowley)
----------------------------------------------------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: voting through pgp
Date: Fri, 10 Nov 2000 17:24:41 -0700
binary digit wrote:
> Imagine if everyone had pgp in the world and voted through pgp, every single
> vote could be verrified and everyone would be happy, and there wouldnt be
> this problem that is going on now in florida
What worries me about electronic voting is that it makes official corruption
into a centralizable event. All somebody has to do is hack one centralized
voting computer, switch the totals for the two candidates, and blammo. There's
no way to prove that it has happened.
I cannot conceive of any accounting system that would not include a paper
trail. There is a reason you receive a paper deposit receipt when you go to
your bank, and why a copy of that deposit receipt is also placed into a file
at that bank. That reason is so that you have physical proof that you
deposited that money into that account, and so that the bank's auditors can
audit parts of the paper trail as needed. There is a reason why you receive a
paper receipt when you go to the grocery store, and why a copy of that receipt
is also printed upon another roll of paper within that cash register. Again,
it is so that there's a paper trail that can be followed in case of fraud or
theft.
Accounting for votes is no different from accounting for dollars -- the same
principles apply, with some twists (such as, how to provide a paper trail
while providing anonymity for the voter). Alas, too many people proposing
electronic voting systems appear to disregard those time-proven principles.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer "The BRU Guys"
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: voting through pgp
Date: Fri, 10 Nov 2000 16:28:14 -0800
Eric Lee Green wrote:
> binary digit wrote:
> > Imagine if everyone had pgp in the world and voted through pgp, every single
> > vote could be verrified and everyone would be happy, and there wouldnt be
> > this problem that is going on now in florida
>
> What worries me about electronic voting is that it makes official corruption
> into a centralizable event. All somebody has to do is hack one centralized
> voting computer, switch the totals for the two candidates, and blammo. There's
> no way to prove that it has happened.
Not at all. You just have to be sufficiently clever. For example, the
official results could include a table of the 'key' for each person who
voted for that candidate. That would allow every single voter to know
precisely where his or her vote was counted. If his vote appeared in the
wrong column, he could submit has electronic voting receipt (which would
just be a digital signature from the 'voting server') and demand his
vote be moved.
> I cannot conceive of any accounting system that would not include a paper
> trail. There is a reason you receive a paper deposit receipt when you go to
> your bank, and why a copy of that deposit receipt is also placed into a file
> at that bank.
A digital signature of the data on that paper receipt signed by the
bank's key would be just as good, unless the bank tried to claim that
their key was compromised.
> That reason is so that you have physical proof that you
> deposited that money into that account, and so that the bank's auditors can
> audit parts of the paper trail as needed. There is a reason why you receive a
> paper receipt when you go to the grocery store, and why a copy of that receipt
> is also printed upon another roll of paper within that cash register. Again,
> it is so that there's a paper trail that can be followed in case of fraud or
> theft.
All of these things could be electronic just as well. All that's need
is a digital signature that the issuer of the receipt can't deny.
> Accounting for votes is no different from accounting for dollars -- the same
> principles apply, with some twists (such as, how to provide a paper trail
> while providing anonymity for the voter). Alas, too many people proposing
> electronic voting systems appear to disregard those time-proven principles.
Your first sentence is right your second sentence is wrong. The way we
account for dollars right now does not provide very good anonymity. The
people I know of who are looking into elecronic voting technologies are
looking into the exact same methods being discussed to _improve_ the way
we track financial transactions. Paper receipts are not a particularly
good balance between anonymity and accountability.
For one thing, it's hard to keep a paper receipt without risking that
the receipt will be located on you. An electronic receipt can be
encrypted by the recipient. Most of your arguments are just showing the
limitations of your imagination.
DS
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: voting through pgp
Date: 11 Nov 2000 00:53:31 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
David Schwartz wrote:
> Absolutely! However, the scheme I suggested neither makes this easier
>nor harder. The two questions are completely orthogonal.
I cannot see how they are orthogonal, and in fact, it seems to me
that attack detection and anonymity seem to be crucially linked when
building electronic voting systems. In fact, see below for a good
example of this tension/challenge.
> Perhaps, for example, there could be a period after the polls close but
>before the results are released wherein people could query their votes
>and compare them to what they believe they voted. If there's a mismatch,
>they would have to go to some polling center and scream bloody murder.
Ahh, but that re-introduces the coercion problem! I put a gun to
your head, tell you to vote my way, and tell you that I'll be checking
up on you after the election to make sure you didn't vote a second time.
By introducing a way for voters to query what they voted for, you've
introduced a way for coercers to stick a gun to a voter's head and force
him to reveal which way he voted, which defeats the purpose of the
"you can vote more than once so you can't be coerced" mechanism.
In any case, even if it solved the coercion problem, I don't think
it's a practical scheme. It this requires that all voters actually take
the time to _check_ that the published serial number is the one they used!
And this is not terribly likely.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: voting through pgp
Date: Fri, 10 Nov 2000 17:03:02 -0800
David Wagner wrote:
> Ahh, but that re-introduces the coercion problem! I put a gun to
> your head, tell you to vote my way, and tell you that I'll be checking
> up on you after the election to make sure you didn't vote a second time.
> By introducing a way for voters to query what they voted for, you've
> introduced a way for coercers to stick a gun to a voter's head and force
> him to reveal which way he voted, which defeats the purpose of the
> "you can vote more than once so you can't be coerced" mechanism.
Use a simple algorithm to allow a coerced voter to get the reply back
that they want. For example, if I want to get back my true vote, my code
would be '4'. If I want to get back that I voted for Gore, my code could
be '5'. So if you try to force me to vote for Gore, I can tell you that
you are welcome to confirm that I voted for Gore, my code is '5'.
> In any case, even if it solved the coercion problem, I don't think
> it's a practical scheme. It this requires that all voters actually take
> the time to _check_ that the published serial number is the one they used!
> And this is not terribly likely.
That process can easily by automated. If a vote is close, more people
will check. The further apart the vote, the more fraud is needed to trip
it and the more likely it would be detected.
DS
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Calculating the redudancy of english?
Date: 11 Nov 2000 01:28:40 GMT
In <8uhg1c$sdj$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Bill Unruh) writes:
]In <8u7e4p$9m4$[EMAIL PROTECTED]> "David C. Barber" <[EMAIL PROTECTED]> writes:
]]I was speaking of dictionary entries *and* their following definitions,
]]where common words would likely be more used than uncommon words.
]] *David Barber*
]]"Kristopher Johnson" <[EMAIL PROTECTED]> wrote in
]]message news:5KFM5.16697$[EMAIL PROTECTED]...
]]> Dictionary entries aren't representative of "real-world" letter or word
]]> frequencies.
]They may however be more representative of "password" use of words,
]since passwords are single (often rare) words without all of the added
]grammatical "chaff" of text (where for example words like "a" or "the" or
]"of" do not occur.) Ie, what the redundancy of English is is situation
]dependent.
]
I just used the trigrams of a dictionary and of a text passage ( a Linux
HOWTO) to calculate the "redundancy" of English, (ie how often the
various trigrams repeat in those passages compared with a random
selection) In addition to the letters of English (only lowercase) I also
use the apostrophe and the hyphen, as they do occur non-negligibly in
English words, and also the beginning and ending of words (ie the
beginning blank, and the ending blank) as letters.
The measurement gives and entropy of -7.44 for the dictionary words, and
about -6.2 for the Howto. This corresponds with what one would expect if
one randomly made words from an alphabet only 12 or 8 characters long in each case.
Ie, on this basis the redundancy of English is about 2.5 (for the
dictionary) or 4 (for the text).
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Crossposted-To: sci.optics,sci.physics
Subject: Re: Photons, polarization and quantum crypto
Date: 11 Nov 2000 01:36:43 GMT
In <8uhgt6$efb$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
]Hi folks,
]I just finished reading Simon Singh's excellent "The Code Book", about
]the history of cryptography and cryptanalysis. At the end, he describes
]the principles of quantum cryptography in which the polarization state
]of single photons is used to convey information. Specifically, they
]would be used to transmit cryptographic keys used for decrypting
]messages. It is stated that this method is absolutely secure in part
]because interception of the photons and measurement of their
]polarization states is impossible without changing the state
](Heisenberg) and thus alerting the proper receiver that someone has
]stuck their hand in. There are other elements of the system, including
]a method by which the proper receiver makes measurements (still changing
]the state), but is able to deduce along with the sender what the key
]should be. The important point, however, is the above general method, as
]well as the concept that what is needed are 4 possible polarization
]states: vertical, horizontal, 45 degrees left, 45 degrees right.
]I have thought of one method by which such a system might indeed be
]subject to attack/interception without changing the states
]*sufficiently* to alert either sender or receiver.
]Suppose photon 1 comes along with a given but unknown (to
]the interceptor) polarization. The interceptor places a half-wave plate
]in the path. Classically at least, the polarization state will be
]rotated by twice the angle between the half-wave plate optic axis and
]the photon polarization direction.
]During this interaction, a torque is imparted on the plate in order to
]preserve angular momentum. Now, this torque may be vanishingly small,
Actually, the angular momentum of the photon is unchanged after going
throught the plate. It began as an equal supreposition of angular
momentum along and antiparallel to the direction of motion, and ends in
exactly the same situation, with only the phase between the two changed
(by 90 degrees). Ie, there is no net torque on the plate.
iNow while the photon is traversing the plate, there may be.
Unfortunately if yo umeasured it while the photon traversed the plate,
you would rotate the plate by an unknown amount as the photon traversed
the plate, and thus the phase of the two parts coming out of th eplate
would have been scrambled. Ie, the polarisations would no longer be the
definite linear polarisations you started with.
]but *hypothetically* I propose that it could be measured. Furthermore,
]the magnitude of this torque would be proportional to the angle between
]the photon polarization. Thus, one could know, certainly to within 90
]degrees, what the state of the photon was just prior to entering the
]plate. If the photon was lined up with the optic axis, there would be
]no rotation and no torque. If it was at 45 degrees there would be a 90
]degree rotation and some torque. If it was at 90 degrees, there would be
]180 degrees rotation and the maximum torque.
]Following the first half-wave plate would be another, identically
]aligned half-wave plate. This would then reverse the effects of the
]first plate, leaving the photon in its initial state, or at least very
]close to its intitial state.
]My questions to you, gentle readers who are more versed in quantum
]mechanics, are:
]Will a single photon indeed be rotated by a half-wave plate (or any
]retarder). Classically one thinks/speaks of the plate introducing a
]phase shift between orthogonal components of a light beam, which in turn
]is part of the classical explanation for any of the various states of
]polarization. What about one photon?
Yes.
]Assuming that indeed a single photon may have its polarization direction
]altered in such a manner, can the torque be detected? If so, perhaps it
]cannot be detected without changing it. Also, passing through the
]wave-plate may not impart an exactly 2 theta rotation to the photon, at
]least not as compared to its original polarization direction. The 2
]theta would be exact only as compared to the half-wave plate optic axis
]*after* it has rotated slightly to zero-out the net angular momentum of
]the system. But for the cryptographic system, 90.000000001 degrees is
]just as good as 90.0000000000000000 degrees.
In order to measure the effect of the photon inside the plate accurately
you will mess up the phases of the two circular polarisation components
which make up the linear polarisation, and thus mess up the linear
polarisation which comes out.
]I reiterate that I am not well versed in QM. This is the reason I am
]writing. Is this idea dumb?
]Thanks very much for your opinion on this.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: voting through pgp
Date: 11 Nov 2000 03:04:36 GMT
[EMAIL PROTECTED] (David Schwartz) wrote in
<[EMAIL PROTECTED]>:
>
>David Wagner wrote:
>
>> Ahh, but that re-introduces the coercion problem! I put a gun to
>
Ahh but what about ghost voters. You give a buch of bums
cigarattes and have them vote your way. Of course that could
never happen in real life. Cigarettes for votes. Sorry I forgot
it happen in American all the time. I heard the Bush camp my sue
over the democrats buying votes from bums with cigarettes.
Where will this fucking litagation end. Will lawyers be the only
winners.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: voting through pgp
Date: 11 Nov 2000 03:27:57 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
David Schwartz wrote:
> Use a simple algorithm to allow a coerced voter to get the reply back
>that they want. For example, if I want to get back my true vote, my code
>would be '4'. If I want to get back that I voted for Gore, my code could
>be '5'. So if you try to force me to vote for Gore, I can tell you that
>you are welcome to confirm that I voted for Gore, my code is '5'.
If you think voters will grok all this, I think you are a bit optimistic.
>> In any case, even if it solved the coercion problem, I don't think
>> it's a practical scheme. It this requires that all voters actually take
>> the time to _check_ that the published serial number is the one they used!
>> And this is not terribly likely.
>
> That process can easily by automated. If a vote is close, more people
>will check. The further apart the vote, the more fraud is needed to trip
>it and the more likely it would be detected.
Automated? How?!? The only way I see to automate the check requires my
computer to remember which serial number I've used last -- but this bring
back the coercion problem, because it allows a coercer to see that the
serial number stored on my computer's hard disk has been bumped up since
he last stuck a gun to my head. Are you sure that this can been automated
securely? Or am I missing something?
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: hardness of monoid word problem?
Date: 11 Nov 2000 03:02:24 GMT
Hi,
Does anyone have pointers to using the following problem for cryptography:
Given: A finitely presented monoid M (say by generators and relations) and
some string S.
Question1 : Can S be derived by composing elements of M ("is S an element
of M?")?
Question2 : If S is an element of M, what is an explicit derivation of
S from a set of generators of M ?
I think that this is either called or closely related to the "word
problem" for a monoid M.
I am aware of the Anshel-Goldfeld scheme for encryption based on the word
problem in a particular group. I am wondering if something similar may be
constructed for a monoid. I also vaguely remember something in A.
Salomaa's book _Public-Key Cryptography_ along these lines regarding
syntactic monoids of automata -- does anyone have results on the security
of that scheme?
I know there exist finitely presented monoids in which the word problem is
undecidable. It seems to me that a "bounded derivation" version of the
word problem in such monoids is then likely to be NP-hard. Not that this
tells us anything about difficulty in practice, of course. :-)
Thanks much,
-David Molnar
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: voting through pgp
Date: 11 Nov 2000 03:31:06 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
SCOTT19U.ZIP_GUY wrote:
> Ahh but what about ghost voters. You give a buch of bums
>cigarattes and have them vote your way.
Yes, I think we should take care to think very carefully about
these attacks before changing the system! The risks of electronic
voting are not confined to electronic attacks. To give another
example, absentee ballots are traditionally an important point of
potential vulnerability.
However, with this particular case, I'm not sure I see why electronic
voting would increase the frequency of the "votes for smokes" class
of voting fraud. What is it about electronic voting that would make
this problem any worse than it already in today's paper-based system?
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: voting through pgp
Date: 11 Nov 2000 03:40:06 GMT
[EMAIL PROTECTED] (David Wagner) wrote in
<8uiehq$od0$[EMAIL PROTECTED]>:
>SCOTT19U.ZIP_GUY wrote:
>> Ahh but what about ghost voters. You give a buch of bums
>>cigarattes and have them vote your way.
>
>Yes, I think we should take care to think very carefully about
>these attacks before changing the system! The risks of electronic
>voting are not confined to electronic attacks. To give another
>example, absentee ballots are traditionally an important point of
>potential vulnerability.
I personally think that absentess ballots is a bad idea. If your
not in the area to bad. except for the military. I also think will
we see tampering in the Flordia election. I still think Gore will
win. He did not appoint a son of the famous Daley of Chicago for
nothing. Why did he not do the honorable thing like Bushs brother
and stay out of the process.
>
>However, with this particular case, I'm not sure I see why electronic
>voting would increase the frequency of the "votes for smokes" class
>of voting fraud. What is it about electronic voting that would make
>this problem any worse than it already in today's paper-based system?
>
Nothing except a false sate of security. I was very impressed to
witness the last election in Mexcio they really take voting serious
and fraud in the last election there was much lower than in the
banana republic you and I call home. Electronic voting will make it
more corruptable.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Q: Computations in a Galois Field
Date: Sat, 11 Nov 2000 04:04:45 GMT
Mok-Kong Shen wrote:
> My understanding of the section you mentioned is that both
> the x to 1/x mapping and the affine transformation are
> such that they are simple to describe and (apparently by
> some chance) happen to be very good.
The x -> 1/x thing is known to be very good; it's not coincidence, it's
well known as a bijective S-box strongly resistant to DC and LC. Any
affine transformation would preserve these properties; it's not hard to
choose a simple one that achieves the few extra properties that the
Rijndael designers wanted.
Now I understand why you're asking - you want a non-interoperable
variant! You could go for choosing a different affine function with the
same nice properties, there should be many. I don't think I'd recommend
messing with MixColumn, and I'd *definitely* leave ShiftRow alone.
Frankly, though, your best bet is probably a simple variant of the key
schedule; this will probably allow you to implement your variant on
Rijndael hardware. A radically different set of round constants would
probably do it.
Unless I'm not guessing the purpose of this variant properly?
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
** 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
******************************
