Was YOUR vote counted (feat. homomorphic encryption) - Numberphile

Asked me to talk a little bit about the new innovations in voting systems. And so I'd like to tell you about end-to-end verifiable voting systems, which is the buzzword that academics are using to describe this. Now,Which means really that you can verify the whole flow of information, from your head, as to who you think you want to vote for, all the way through the casting of the vote and the tabulation and then the final tally, so that you can verify that every step of the way is going the way it should and that your vote counts the way you intended, that the final result is the accurate representation of everybody's votes. And right now, with many voting systems, you can have a certain amount of verifiability.

The lovely thing about paper ballots is that you can see that, you know, what you wrote down is what you intended. And so that's a very important property, very nice. But once you've cast the paper ballot, you're trusting the chain of custody of those paper ballots to make sure that the count is done right and that the ballots being counted are the right ones. Brady: "Talk to me about this selfie thing.

Some people like to take a photo of their ballot, don't they?" Yeah, it's a lot of fun, and I think it may increase voter participation to have a little more fun like that in the ballot booth and so on, too. The thing that is worrisome about it, though, from a security point of view, is that, you know, with a selfie of you casting your ballot, you can sell your ballot. And that's one of the things that we've learned the hard way over many many decades, is that you don't want to enable people to sell their ballots. So you shouldn't leave the voting booth with any kind of proof as to how you voted.

You shouldn't have a receipt saying you voted this way, you shouldn't have a copy of your ballot, you shouldn't have anything that proves how you voted. Because that can be worth, you know, 20 bucks to the, you know, to you, from the guy down the bar who wants to, you know, buy your vote. Or maybe coerce you. So, yeah, how can you possibly know that your vote was counted the way you wanted? This is a hard question, and it makes a fascinating research area.

And it turns out you can thread this needle with a bit of care and a bit of cryptography, a bit of mathematics. So how do you do this? So the idea would be that you get a receipt when you vote. And the receipt is not the plain text as to how you voted but an encryption of how you voted. So it's something that you can't sell down at the bar, because it's not something that's interpretable by somebody else.

Brady: "So what is it, like a number, or a barcode, or...?" It's a number or a barcode or something like that. It represents how you voted. So you get a receipt, and, the new thing here in these end-to-end verifiable systems is the copies of all the receipts get posted on the web. So say, Brady, and here Brady's receipt, and Ron, and here's Ron's receipt, and so on and so forth.

Everybody's name and their receipts get posted. Nobody can tell how anybody else voted. You can't sell your vote based on that posting. But it's all on the web, and it's all there for anybody look at.

And you can look at it, and you can see that, yep, they've got my receipt right, and that receipt is an encryption of my vote, right? So that's the key thing. You know your vote is in the pile, and you know your vote is in the pile the way you think it should be, because you have reason to believe, as I'll explain, that your encryption of your vote is actually correct. Brady: "Everyone's encryption looks different, though." Everybody's encryption looks different. So it's not a simple encryption in a deterministic way.

It's a good point. Yeah, so if everybody's voting for Alice, all the Alices don't look the same, and all the Bobs don't look the same. So there's a couple of subtleties here. One is, well, how do you verify the tally then? So somebody is announcing that Alice won.

And so, all these encrypted votes are primarily for Alice, and there's some for Bob, but there's more for Alice. That's the assertion that the election officials have made. How do they know? How do they convince anybody that that's right? And they'd like to convince everybody that that's right without showing the decryptions of everybody's vote. So they've got this pile of encrypted votes and an announced result, and you'd like to know,...

If you're an election official, you'd like to convince everybody that's the right result. So there's a number of ways of doing this, and there's quite a large literature on this. Here's a way that's pretty simple to describe. So you could use something called homomorphic encryption.

What does that mean? So it means that you can multiply ciphertext together and end up with them representing the sum of their plaintext. So, encryption of a one times an encryption of a two will give you an encryption of a three, right? So you end up adding the plaintext when you multiply the ciphertext. So this is cool. You can do lots of wonderful things with this.

And in particular, you can do the tally for the voting system. For example, if your vote is a vote for Alice, you might have an encryption of a one. And if your vote is a vote for Bob, you might have an encryption for a zero. And suppose Alice and Bob are the only two candidates.

