Primer on concepts in cryptographic voting

From: Charlie Strauss <cems_at_browndogs_dot_org>
Date: Sat Dec 16 2006 - 01:06:00 CST

since we've been discussing this I thought I'd take a stab at a
layman's guide to crypto. It's an early draft. feel free to add on.

Primer on concepts in cryptographic voting

EARLY DRAFT Dec 15 2006

Charlie E. M. Strauss

Who is this for?

The purpose of this document is to introduce lay people--not
cryptographers--to high level concepts in cryptography needed to
appreciate encrypted voting technologies. The goal is not to wade
through the detailed math but to get right to sophisticated concepts
and notionally convey their importance and meaning. This is also not
meant to present any particular air-tight system for cryptographic
voting. It is just a primer on concepts one may encounter in
considering some scheme. Nor are the assertions made here
authoritative, the author is not a cryptographer and is merely hoping
to convey the gist even if the details contain specific errors.

It is expected that the reader is a technologist. In a few example I
will use limited math terms to clarify or demonstrate the idea but in
all cases it will not be required and can be skipped over. This
document will bore you if you already know cryptography or were
hoping for more rigor and math instruction.

Why is this important to know?

Advanced cryptography is not just about increasingly tricky ways to
send a secret message. Instead in large measure it is about ways to
establish trust between two people who have not met or for two people
to exchange messages in a way they can prove who they are to the
other person. That is, it is about the verification of trust and
proof of identity. So encryption in voting is not just about keeping
the ballot secret but being able to prove the receiver got your vote
or a voting machine being able to prove it cast your ballot correctly
in a situation where there could be hostile adversaries.

Some crypto tricks are slightly amazing and achieve counter intuitive
outcomes so it’s helpful to have seen that it is possible even if you
don’t understand how.

Concrete Example:

Is it possible for someone to correctly sum up a set of ballots
without ever actually know what was on the ballots or what numbers
they were adding?

That is, is it possible to take a set of numbers that have been
encrypted and combine them in a way that produces the encryption of
the sum. Now you might say, “well sure that’s easy. Just decrypt all
the numbers, add them up, and encrypt the sum”. But suppose we could
do this without actually knowing the decryption key? In this case we
would have a way to tabulate the total without ever looking at the
ballots. This could then be handed off to a third party who
decrypts it and learns the total, but without that third party ever
having seen any individual ballot.

This then brings up a whole host of issues. Can the man doing the
blind addition cheat? Can the people who cast their ballots
determine if their vote was in the final sum? While we won’t answer
those questions here we will introduce the concepts you will need to
know before in evaluating someone’s proposal to address those with
cryptographic voting.

Syllabus

        Notions in crypto useful in voting systems:

                Public Key encryption

                        Challenge and response

                        Signing

                Homomorphic encryption

                        Blind escrow

                Salting

                Shared secrets

                        Threshold encryption

                        Distributed shared key generation

Public Key encryption

For many reader’s this first section will be a gentle review of
concepts they are will acquainted with, but for maximal accessibility
to a larger readership I include it anyhow.

The canonical situation in Cryptography involves Alice wanting to
send Bob a message in a way that is encrypted. Traditionally one had
a code book shared by Alice and Bob. The weak point of this was two-
fold. First somehow Alice and Bob had to exchange that code book in
clear text, and possibly that exchange could be compromised. The
second aspect is counter intuitive: Alice and Bob would also know
each other’s code books, since, well they were the same--the encoding
and decoding were symmetric operations.

These days many people are familiar with the modern solution to this
dilemma: public key encryption. In public key encryption the
encoding process cannot be undone using the encoding-key. To decode
requires another key that cannot be computed from the encode key.
Thus for Alice and Bob to communicate, Bob openly announces his
encoding-key to the world. Alice uses the public key to encode a
message and sends it to Bob. Only Bob can decode the message,
because only Bob knows the decode-key.

Now the reality of this is that actually the decode-key can be found
from the encode-key in principle but by clever choices one can make
that calculation so difficult that the most powerful computers cannot
perform that computation in a million years. (Aside: this is one
reason people are afraid of quantum computing, which may render such
calculations feasible.)

Signing

Since Bob’s encryption key is public, anyone--not just Alice--could
encrypt a message and send it to Bob. They might even claim to be
Alice. How can Alice sign her message so that only she could have
sent it?

The solution is that Alice creates her own key pair, and publishes
the decrypt key to the world. When she wants to prove to anyone that
she sent a certain message she can just encrypt it with her secret
encode-key and send it out. Anyone can decrypt it with the public
decryption key but only Alice could have sent it since she alone
knows the encryption key.

