This post has been republished via RSS; it originally appeared at: Microsoft Research.
Senior Cryptographer Dr. Josh Benaloh
Episode 65, February 27, 2019
If you’ve ever wondered why, in the age of the internet, we still don’t hold our elections online, you need to spend more time with Dr. Josh Benaloh, Senior Cryptographer at Microsoft Research in Redmond. Josh knows a lot about elections, and even more about homomorphic encryption, the mathematical foundation behind the end-to-end verifiable election systems that can dramatically improve election integrity today and perhaps move us toward wide-scale online voting in the future.
Today, Dr. Benaloh gives us a brief but fascinating history of elections, explains how the trade-offs among privacy, security and verifiability make the relatively easy math of elections such a hard problem for the internet, and tells the story of how the University of Michigan fight song forced the cancellation of an internet voting pilot.
Related:
- Microsoft Research Podcast: View more podcasts on Microsoft.com
- iTunes: Subscribe and listen to new podcasts each week on iTunes
- Email: Subscribe and listen by email
- Android: Subscribe and listen on Android
- Spotify: Listen on Spotify
- RSS feed
- Microsoft Research Newsletter: Sign up to receive the latest news from Microsoft Research
Final Transcript
Josh Benaloh: Elections in the US are conducted mostly at the county level. There are over 4,000 counties in the US. There are over 8,000 separate election jurisdictions in the US. And the thought that a small county, somewhere, maybe in an important swing state, could have enough cyber security in place to withstand an attack from state-level attackers is just not realistic. Even though we can’t defend an election from being tampered with, we can institute good auditing. And one method of good auditing is this end-to-end verifiability that allows you, as a voter, to see whether your vote has been changed.
Host: You’re listening to the Microsoft Research Podcast, a show that brings you closer to the cutting-edge of technology research and the scientists behind it. I’m your host, Gretchen Huizinga.
Host: If you’ve ever wondered why, in the age of the internet, we still don’t hold our elections online, you need to spend more time with Dr. Josh Benaloh, Senior Cryptographer at Microsoft Research in Redmond. Josh knows a lot about elections, and even more about homomorphic encryption, the mathematical foundation behind the end-to-end verifiable election systems that can dramatically improve election integrity today, and perhaps move us toward wide-scale online voting in the future.
Today, Dr. Benaloh gives us a brief, but fascinating, history of elections, explains how the trade-offs among privacy, security and verifiability make the relatively easy math of elections such a hard problem for the internet, and tells the story of how the University of Michigan fight song forced the cancellation of an internet voting pilot. That and much more on this episode of the Microsoft Research Podcast.
(music plays)
Host: Josh Benaloh, welcome to the podcast.
Josh Benaloh: Thank you so much.
Host: Your bio begins by saying that you’re a Senior Cryptographer at Microsoft Research. What does a senior cryptographer do for a living? What gets you up in the morning?
Josh Benaloh: It varies quite a bit. I tend to have a foot in a few different places. I do research on elections in particularly, but cryptographic protocols more generally, multi-party protocols. I do policy work of various sorts and I spend a lot of my time doing internal consulting with Microsoft product groups.
Host: So, what do you do when you consult with a product group? Do you give them insights into why they’re not as safe as they think they are or…?
Josh Benaloh: Well, there are a few aspects to this. There’s a benefit to having one part of me in the research side and one part of me in the practitioner side, because I know what is being developed, I know what’s coming down the pike. So, I can talk to product groups about how they should do things. Cryptography is very subtle. It seems easy. There are some books out there that are very popular that people read and think, “Okay, I understand this all.” And when I go into somebody’s office and I see this on the shelf, I know I have a hard time ahead of me.
Host: What, Cryptography for Dummies, or…?
Josh Benaloh: There are books with titles like Applied Cryptography or Practical Cryptography that often oversimplify things. And just the order in which you do certain steps can make a critical difference. So, if I can go to a product team and they show me what they’re doing, and I can say, “No, if you do A before B, you’re going to have a problem, you’re going to regret it, do B before A…”
Host: So, do they seek you out, the product groups, as, “Help us out here, Josh?” Or do you go around and say, “Hey, you guys need this?”
Josh Benaloh: It’s almost always seeking out. But there are a lot of different ways in which I can work with product groups. For about the past, I think fourteen years, we’ve had something called a Crypto Board at Microsoft. And the Crypto Board is responsible for multiple tasks. One of them is setting corporate policy for how cryptography is used. Another is working with product groups to try to consult and help them.
Host: Well, let’s talk about this concept of security. We’re doing so much on the internet these days, and arguably we’re going to do more and more. And yet, the internet was not designed with security in mind. So, what are folks like you doing about that?
Josh Benaloh: Yeah, it’s certainly true that the internet was not designed for security. The internet was designed by a few people who knew each other very well and they were trying to set things up so that they could communicate with each other, and there was no sense, in the initial designs of the internet, of having to secure it against malicious forces. More recently, we’ve had to build security on top of the internet. If we had designed it initially with security at the base, it would have been a lot easier. Cryptography is an important tool in trying to secure it in a variety of ways: trying to keep data private, trying to make sure that the people you’re talking to are the people who you think you’re talking to, trying to maintain integrity of data, which is distinct from privacy of data, and basically “I should have access to the data that I’m entitled to have access to, and I should not have access to the data that I’m not entitled to.” In practice, although cryptography is an important tool there, and it’s very widely used now, most breaks of the internet are not about the cryptography. Most breaks are, maybe, the use of the cryptography or the implementation of the cryptography or things that even go around the cryptography. We’ve essentially got a very good front door, but the windows and the back door and other parts of the house that we’re trying to protect are more vulnerable.
Host: All right, we’re going to come back to that “what freaks me out at night” kind of thing… I was going to say, what keeps you up at night? That freaks me out at night. All right, Josh, let’s talk about securing the vote.
Josh Benaloh: OK!
Host: First, could you give us a little election history? I mean, I don’t know that people think about how we’re voting now and how it used to be and how it’s changed, but I think that would be a good level-set for launching into what you’re doing with election security now.
Josh Benaloh: Sure. Well, voting certainly goes back for millennia, and attempts at voting secretly go back for millennia. Public votes are difficult to tamper with in the sense of tampering with the votes themselves. But of course, when votes are public, then votes are coercible, and people can sell their votes or have their arms twisted into voting in particular ways. The history is not a pretty one. People have been stealing elections for centuries.
Host: As long as they’ve been voting.
Josh Benaloh: Yes.
Host: Vote for me!
Josh Benaloh: It’s interesting to note that most US Presidents were elected without the benefit of the secret ballot. The secret ballot in large elections actually was a technological innovation when it came about in the mid-19th Century. So, the way that people voted for president or many offices was typically, you would go to a public space and you would announce in some public way what your vote was, and that makes it easy to tell who’s voting and that only authorized people are voting, and that the votes are being counted properly, but it enables coercion and vote selling. The way that we vote in a poll site, in-person voting, was a technological advance in the 1850s. It’s typically called the Australian ballot, the process wherein people are voting in private within a public space so that the fact that they are voting privately is publicly monitored and enforced. So, this was an innovation at the time, and it took a while to move around the world. In the US, the number of US Presidents is different from the number of the US President, because Grover Cleveland was president number 22 and number 24. And that actually came about because of the lack of a secret ballot. So, in 1884, Grover Cleveland was elected without a secret ballot. In 1888, his competitor Benjamin Harrison defeated him, again, without a secret ballot, in an election that was utterly rife with vote selling, with coercion. And it was so bad at that time, that the US moved very quickly to secret ballots, and in the election of 1892, there was a rematch between Grover Cleveland and Benjamin Harrison, and with the benefit of the secret ballot, Grover Cleveland won again and became the 24th president.
(music plays)
Host: Okay, so we’ve got the secret ballot now. Since the mid-19th century, lots of stuff has happened, technologically, and the size of the country, and… So where are we now? Give us a lay of the land of what the unique problems are and what you’re doing, with technology, to work on these big problems.
Josh Benaloh: Well, if we look at elections broadly, they’re much harder than most other problems. The thing about banking or e-commerce or other fields is that, if something goes wrong, I know about it. I can have an opportunity to correct it. If my vote is changed, I don’t know it. There’s no way for me to discover that my vote has been altered, much less correct it. That’s of course within the context of the secret ballot. Of course, if we gave up on the secret ballot, then it would be very easy. We could have a public vote in which people cast their votes in person, by mail, over the internet, even by carrier pigeon. They just make their intentions known to the voting office, and the voting office publishes a list on a webpage somewhere, digitally signed for integrity purposes, so that everybody can look at the list and see, yup, my vote is there, it’s correct. I can see all the other people who are voting. I can check that they are legitimate voters, at least according to the registration lists. Of course, the accuracy of registration lists is another question, but that’s a little bit out of scope here, and that’s a public process.
Host: Right? Scope creep.
Josh Benaloh: Yes. But I can check that everybody else who’s listed there is supposedly a legitimate voter and that they have had an opportunity to check the list as well, because the list is public, and I can add up the votes on the list myself.
Host: But that’s not going to happen.
Josh Benaloh: Yes. So, it turns out, it’s possible to achieve all of these things with a secret ballot. And this is where cryptography comes in. With just a little bit of cryptographic sauce in just the right places, it’s not that hard to achieve the same things. And the basic trick is, we can still have a public list, but the public list is not of my vote, directly, but it’s of my encrypted vote, and everybody else’s encrypted votes. So, you can still check that you’re on the list. You can still check who else has voted. But now you need means for checking that the encrypted votes really do correspond to the tally. That’s all math, and cryptographically, we can do that. We can compute on encrypted data in such a way that we can process the data in encrypted form, turn it into an encrypted tally, and then provably decrypt that tally so that anybody can check and confirm the whole process and say, yep, this all looks good. We also need to provide tools that allow voters to be certain that the encrypted votes next to their names, which are opaque, really correspond to their selections. And that seems hard, but it turns out there are some pretty good ways of doing that that are quite effective, and we can make that happen as well. And I should try to be clear. I’m describing one process, but there’s this notion that’s called end-to-end verifiability, that enables this kind of election verification to take place.
Host: Talk a little bit about end-to-end verification. It’s a definition…
Josh Benaloh: Yes…
Host: …but there’s many ways to get to it.
Josh Benaloh: Exactly.
Host: Could you break that down?
Josh Benaloh: Sure. The definition of end-to-end verifiability is the properties that I just described. Voters should be able to check that their own votes have been properly recorded. And voters should be able to check that all of the recorded votes have been properly tallied. You might think that’s missing a little bit, that, well, but I can’t check that your vote has been properly recorded. But in some sense, that’s not really possible in any means without my knowing what your vote is.
Host: Right.
Josh Behaloh: So, this is really the most we can hope to have, and this is what we achieve in a public election. The challenge now is to achieve the same thing with a secret ballot election, and that’s where the cryptography comes in. And there turn out to be multiple ways of achieving these goals. Some very creative ways have come up for both parts, for the checking that votes have been recorded properly, and for the tallying. But the tallying tends to be highly cryptographic either by using homomorphic tallying methods, which compute on encrypted data and transform these individual encrypted votes into encrypted tallies, or there’s another approach that’s commonly used called a mix-net, which is basically a cryptographic shuffle of the ballots which has some benefits. It also has some privacy concerns, so there are trade-offs. But it’s good to have both techniques available.
Host: Well, and in fact, we’re going to have trade-offs no matter what. I mean, it’s just a matter of what is the sweet spot for what we’re willing to reveal versus what we want to keep private?
Josh Benaloh: Yes, and that manifests itself very distinctly in the election context, because you would think that it would be a good thing to have all the ballots be public in the end. But if the ballots are public, then it allows voters to sell their votes, once again, by various little tricks. You know, for instance, if I work for a small company, say, with a couple hundred employees, and the owner of the company is running for mayor, the owner can say, I want everybody in the company to vote for me as mayor, and there’s some minor office down at the bottom of the ballot, you know, dogcatcher type of office. Write in your own name there, and I will now look at all the public ballots that have been published and make sure that for each of you there is a ballot of that form, and if I don’t see a ballot with your name for dogcatcher and my name for mayor, don’t bother coming to work tomorrow.
Host: Interesting…
Josh Benaloh: And that is a sort of an obvious way of revealing things, but there are less obvious ways that can be used that are collectively called pattern voting, where a different pattern is assigned to each voter of the low-level contests. And that pattern had better appear. If a town council has ten different seats, then there are ten factorial ways of ordering the names, and the local controlling entities could just…
Host: Shall we say?
Josh Benaloh: Yes… could just go around and assign a different permutation to each voter and say, if this permutation doesn’t appear on a ballot, then whatever consequences might occur…
Host: Suddenly, Josh don’t feel so good.
Josh Benaloh: Exactly.
Host: You know, there’s another side of it too, in the 21st century, where, if your vote was made public, it wouldn’t just be the vote-buying thing, it would be the Twitter-mobbing afterwards if somebody decided they didn’t like how voted, they can ruin your life after the fact.
Josh Benaloh: Yeah.
Host: Well, I mean, these are all ruining-your-life-after-the-fact kind of things, but…
Josh Benaloh: Sure. There could be vote-shaming of various kinds.
Host: Vote-shaming. What a fascinating word.
Josh Benaloh: We’ve invented a new term.
Host: I love it.
(music plays)
Host: Okay, so. Cryptography in general being a way to get closer to that sweet spot… what’s the math and the theory behind this? Our listeners are pretty technical, and I’ve seen some of your slides on this. I didn’t understand any of the slides, but I saw them.
Josh Benaloh: That’s because you didn’t hear me talking about them. Once I explain them, they’re easy.
Host: I was… busy.
Josh Benaloh: So, homomorphic encryption has existed for over thirty years. When I was an undergraduate, I took a cryptography class from Ron Rivest at MIT. And Ron is great. And Ron does, in many of his classes, and I do this very often when I teach, whenever I can, is have students do projects at the end of the semester or quarter or whatever it is. And in this case, this was in the spring of 1981. There had just been an election in 1980. It was a 3-way election, and I was sort of naively thinking, maybe if we could computerize this somehow, we could have ways that would allow people to express their preferences in some way. I didn’t know at the time that it doesn’t really work very well.
Host: No.
Josh Benaloh: There’s Arrow’s Theorem and related theorems that say that there’s nothing good that we can do with preference lists. But I was thinking about this, and I decided I would do my project on elections. And Ron handed me a paper that he’d written with a few colleagues, Adleman and Dertouzos, called Privacy Homomorphisms, which talked about how you can manipulate data that had been, not encrypted, but protected in some way. And…
Host: Mathematically.
Josh Benaloh: Yes. And I had been a math major, and I jumped on the word homomorphism. I knew what that meant. You know, it meant that you can apply an operation that preserves the structure of something. So, I thought yes, maybe I can do that in this context. And I did a few sort of weak things along that line for my project. None of it really worked, but these were interesting ideas. Years later, when I found myself in a doctoral program and looking at thesis topics, I had much better tools available to me, I knew a lot more, and the field had grown. And I realized that I could actually do something that went much further to solving that problem and started using homomorphic encryption as a way of enabling an election that really could be verified. Elections really come down to doing addition. It’s just ones and zeros, who you voted for, and the tallies are just adding them up, and there’s really not much more than that. So, the trick is basically, if we have an additively homomorphic function, then we can take encrypted votes and apply this additive homomorphism and we get an encryption of the tally. And that’s pretty much all there is to it. There’s a whole thesis in that. Well, there was a little bit more in the thesis, but you know that was the core idea.
Host: That’s awesome.
Josh Benaloh: And it turns out, could be done very efficiently, so I invented a little additive homomorphic encryption system of my own. The general form of RSA, at least typically, used a large exponent. RSA in its practical usage today typically uses a small exponent, and my encryption system used two small exponentiations, which is a lot more efficient than one large one. So, it was an efficient way of doing things. People have been interested in homomorphic encryption for years, saying, well, there are additive homomorphic encryption systems, there are multiplicative homomorphic encryption systems. I wonder if we could do something that would do both at the same time. And it turns out that if you can do addition and multiplication together, then you can do everything. You can do any computation because you can break computations down into addition and multiplication. It’s really the equivalent of ands and ors. But people thought for many, many years that it would be nice, but there are good reasons to think that this just can’t be done. And then about ten years ago, it turned out it could be done. It was Craig Gentry that found a way to do this that was wildly inefficient. It slowed things down by I think about twenty-five orders of magnitude. It’s about 10 to the 25th slower than doing the computation directly.
Host: That’s ridiculous.
Josh Benaloh: Yes, that’s, of course, ridiculous. You can’t do the simplest computation with that. And there’s been a lot of research since then on bringing that down. And now it’s down to about ten orders of magnitude for general computation, which is still very painful, but there are cases where it’s far more efficient, and this is a tool that allows for computation on data in encrypted form. So, once we have that, then we really enable very powerful cloud data services, and we can do some of that today. We can’t do all of it, because the general computation is still nowhere close to efficient enough. The reason I want to distinguish it is I want to make clear that even though we’re using homomorphic encryption for our elections, we’re using what’s now come to be called simple homomorphic encryption, which is very efficient.
Host: We’ve heard the pronouncements: people aren’t going to put public elections on the internet until it is end-to-end verifiable. And we can’t do that yet, so we’re not doing this yet, right?
Josh Benaloh: Well, I would say a little bit more.
Host: That’s what I want you to do.
Josh Benaloh: Okay, then I will.
Host: Isn’t this speculative technology now? Where’s it being used? It is being used?
Josh Benaloh: No, it is not speculative. Yes, it is being used. So, end-to-end verifiable election systems do exist and have been fielded in a variety of contexts. They tend to be in small, localized contexts. There was an end-to-end verifiable system used in Tacoma Park, Maryland, for a couple of public elections. A few hundred voters. But they used a very nice end-to-end verifiable system there called Scantegrity. And the voters liked it very much. But it was a lot of work, and after doing elections in, I believe it was 2009 and 2011, Tacoma Park was very happy to continue it, but the researchers, who had put a lot of time and effort into it, were saying at that point, find a way to do it yourself, please. And of course, there was nobody to pick it up, so it hasn’t been done so much since.
Host: OK.
Josh Benaloh: There’s an internet-based end-to-end verifiable system called Helios that’s used in a variety of places. It’s used commonly by professional societies, like the ACM uses this. The IACR, the International Association for Cryptologic Research and many professional…
Host: Of course they do…
Josh Benaloh: Well, actually, it was very hard to bring this in, because cryptographers are very suspicious people.
Host: That’s funny right there.
Josh Benaloh: So, it was quite a challenge to move the community to this. What the community had been doing was mailing out paper ballots in double envelopes and such. And many people thought we should continue doing that, even though it costs tens of thousands of dollars.
Host: You don’t even eat your own dog food.
Josh Benaloh: Well, we weren’t. But eventually, the economics, together with the import of the election moved us to, you know, we can really do this. Many of our offices, there’s only one candidate. There aren’t a lot of people spending a lot of money trying to steal this election. It’s okay. I would not recommend this for public elections. Not today. End-to-end verifiability is a very valuable tool, and it mitigates a lot of the concerns of internet voting. I was a part of a US Vote Foundation study that was published three years ago that looked at using end-to-end verifiability for internet voting. And some of the conclusions were that it’s absolutely unconscionable to do internet voting without end-to-end verifiability. It mitigates many of the problems in a way that nothing else can, and without it, it’s just so vulnerable you shouldn’t even touch it. However, there are still problems even with end-to-end verifiability that have not been adequately mitigated, and therefore, we should not be doing that today, even with end-to-end verifiability. What the report recommends it we should be using end-to-end verifiability in in-person elections, in poll sites, in traditional ways first, getting more experience with it before we contemplate the next step of moving it into the internet realm. We should definitely be doing things carefully. Anytime we try something new, it’s good to put it out for the public to have dry runs and trials. There was an internet voting system that was built for Washington, D.C. a few years ago, and it was actually built very well, although it wasn’t end-to-end verifiable. But it was open source. It did many of the right things. The code was actually quite good. And they did the right thing of putting it out for a public challenge in a mock election before it was actually used. And a professor at the University of Michigan, Alex Halderman, got a few students to look at this during the trial, and they eviscerated the system. They were watching the internal cameras in the voting center, watching the workers look at what was going on. They were able to compromise all of the votes, change all the votes to anything they wanted. They changed the actual voting mechanism and put the University of Michigan fight song at the end of the voting process. The first that the election officials in D.C. got wind of what was going on was when they started getting complaints from voters saying, “I really like this internet voting process, but that music at the end is kind of annoying.” And that’s when they discovered that this trial had been hacked, and they did cancel the project.
Host: I always ask my guests on this podcast what keeps you up at night. I want this end-to-end verifiability to be there. It’s not, but what ought we to be thinking as we now know these things, I think that were made clearer? Maybe we had our head in the sand a little bit?
Josh Benaloh: There’s a lot that we can do. So, I was an author of a report that was just released in September. It was released by the National Academy of Science, Engineering and Medicine, called Securing the Vote: Protecting American Democracy. There’s a lot of good stuff in the report. A few highlights I can give now. Feel free to download it and read it yourself. I think it’s a very readable report. But some of the highlights include that, of course, the 2016 election was infiltrated, but we saw no evidence of actual tampering with votes themselves. Even though we know now that it’s very possible, we didn’t see any evidence of that. In fact, I was on a phone call with election officials from all over the country two days after the election and the consensus was that as far as the casting and counting of votes go, this was the cleanest election that people had seen in a long time. There were certainly some incidents, but they were relatively small compared to what is typically seen in an election. So, we know there are vulnerabilities, and they really do need to be addressed. So, there are a few steps that can be taken. Certainly, we can apply best practices, things that are not being done today to secure registration lists, to better secure the actual voting equipment. And there are things that we can do in terms of basic, general security practices that most industry does today. The problem we have is that it’s an asymmetric battle. Elections in the US are conducted mostly at the county level. There are over 4,000 counties in the US. There are over 8,000 separate election jurisdictions in the US. And the thought that a small county, somewhere, maybe in an important swing state, could have enough cyber security in place to withstand an attack from state-level attackers is just not realistic. Even though we can’t defend an election from being tampered with, we can institute good auditing. And one method of good auditing is this end-to-end verifiability that allows you, as a voter, to see whether your vote has been changed. We have other methods of auditing, and there are better methods of administrative auditing that can be used, but end-to-end verifiability offers a public audit, allows voters, themselves, to become part of the process and to check for themselves, and candidates to check for themselves, and interest groups or news media or others to do the checks. So, that’s something that I very much hope that we’ll be moving towards.
Host: So, in conclusion, we need more research? Classic last line of a dissertation…
Josh Benaloh: I’m actually reluctant to say that. Yes, it’s true, but…. And the reason I want to say but is that end-to-end verifiability is ready to go now. And many people are putting it off and saying, well, that sounds good. You should do more research on it and wait. And sure, there are ways that we could improve it. Better usability studies would be helpful. There’s a lot of opportunity for good usability research. There are some opportunities for other areas, but usability applies in traditional elections as well, and we’re not saying, well, we haven’t done enough usability studies, so we can’t have an election.
Host: Right!
Josh Benaloh: Let’s do that research, but that doesn’t mean we should wait on deploying end-to-end verifiability and the best tools that we have now. And then also, let’s do some research on how to make them better.
Host: Josh Benaloh, thank you for coming on the podcast. It’s been delightful having you as a guest.
Josh Benaloh: Thank you so much, Gretchen. This has been really a lot of fun.
(music plays)
To learn more about Dr. Josh Benaloh and how cryptographers are working to secure the vote, visit Microsoft.com/research.
The post Securing the vote with Dr. Josh Benaloh appeared first on Microsoft Research.