So then, each ballot is either a one or a zero, and basically what you want to do is add them up. But they're ciphertexts, so you don't see the ones and the zeros. But you can use this homomorphic property, you can multiply all these ciphertexts together end up with a number which represents the sum of all of the plaintext ballots. And that sum is just the number of votes cast for Alice then, right? So the tally for Alice is the sum of all these things.

And Bob is just the number of votes minus the tally for Alice, of course. So if Alice has more than half, she wins. So there, you can multiply these ciphertexts together and get a ciphertext that's the ciphertext for the sum, and that ciphertext can be decrypted publicly in a way that everybody can see is proper. So you can see yes that is...

And everybody could also do this multiplication, So that is, they can check that that's the ciphertext to decrypt, and the election officials could decrypt that in a nice way and show that that's the proper decryption, so that we have the right tally for Alice. So that's one part of what you need to do then, is everybody can verify the tally from these encrypted things. And that's cool, right? So that's one part of it. The other part you want to deal with is the fact that you need to know that your ciphertext is really representing your vote, right? So you go into the voting booth, you're getting this receipt, and you want to know that that receipt really represents your vote.

So you vote for Alice, and you get this receipt which is a ciphertext, you can't decrypt that ciphertext. In fact, you shouldn't be able to decrypt that ciphertext, because then you could sell your vote, just like you could with a selfie, right? So you want to know that that ciphertext is really for, say, Alice, if you're voting for Alice. So, that's a little more subtle. Maybe this matchbox analogy is not a bad way to explain it.

How do you know that you've got a good match? You're going on a camping trip, you can, you're allowed to take only one match How do you know you've got a good match? Well, you could take a box out of the drawer, you can say well, maybe this is a box of good matches. And you try randomly sampling those matches, and, light, yeah, that one lights, that one lights. But you want to take with you a match you haven't tried yet. And so you, maybe the last match, you say, well, I haven't tried that match, but all the others in the box were good, and therefore I'm going to trust that this one is good.

You put that your pocket and take it camping. So you can do something like that with the encryption here. You can say, I walk into the voting booth, I get an encryption of  my first representation of the choice. I say Alice and I get encryption, then I want to see, is that really a good encryption? It's like seeing if it's a good match.

So I'll strike it, or I'll ask that to be decrypted, which the machine can do for me, since it encrypted it in the first place. So, so once I test it, I, once I see that, how it decrypts properly, unfortunately, I can't use that to vote with, because now I know how to, how it decrypts as well, and I can't post that, because I could sell my vote if I were to post that one. So that's a spoiled ballot, and, and we can't use that. Brady: "That gets taken off the tally." It's taken, it's not even posted, it's not in the tally, it's not used, it's not anywheres.

It's like I haven't voted at all, I'm just testing the voting machine. And I can do that as many times as I like, you know, two or three times, check out different decryptions of different things, and I can see the machine is reliably encrypting whatever I say I want to vote for. I can say I'm voting for Alice and test that, I can say I'm voting for Bob and I test that, and say I'm voting for Alice again. Maybe I don't test that one, and I say, okay we'll go with that, we'll post that on the web.

And then you've got confidence, just like with the matches, that that encryption was done properly. It doesn't need to be done by a lot of people, right? It just needs to be done enough so that you know machines aren't trying to cheat in any large-scale way. So those are the two parts of it. Getting encryptions that you can trust, even if you're not a computer, and getting a tally that you can verify, even though the inputs of the tally are encryptions.

And so this is a wonderful idea. It's evolved over the years with many different people putting parts of it together, but it means you can have a voting system, then, that's verifiable, all the way from who you want to vote for, that end of the process, through the casting of the ballot, through the posting of the ballots, through the tally and the announcement of the result. You can verify that the outcome is right. So, in the future, this might be the kind of voting system everybody will vote on.

But it's still in research stages a bit. It's under development. There are some jurisdictions that are starting to use it in practice, and we'll see how it goes. I'm optimistic.

...Alice, so put another Alice in, pick one out, and put it back, together with a copy of it. So now I've got six ballots. That's cool. So now I've drawn the bits.

Now it's four to two....