Now Alice and Bob can carry on a private conversation. Alice first
encrypts her message using her secret encryption-key then she re-
encrypts that encrypted message with Bob’s public encryption-
encryption key. Bob then reverses the process, first decrypting with
his secret decryption key and then decrypting with Alice’s public
decryption key. Thus only Bob can decrypt the original message and
only Alice can have sent it. Moreover Alice cannot deny she was the
only one who could have “signed” the message with her encryption-key.

Notice that if Alice is a voting machine, it is possible for her to
securely encrypt messages without having the decryption key stored
anywhere in the machine where an attacker with access might find it.

Public Key Example: Challenge-Response

Suppose you want to log in to a remote computer. Commonly you send
your password to the remote computer over the wire. But how do you
know that remote computer was not another one impersonating the real
server?

One approach is for the real server to have a public encryption-key.
When the user tries to log in, the server picks a random word, called
a “challenge” and sends it to the user. The user takes this word and
appends his password to it, then encrypts the result with the public
key and sends this---the is called the “response”. The server can
now see if the response it gets is the correctly encrypted word-pair.

The neat thing is that the password is not sent. And the response
message sent will be different every time, as long as the challenge
is different, so an eavesdropper cannot try to use the response to
access the server at a later time.

(Aside: If both the server and user have public keys they can avoid
other types of attacks like a “man-in-the-middle” attack where an
attacker sits in the middle of the conversation relaying each sides
messages and listening in.)

Homomorphic Encryption

Okay, don’t panic. This is our first buzzword and I’m going to
explain it in plain technical english.

Homomorphic encryption is simply the name given to encryption methods
that have the magical property discussed in the example in the
introduction. Specifically if you have encrypted two numbers and you
“add” the encrypted forms then the result is the encrypted form of
the sum of the original two numbers (i.e. the sum of the unencrypted
numbers). If I were to write E(x) to mean the encryption of the
number “x” then when the encryption method has the special property
of “homomorphism” then it obeys the following rule for any pair of
numbers x and y:

E(x) + E(y) = E(x+y)

Now I have to make a small caveat here. When I said “add” I put it
in quotes because the way two encrypted messages get added is not
literally grade school addition. It’s some other mathematical
operation specific to the details of the encryption method that’s not
important that you know. The key thing to appreciate is that the
encrypted forms can be combined without decrypting them.

A silly example:

Suppose my super duper encryption method was that I took whatever
number you gave me and --now don’t tell anyone--- but I multiplied it
by 7. Now you can quickly see that the sum of any two “encrypted”
number is actually 7 times their sum as well. So this would be
called “homomorphic” albeit a trivial case.

Another silly example:

To get across the notion that sometimes what I mean by “addition” is
not actually standard addition but is still a well defined operation
consider another silly encryption method. Perhaps I could take the
original number x and encrypt it as 2 to the power of x: E(x) = 2x.
Now to combine two encrypted numbers, E(y) and E(y) I would multiply
them together to obtain the encrypted form of sum x+y.

There are many different homomorphic classes. One particular class
homomorphic encryption obeys the rule that “addition” of E(x) and E
(y) is encryption of the product of x and y. Another kind results in
the exlcusive-or of the bits of x and y. ( Aside: If you read the
voteHere documentation you will quickly run into the buzz-term “El
Gamal” which is the name of a particular class of homomorphic
encryption that supports produces the product of x and y (or in
exponential form, the sum))

Let’s look at an interesting application of the this.

Blind escrow probing

Suppose Alice encrypts some enormous string of bits--perhaps that is
her entire computer disk-- and escrows it with Bob. She does not
perfectly trust Bob, which is why she encrypted it. Now she wants to
retrieve some tiny portion of this big encrypted string. Let’s say
in fact she only wants to know the value of bit number 2047.

Now Bob could just send the whole data base for her to decrypt.
Instead were going to make this problem interesting by supposing that
Allice is working in a hostile environment, and does not trust the
computer she is working on enough to let it even temporarily hold her
entire database in unencrypted form. All she wants it to know is the
value of bit number 2047.

What she does is she encrypts a mask that is all zero’s except bit
2047 and sends the encrypted form of the mask to Bob. He “adds” this
to his stored encrypted value and sends back the result. We’ll
suppose that Alice had chosen a homomorphic encryption with the
property that the addition of any two encrypted values results in the
binary “AND” operation of the original numbers.

The result is that when she decrypts the returned value she only gets
the bits her mask allowed, which in this case is just bit 2047.
Additionally Bob cannot even tell what bit Alice asked for.

(Aside: I don’t actually know of a homomorphic encryption class that
supports “AND”. We can however accomplish the same task with XOR
with more effort. I supposed AND was available just to keep this
pedagogically simple)

