From: Charlie Strauss <cems_at_browndogs_dot_org>

Date: Sat Dec 16 2006 - 01:06:00 CST

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
*