A few extra details on the WIRED article about STAR-Vote
WIRED recently ran a great article by Ben Wofford and a companion podcast about STAR-Vote, an effort that began in Austin, Texas to build a new voting machine using state-of-the-art encryption technologies, and how that ultimately led to Microsoft’s ElectionGuard project. This blog post is meant to fill in a few of the details and share credit with a long list of people without whom it might never have happened.
The WIRED article goes into a lot of detail about the skepticism that I and many other technologists had prior to Dana DeBeauvoir’s talk at EVT/WOTE in 2011. To give you some kind of a view into that skepticism, you may appreciate a five minute “rump” talk I did in 2010, in the style of Stephen Colbert’s “The Wørd” television rants. When Dana DeBeauvoir called me to help her, my life really changed.
The STAR-Vote journal article that resulted from our initial meeting in 2012 is online and free for anybody to read; see also, a video of my 2013 presentation. If you look at the credits, you’ll see a variety of staffers from the Travis County Clerk’s office (alphabetically: Susan Bell, Dana DeBeauvoir, Gail Fisher, Julian Montoya, Michelle Parker, and Michael Winn), who were absolutely instrumental in shaping the system. In a very real sense, they were the “customer” of the design and we technologists were working to engineer a system that would meet the requirements they set down. For the technologists who made STAR-Vote happen, they fall into several camps: Mike Byrne and Phil Kortum are usability experts; Neal McBurnett and Phil Stark are experts in statistical auditing of elections; Josh Benaloh and Olivier Pereira are cryptographers with direct expertise in voting applications; and last but not least, Bryce Eakin was a former Rice student, who had taken a class about voting from Mike, myself, and Bob Stein, and had contacted me asking if there was some way he could help out, and help out he certainly did.
A number of other researchers joined into the effort after our initial paper came out. This includes Ron Rivest (the “R” in RSA) and Claudia Acemyan (a graduate student and later a post-doc working with Mike, Phil, and I at Rice). Also, I have to give a shout-out to Matt Bernhard and Matt Kindy, then Rice undergrads, who were furiously hacking on our old VoteBox codebase, while the STAR-Vote team was meeting in Austin, to make it into a running demonstration prototype of STAR-Vote. Matt went on to earn a PhD with J. Alex Halderman at Michigan and is now working at VotingWorks. (You can see Halderman, as a then-Princeton graduate student, in the 2007 group photo below. Halderman and I share Ed Felten as our Princeton PhD advisor.)
A few other relevant details: the 2007 meeting where Josh convinced me that homomorphic cryptography was the way to go was at Schloss Dagstuhl, which hosts academic computer science workshops. If you look at the group photo, below, I’m standing roughly in the center, next to David Chaum, in the orange-ish aloha shirt, who is a legendary cryptographer. Chaum-Pedersen proofs (see also, lecture notes from Canetti and Rivest) are essential to STAR-Vote, ElectionGuard, and virtually every other electronic voting scheme. (Want to know more about the math? See the “sidebar” below.)
The size of this photo tells you something of the size of the larger academic community around secure voting systems and cryptography. I was at this Dagstuhl to present some results from the California Top to Bottom Review, led by Dave Wagner and Matt Bishop; I was on the team that analyzed the source code to the Hart InterCivic eSlate — the very same machine currently used in Harris County (Houston, TX) and which Dana DeBeauvoir used up until recently in Travis County (Austin). Shout out to Srinivas Inguva (then a Stanford masters student), Eric Rescorla (now Firefox’s CTO), and Hovav Shacham (then a Stanford graduate student, now a professor at UT Austin). That work was intense.
I also want to acknowledge Brent Waters (then a staff cryptographer at SRI, now a professor at UT Austin) and Ben Adida (then a graduate student of Ron Rivest, now the director of VotingWorks), who walked me through all the ElGamal mathematics that we then implemented in VoteBox. VoteBox, itself, was primarily built by my then-graduate student Dan Sandler (now, one of the leaders of Google’s Android efforts) and then-Rice undergraduate Kyle Derr. A large number of future Rice undergrads would later use VoteBox as the basis for class projects and independent work. Today, you wouldn’t want to use VoteBox or the STAR-Vote prototype derivatives of it. You’d instead want to use ElectionGuard, which integrates with a fork of the VotingWorks BMD, which is in turn built on the beautiful and simple Anywhere Ballot design.
The WIRED article talks in detail about ElectionGuard, conceived by Josh Benaloh inside Microsoft Research. The initial version of ElectionGuard was built under contract at Galois Research, led by Joey Dodds, Joe Kiniry, and Dan Zimmerman. I spent a month with Galois in the summer of 2019, but I was helping with their other voting machine project, sponsored by DARPA. More recently, development on ElectionGuard has continued under contract at InfernoRed, led by Matt Wilhelm and Keith Fung. I also made a number of contributions to this code.
This calendar year, I’m on sabbatical from Rice and working with VotingWorks (founded by Ben Adida and Matt Pasternack), applying ElectionGuard to the world of risk-limiting audits. Informally, we want to compare the paper ballots, at random, to the electronic versions, to make sure they match up, or at least that the error rate is small enough that we can have measurable confidence that we have the correct winner of the election. What I’m doing is implementing a 2019 design by Josh Benaloh, Phil Stark, and Vanessa Teague called VAULT. (Vanessa was also at that 2007 Dagstuhl meeting. It’s a small world.) The rough idea is that it’s bad for election officials to just publish all the individual ballots in an election, since that might enable some forms of bribery or coercion, but we want to be able to provide some transparency into the electronic votes stored on the computer. We’re using the same “end to end” homomorphic cryptography to make it work.
My implementation, still in progress, builds on the ElectionGuard Python library, which provides all the cryptographic primitives. Fun fact: encrypting a typical voter’s ballot and generating all the Chaum-Pedersen proofs for it takes multiple seconds on a modern computer. When you have a voting machine doing the work while a voter is standing there, this isn’t a big deal, since the computer can do the work in the background, selection by selection. The voter will never notice. But if you’ve got a million ballot records that just came out of a high-speed paper scanner, and you want to encrypt those ballots in maybe an hour or two, then post all the ciphertexts online? No single, modern computer is anywhere close to fast enough. Luckily, each ballot can be encrypted independently, so we can temporarily harness thousands of computers from cloud providers like Microsoft Azure or Amazon EC2. That’s the code I’m writing today.
Sidebar: what’s the big deal about e2e cryptography in elections?
With conventional cryptography, you encrypt a number with a secret key and what you get out is a ciphertext that looks like random bits. Furthermore, there’s nothing you can do with that ciphertext except eventually decrypting it. Fundamentally, what makes “e2e” cryptography interesting are the properties that it provides for us to operate on encrypted numbers. In particular:
- We can “add” these encrypted numbers together, without first decrypting them, and get their encrypted sum. To explain this, imagine you have a⁵ and a⁷ and you want to derive a¹². All you have to do is multiply a⁵ × a⁷ = a⁵⁺⁷ = a¹² ; you multiply the numbers and the exponents add. That’s an “additive homomorphism”. Similar homomorphisms exist in ElGamal and many other encryption techniques. Some newer cryptosystems are fully homomorphic, meaning you can do general-purpose computing on the encryptions rather than just addition, but we’re not using those for voting.
- You can “re-encrypt” by “adding zero”. The trick here is that there are many different ways to encrypt a given number. This is important, because we’re mostly just encrypting zeros and ones, and we want all the encryptions to look different from one another. (Cryptographers use the term “nondeterminism” to describe this property.) So if you’ve got all these different encrypted zeros and you can “add” them, what happens is that you get out new versions of what you had before, all without needing to being able to decrypt. (ElGamal is a public-key cryptosystem, so we can put the public key in every voting machine, while carefully controlling the private decryption key.) Why might you want to “re-encrypt” a number that you cannot yourself decrypt? That gets into a whole family of techniques to shuffle/reorder ballots called mix-nets. These are useful in voting applications, digital currency, and all sorts of other things.
- We can “prove” that a given encrypted number is either zero or one but, and here’s the crazy part, without revealing anything else. That’s what the Chaum-Pedersen proof does for us. Chaum-Pedersen proofs show up all over the place in electronic voting, because they allow any election observer to see all the encrypted ballots and verify that each and every one of them is well-formed (i.e., there’s no over-voting; we can prove things like, for a given contest, a voter has made at most one selection).
Once you’ve got these primitives, you’re pretty much ready to build an e2e voting system. The only missing piece is how you, a human voter standing in front of a machine, are going to trust the machine itself, which is doing all this fancy math on your behalf. Josh Benaloh has come up with a series of solutions to this problem which we now call “Benaloh challenges”. The idea is that a voting machine doesn’t know, for any given voter, if that’s a “real” voter or whether it’s an “auditor”. An auditor uses the machine in exactly the same way as a real voter does, right up to the point where the machine computes the encrypted ballot and commits it. For STAR-Vote and ElectionGuard, that would be when the paper ballot is printed out. For other voting systems it could be different. The magic of a commitment is that the machine can’t take it back. Instead, the regular voter will be depositing that ballot while the auditor will demand that this particular vote be decrypted.
That decryption is realized in a polling place by the auditor bringing the paper ballot to the front desk and having it treated as a “spoiled ballot”. At the end of the election, all the spoiled ballots are decrypted and publicly posted. The auditors will have their original paper ballots in hand, and will compare every such ballot to the public decryptions. If even one is in error, then you’ve caught the machines cheating! The property we’re ultimately verifying here is that our digital ballots are cast as intended by the voter.
Every voter also goes home with a “receipt” consisting of the cryptographic hash of their encrypted vote. That can be used to find their ballot on a public web site of some kind, allowing the voter to confirm that their vote is indeed part of the public tally. Anybody, anywhere, can download all of the encrypted ballots in a given election and “add” them together. The election officials will decrypt the election totals and provide a proof that they did this correctly. (Chaum-Pedersen again!) Ultimately, we’re proving that every vote was counted as cast. No votes missing. No votes tampered.
But what if the voting machines had malware on them and generated bogus encrypted votes? The auditors would catch this behavior with a very high probability.
Then what? The paper ballots, human readable and (for the most part) verified by the humans who cast their ballots, are still in the ballot boxes, so we can scan them and tabulate them without the fancy cryptography, if need be.
Could humans be tricked? Would they notice if something went wrong? This turns out to be an area with a long academic history. We built an “evil” voting machine that tried to trick voters back in 2006. More recent studies have looked at this with paper ballots from ballot marking devices (Bernhard et al. 2020, Kortum et al. 2020). The punchline seems to be that when voters try to verify a ballot, they will likely notice any errors, and it helps to give them a spoken nudge to make the attempt.