Salting

A commonly arising problem in encryption is how to send the same
message twice without an eavesdropper knowing that the same message
was sent. In voting if the encryption of two identical ballots
produced the same encrypted value we could figure out how one person
voted if we knew how the other one did.

The traditional solution is simply to “salt” the message. This means
append some fixed length piece of variable gibberish to the front of
the message before encrypting it. Then identical message bodies
don’t have identical encrypted values.

I bring this up because the traditional salting method of appending
gibberish won’t always work for homomorphic encryption because, for
example, multiplying the messages may no longer make sense. However
I believe there are ways to achieve a salted message in homomorphic
encryption so that the same message will have variable encrypted forms.

Shared secrets

At the end of the day, we generally need to decrypt something so it
would seem that someone needs to know the description key. Is there
a way we could avoid having to trust one person? This gets to the
notion of handing our shares of secret so that no one person knows
the whole secret.

  Suppose Alice wants to make sure her relatives can open her jewel
safe after she dies. But she does not trust any one of them
individually. So what she does she gives one relative the first
number in the combination, the next relative gets the next number and
so on. This way they all have to conspire together as none can open
the safe alone. In our voting example, these might be adversarial
stake holders like the political parties.

In practice, this prescription of segmenting of the combination is a
naive approach since with a partial conspiracy it may reduce the
remaining numbers to a set too small to be secure. There are better
ways that are secure.

Threshold encryption

A special case of secret sharing is the case where one or more of the
secret sharer’s is uncooperative and won’t divulge the secret.
Perhaps the polonium sushi the killed Alice also killed one of the
secret sharers. There are cryptographic ways one can arrange a
shared secret among N people such that the secret can be recovered if
a quorum of any K sharers are present.

Distributed shared key generation

So far we’ve assumed that Alice knows the full key and thus can
partition it into shares for the secret sharers. In the case of
voting we may not want anyone, including Alice, to know the full
key. There are cryptographic ways to generate a key such that it is
shared right from the start and no one person knows the full key.

Trust

The example I gave in blind escrow probing was a tad contrived but it
illustrates the power of homomorphic encryption in environments one
does not totally trust. A process not too far removed from that
Blind Escrow probe is used in the voteHere system to allow the
receipt generator to prove to voter it did not cheat when it
generated what it claims is an encrypted from of the voters ballots.
The details are far too complex to layout here but approximately what
happens is that the voter is allowed to randomly select one entry
from the “ballot” and probe what is contained in the encrypted
receipt number. Since the machine can’t anticipate which entry will
be requested after it prints the receipt it can’t generate an
undetectable fake receipt. Note: I’ve not described this
sufficiently for you to assess whether that makes sense or not; I’m
just pointing out that the key to understanding voteHere is tied to
the notion of Blind Escrow Probing and homomorphic encryption.

Bugaboos

While I have pointed out there are many cryptographic solutions to
different sorts of problem, like learning the total without having to
decrypt the ballots to sum them, or ways to share secrets, or ways to
generate keys so on one knows the whole, it’s not perfectly clear to
me to what extent these solutions can be mixed and matched. For
example, it’s not generally possible for a given homomorphic
encryption scheme to permit more than one operation. e.g. I believe
there are no known ways to combine E(x) and E(y) for both
multiplication and addition of the message.

A related aspect of this is that if there is a way to decode a
message without the shares being combined so that the key is
revealed. There may well be but I don’t know how. If so then for
voting this also has to be done in a way such that none of the
sharers could cheat and alter the message. For example, a way that
would not work is if each person encrypted the message with their own
key in a serial fashion. ( This gives too much power to the last
person to decrypt because they can claim any message they wish was
present. ) I suspect there is a solution to this, but I’m personally
not sure how it works.

Another item I don’t know the answer to is if there are ways to
assure that shared keys are destroyed. If not then there is always a
latent chance that the real decrypt key could be discovered. This
might be bad for the secret ballot if it allowed receipts and thus
individual ballots to be tied to voters. I strongly suspect the
answer to this is no. If so the best one can do here in voting is
either administratively control this, say by bottlenecking a crucial
share in a trusted machine that then gets it;s memory authoritatively
wiped, Or by letting the voter himself be the only person who has
the full key set.
_______________________________________________
OVC-discuss mailing list
OVC-discuss@listman.sonic.net
http://lists.sonic.net/mailman/listinfo/ovc-discuss
==================================================================
= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
==================================================================
Received on Sun Dec 31 23:17:15 2006

This archive was generated by hypermail 2.1.8 : Sun Dec 31 2006 - 23:17:16 CST