Verifiable Open Source Elections using Homomorphic Encryption & Zero-Knowledge Proofs

um I also work on uh pizza dough during the pandemic we threw the world's largest pizza party it's been about 300 000 uh feeding people around the world on May 22nd for Bitcoin Pizza day uh and then I also work on uh the notorious frogs which is a uh a blockchain based uh fantasy RPG game 1930s gangster frogs in a fantasy world we got aliens we got Wizards and we got amphibians it's fun all right so what is election guard election guard is an open source software development kit that makes voting more secure transparent and accessible right um this is a project that was started by uh a man named Josh benello at Microsoft probably 12 12 years ago something like that and um in the past like four five six years there's been a lot of traction around this topic and it's led to um you know a lot of extra development so everything that we have is MIT licensed uh we're developing an encryption library that is complete that's based on C plus uh we've got a waza module that's in the works we've got a python reference implementation and then the community has built a few other implementations one in kotlin uh there's a typescript implementation that exists now as well and uh yeah most of it's built around a.net Stack because if you know Microsoft and so who's building this uh you know Microsoft's democracy forward program I don't know if you've heard of them but they're a small startup uh I've got a link here for the the PHD thesis that started all this thing if you guys are interested in Reading any of that but we're going to walk through the protocol here in a few minutes uh and then Inferno red is uh the software development partner and then we have a few different partners for voting systems manufacturers um heart inner Civic uh it's based in Texas and they've got uh voting machines that they um sell into communities here in the US uh enhanced voting is uh focused on building online experiences that are accessible for people and then uh we've got voting works as well uh who's building machines that are uh using consumer off-the-shelf Hardware right to keep to make it so that you don't have to spend hundreds of thousands of dollars on all these different machines uh miter is building a a verifier and we'll talk about verifiers in a little bit uh and then you know we've got a center for civic design Partners universities uh you know kind of all over the country who have contributed in some way to this thing okay so how does it work election book guard is uh basically divided into three steps there's the election set up which is a trusted setup process there's uh the actual encryption of the votes uh and then there's the tallying and decryption phase so in this first phase um this might look familiar to some people uh we use uh Shamir secret sharing mechanism here in order to pass information around uh the encryption methodology that we're using is algomall so um you know each uh we call these guys Guardians right they're just public private key Pairs and they um you know share parts of their private key material around so we can do uh Quorum based encryption so that way no uh no individual is able to decrypt any other individual specific ballot right so the ballot encryption phase uh and this is what the C plus plus library is built on and it's designed specifically to run on low-powered Hardware like scanners um you know and other machines like that uh like I said we're using alcohol to encrypt each one of these ballots and then we have a Sean Peterson proof that proves uh that the encrypted value is either a zero or One A true or false yes you voted yes or no you voted no um then for each contest in a uh on a ballot say like school board for example choose three out of five we have a a range proof that is responsible for making sure that the sum of all of those values from each of the selections does not exceed the maximum right so all of this happens very quickly um we never write out the um uh the plain text ballots out to disk we worked entirely in an encrypted space because we have these homomorphic properties of alcohol so once the machine has encrypted that value from that point on if uh anything else in the system ever released it's all going to become public anyway at the end of the election all right so this is um where things start to get a little bit interesting so what we end up doing is we create a confirmation code for voters right so once we do the encryption uh there's a basically a hash value that includes uh the entire ballot a representation of the schema of the ballot and some other information uh like you know device ID things like that that are rolled up into this tracking code verification code confirmation code whatever you want to call it and at the end of the election when the tally is completed and the decrypted value of the tally is published the uh a voter can go to a website and they can go and they can check and verify that their vote was actually included in the election record right so what's really important here though is that uh this confirmation code gets generated at the point of encryption um prior to the decision of the voter to cast or spoil um and that uh and you know spoiling a ballot is uh we're going to talk about that in a second um but that separation between the encryption happening and then the decision to um what you're going to do with that as a voter is what makes this whole system works and it creates this challenge mechanism that allows voters to be able to challenge the system and make sure that it's behaving correctly so that's where the the challenge ballots come in also known as uh spoiled ballots and uh what we do here is uh um in most jurisdictions where whenever you go vote if you make a mistake on a ballot uh you typically can take that back up to the table say hey I made a mistake I'm not gonna I don't want to use this one and it'll give you a brand new ballot and then you can go and you can cast that so um we actually piggyback on that process which is a legal process um and those spoiled ballots actually become part of the election record and so what we do is uh we actually do decrypt the spoiled ballots the ballots that are not cast and are not included in the election and uh what this means is you as a voter can go in and say fill in all the first selection get your confirmation code say spoil it challenge it go back up to the table depending on what sort of process or system is being used uh and then you go back through and you vote for real and then now you have two tracking codes and uh when the election results are published since we published both the plain text and the ciphertext values for the spoiled ballots uh you can prove that the encryption was done correctly because if the machine had misbehaved and tried to switch one of your votes you would be able to know and since the decision to or the decision of the voter to do that is separated from the actual encryption process um the machine has no way to know which Choice you're going to make and so it has to behave correctly so this right here's um an example of of one system uh this is a you know an online tablet-based system um this whole system is built to be very uh generic and generalized and be a general voting protocol that can be used for um you know for a wide variety of different use cases and uh we've been targeting primarily using um uh Precinct scan cases so like when you you have a bubble sheet and you fill that in and there's a paper record you scan that into a machine or tablet base and uh most of the the actual accumulation of the tally and the creation of the tally which we're going to get into here next is done at that Precinct level it's run by actual election officials uh and it's not actually run by us at all so the tally in the decryption process is uh homomorphic right so what we end up doing is we uh we accumulate all of the cast ballots all the selections on each one of the ballots together and then when the decryption happens uh we're only decrypting that accumulated value so we never actually decrypt an individual cast ballot so in this way with all of the proofs that we have in place the Sean Peterson proves and uh these homomorphic properties of uh of alcohol we don't we were able to protect voters privacy because we're never actually going to decrypt one of the ballots themselves so and if you remember we do decrypt the spoiled balance right so that part um is done and that's that's managed by the software uh and going back to the the key ceremony or The Trusted setup process that we have uh in the social layer is where you enforce this I mean obviously a lot of the people who are are fulfilling this role of Guardians typically their election officials or non-technical but that whole process uh protects against any sort of collusion so if somebody did want to try to decrypt an individual ballot um they would all have to agree to it and depending on where you are what jurisdiction um what type of voting is actually happening that may or may not be a concern but it's uh it's managing the social layer and not actually in the protocol all right so what about blockchain for our use cases um it's not really necessary um we're we're working primarily with uh local governments and jurisdictions where you have a lot of um difficulty getting funding for I.T systems and things like that so um we're not really using it but it's uh the protocol is data layer agnostic the like I said the most important part of this is that you separate the decision to cast or spoil or the challenge process from the actual encryption so you can use this in a blockchain system um we are aware of a couple of teams that are using blockchain for for this type of stuff uh but for our target audience which is you know County clerks here in the United States who are responsible for actually implementing elections um they just they don't need it they don't understand um the uh there's no real value of having a decentralized distributed database come into play and of course like if you've got a public blockchain network ordering your votes in some cases can of course be a privacy risk uh you know if I know exactly when a vote was submitted and I can read that and I see you say on the news as like a newscaster is there I can tell which of those votes was yours even though it's encrypted there are some certain things that um Can Happen around that so um of course there's Technical Solutions to these things and there's ways around that um so if you guys uh end up working with this and you find a good use case before with blockchain you build something we would love to hear about it okay so I promised uh in the initial um in the brief here that I would talk a little bit about some of the lessons that we've learned uh about how to talk about he and zero knowledge proofs and these things with voters in actual elections so um probably most of this probably is not going to come as a surprise to anyone but um building confidence using simple terms uh you know you don't want to insult people's intelligence but they're just they're not going to understand the math they're not going to understand the jargon the terminology um those things simple things so like focusing on things that are similar to the way that they're doing it now uh and this is one of the reasons that we've targeted Precinct scan as a use case it's like well you're using the same machines that you're using before it's just better now so there's no difference um in a couple of cases in the real world use cases we've actually given people the opportunity to opt out and had machines where that are not using the encryption machines that are using the encryption and in those cases the uh the paper ballot ends up being the system of record and um you would be surprised a lot of people really want to try it out they want to see it work there's been a lot of good feedback around it um if you have to say homomorphic encryption you have already lost uh they like people's eyes are just going to glaze over they're not going to understand it they're going to get confused and then when people start to get confused um they're going to say no so um good great ux here is a big difference that's really what uh you know tends to give people confidence and uh making things easy for them uh give them a simple path forward like when you go and you check your ballot at the very end of the election um and verify it you say my vote was counted but then you can have like a little um you know sub thing where you can go and actually check the proofs and check the math uh if for people who are interested in doing that or people who want to right and so part of our model here too has been to get a number of different uh third-party vendors to create verifiers for these systems so that that way when the election records are published they can run the entire data set through those and get signed off from say like the AP or you know any other organization in order to build trust in uh in the data set all right so we got a few real world examples um this was used in a primary in Fulton Wisconsin in the spring of 2020. um absolutely crazy to be doing that right before the pandemic happened and uh you know at a time in in this country when everyone was talking about voting it was very very interesting uh it was probably about four or 500 ballots that ran through that process um you know it was very very interesting to see the way that people responded uh the U.S uh house Democratic caucus used a version of this technology to do remote voting to elect their leadership uh in the fall of 2020.

um there was a general election in Preston Idaho in the fall of 2022 and then in the over the course of the next couple of years we're still trying to work find um you know more opportunities to to work this in uh you know other voting systems manufacturers For Better or Worse the the way that we've set up this Consortium of people is that you know Microsoft and Inferno red are primarily leading the software development and the integration but really driving this from Partners you know for-profit companies who are selling machines uh you know Watchdog organizations who want to be the ones who do the verification or build the the voting websites for people um and that sort of thing so it really um it's a bit of a tribe I think it's probably a good way to put it and uh you know we're always on the lookout for new opportunities to to um to get this thing out there and get people using it all right so um if you're interested in helping uh us you know you can join the discussion we run everything open open source we work in public uh we just open sourced uh the latest version of our encryption Library a couple of days ago uh you know our our backlog is open we run everything on GitHub discussions there's monthly Community calls um you know so yeah come and check it out hang out see what's going on uh also you know if you're interested in this sort of thing anytime that you're talking to people and this type of thing comes up you know we have a solution in place that works for how to um to test and assert that the voting machines are behaving correctly so um just getting people in your local community um you know if you sit on say like school board or anything like that I'm just kind of talking about it can be really really helpful and then of course uh the discovery of new use cases right we're focused very much on real world in-person secret ballot elections um but this protocol can be used as a you know a blinding factor for any sort of voting that requires Secret ballot so um we're very interested to see any new ways that people want to use the software and of course you can build something cool right if you're a software engineer uh the third party verifiers any language you want the the specification is open source as well there are uh examples in Python rust c-sharp C plus plus uh typescript I think we already have a whole bunch of them but the more we can get the better because that you know there could be a bug in one you know you never know um but helping build out the verify our websites is something else that would be really useful in general because that also helps convey the information that comes out of those verifiers uh and then also reviewing the specification um just a month ago we had somebody get up on GitHub and was looking at the spec and found a more efficient way for us to do the key ceremony and the decryption that ended up saving probably about 30 percent of the compute Cycles which was really cool to see happen you know especially in a room with a whole bunch of academics who've been working on this thing and then like all of a sudden somebody comes in and finds something really cool and new and like we responded to that and within two weeks they had changed the specification and uh we had started building that new thing um we've got some cool stuff um on the roadmap like Risk limiting audits uh and ranked Choice voting and other benefits of voting some of this stuff really requires us to do cool stuff like uh build a proxy re-encryption mix that and things like that and um these are all really kind of interesting like academically difficult for me at least um uh software engineering problems that we can we're always looking for people to contribute to new ways to uh help with that stuff and then of course Microsoft has a bug Bounty uh you know anything simple you can just throw it up on our GitHub uh anything that is security related there's a process for that that's in the GitHub and uh you know I've seen them pay it out before so um yeah there's some cash yep I think that's it I know I blew through a lot of stuff I got about three minutes left if anybody has any questions do we have time for questions can you can you go over the section where it was the spoil versus cast vote because you were saying the system itself wouldn't be able to know what the user is doing is that like like assuming the system was affected by malware or is this something like can we go over that area a little bit more yeah sure so um the question is how does the uh the the process around the casting and the spoiling and the encryption work particularly if they're on the same machine right so the um once you encrypt the ballot depending on what type of system it is that encryption might print out the confirmation code it might display it as a QR on a screen uh or uh you know some other way but once that confirmation code is created the um that specific machine even if it's on the same computer it doesn't know what you're going to do um whether you're going to cast or spoil the ballot itself so once the encryption is created there's no way for them to change it so even if there were malware that were running on it and as long as a few people actually go and check the spoiled ballots and improve then you can you can rely on you know statistics and heuristics to validate that the machines are behaving correctly the other thing that's probably important to note here too is that if any of these proofs don't check the system is designed to Halt and um we made that decision um kind of early on mostly because of the fact that the people who are going to be working with these things these machines are non-technical so if there's a major problem with the math we want the machine to just stop when they turn it off and they take it out of service and then they go get a backup and they put that that one in and then we can take it offline and see what happens does that answer your question thanks very much I really appreciate this and it's fascinating like uh yeah thank you this is uh it's really gonna help build the future and keep it safe uh so we're just gonna do a couple minutes of setup and in just about two or three minutes we're gonna uh talk about uh using this uh with the Brazilian government for uh hackathon