The IACR Can't Decrypt with Matt Bernhard

The International Association of Cryptologic Research (IACR) held their regular election using secure voting software called Helios…and lost the keys to decrypt the results, leaving them with no choice but to throw out the vote and call a new election. Hilarity ensues. We welcome special guest Matt Bernhard who actually works on secure voting systems to explain which bits are homomorphically additive or not and more.

Watch on YouTube: https://www.youtube.com/watch?v=euw_yqAQFI8

Links:

This rough transcript has not been edited and may have errors.

David: No, no, no, no, no, no, no, no, no. No one has ever made anything easier by introducing threshold cryptography. You have at best made something possible. But you haven’t made anything easier.

Deirdre: Welcome to Security Cryptography. Whatever. I’m Deirdre.

David: I’m David.

Thomas: I’m pretty amused right now.

Deirdre: That’s Thomas. And today we have a special guest. Hi, Matt Bernhard.

Matt: Hi there. It’s great to be here.

Deirdre: Thanks. We invited Matt on today because there was a very funny thing that happened in the world of cryptography this past week.

David: You’re shooting too low. This was in the New York Times.

Deirdre: That’s true. Okay.

Thomas: Yes, I think they were in the New York Times because of my tweet. This all stems from my tweet.

Deirdre: Are you sure? I didn’t see your tweet.

Thomas: I decided to be confident about this fact.

David: I didn’t even know you tweeted Me.

Deirdre: Either, but I smashed my phone. So I’m all out of the loop on Twitter at least.

Thomas: So the International Association of Cryptographic Research, or Cryptologic Research, the logic. Yes. The IACR holds, what is it, annual or semiannual elections for roles within that organization. IACR runs a bunch of the major crypto conferences. So these are like the people that manage that whole enterprise. They have elections of all their members, you know, to elect directors of the organization and a president and a bunch of other things like that. They just held their election, which I found out because they emailed me to say that the election had failed due to the fact that one of the trustees of the election lost the cryptographic key that was required to decrypt the results. So they ran the entire election but are unable to decrypt it because somebody lost a USB key.

Thomas: That’s what happened.

Deirdre: Or the file that was on the USB key or something.

Thomas: I choose to believe that it is a USB key that holds the threshold key required to decrypt the IACR election. They use a system called Helios for this whole scheme. And I guess Helios has been used for other things besides this election.

Deirdre: Yes, they’ve been using Helios for a long, long time. And I’ve used Helios and other election thingies and other. Helios has been used and it’s been around for over 15 years. But this one was very funny because it’s the cryptographers can’t decrypt.

Thomas: So we’re going to get into the Helios details and online elections and all that. But I think like a better to start out with is Just what the IACR is. So I’d like to start with the fact that I’m pretty sure half the Internet now believes that every protocol ever presented at an IACR conference is now backdoored by the nsa.

Deirdre: They’re just papers.

Thomas: That was true of the post quantum cryptography competitions. You and all of that stuff is backdoored.

Deirdre: Oh, all of it.

Thomas: This is an actual. Yeah, this is an actual bogus election. This is like the January 6th of cryptography. Somebody didn’t.

David: The count was in fact stopped.

Thomas: Somebody didn’t like the way that count was going.

David: What are they hiding from us?

Thomas: So Deirdre, can you help me understand more? I happen to be a member of the iacr and the reason for that is I went to meet David and Deirdre at Real World Crypto, which is the best of all of the annual cryptography events. Right. Last year it was held. Was it last year? I think it was last year.

David: Two years ago.

Thomas: Two years ago.

David: A year and a half ago.

Thomas: Okay. It was held in Toronto, which is like driving distance from my place. So we drove up, I picked up David on the way and then we went to Real World Crypto to get into rwc. I was required to join the iacr. David disputes that this was a requirement, but I remember distinctly not wanting to be a member of the iacr or rather feeling that it would have no value to me to be a member of this organization. And yes, I am a member. And I know that because I was told A, to vote and B, the vote didn’t work. So you guys could read me a little bit more about what this organization actually does and really what the implications of the vote are.

Deirdre: So it’s just another academic body that runs conferences and lets you. So the flag, the tent poles for being a academic cryptographer is the Crypto conference, which is held in Santa Barbara every year. And it’s been going for 40 years now. I think Eurocrypt, which is in a different place in Europe or every year, and now Asia Crypt. And those are the big three. They’re considered some like the most prestigious academic, like not purely theoretical, but like straight up cryptography, cryptology and you know, a little bit of, you know, attack stuff in the world. There are other venues where you can do more applied stuff that’s more of like a security vent. But for straight up cryptographers who are doing straight up academic cryptography, those venues run and operated by the IACR is where it’s at.

And then they add, they added the Real World crypto symposium a couple like over 10 years ago now and that became very, very popular because it’s not a place where you submit papers and get published in peer review, but you submit presentations and they also get reviewed for, you know, quality and relevance. And it also appeals to people in industry who may not be publishing cryptography papers, but they’re very interested in like what how this stuff gets deployed and results that affect the real world.

Thomas: RWC is the good one because it’s where most of the good attack presentations get published or at least most of the good.

David: Real world crypto is just the worst MTV reality show.

Thomas: I remember it not being an especially good MTV reality show. Do the directors of the ICR pick the program committees for rw?

Deirdre: I think you have chair of the actual conference and the actual symposium you have several chairs and they help choose the program committee and they help us try to find them. Because for example for crypto Eurocrypt and Asia Crypt, you may need like 100 people to be on the program committee because there are just so many submissions to review. I think it’s smaller for real world crypto to review submissions because it’s not full on papers, its presentations. And then there’s a bunch of other smaller conferences for real World for icr. And then the other thing that IUCR does, they run the EPRINT cryptology archive. It’s basically archive where you published all sorts of pre print papers from all over science and academia. But ICR and the cryptographers basically have their own and we don’t know why they just aren’t on archive like everybody every other field but they do and that is a really good place to keep up to date on the latest developments in academic cryptography. Because basically everyone submits a paper there whether it’s just an idea or a very important result that they want to see, everyone to see.

Thomas: So I runs the three most important conferences in cryptography.

Deirdre: Yeah, conferences where papers are peer reviewed and published. And then they also run real world crypto which is very important for more applied industry stuff.

Thomas: So in the field they’re doing essentially the same thing that ACM does for computer science or Usenix or like Springer for the other sciences that are even worse at the stuff.

Deirdre: Spring is a publisher. But ACM and Usenix, correct? Yes, it’s just, it’s specific to, you know, robust quote academic cryptography.

David: For under peer review they’re arguably more competent because they run multiple good conferences. Whereas like Usenix runs well, USNIX runs a few in A different field, but they run one security one, and then ACM runs one security conference and then IEEE runs one security conference. It’s not in Oakland and everyone calls Oakland. But the ICR manages to run more than one top tier cryptography conference, which is actually kind of impressive for an organization to do.

Thomas: Okay, this makes sense. So, yeah, I still don’t know why the New York Times cares about the vote. I do get the. I do get the funny part.

Deirdre: Let’s see.

Thomas: Oh, it’s a fellow. It’s a person like an early career journalist that like got a break on the story. There’s a little blurb about it at the bottom. I’m sure they’re great. I’m just saying there’s a little blurb about this at the bottom. I too was wondering whether this was like a beat reporter at the New York Times that found this out. But no, apparently not.

David: The person who’s assigned to cryptography the whole time.

Thomas: Well, I mean, there’s people that are assigned to the Internet or computer security. Those are topics that actually get covered. I think the entire angle on this story is just that it’s really funny.

Deirdre: Literally. Cryptographers have a fancy way of doing their elections with fancy cryptography. And even the cryptographers can’t hold onto their keys to do their fancy decryption.

Thomas: I think that’s, that’s it among the four of us. Could anybody competently describe how the system roughly works?

Deirdre: So one thing that I did learn, like I’m, I’m threshold pilled because I worked on threshold signatures for several years when I was working when I was at dcash. Helios has, I’m pretty sure, El Gamal encrypted ballots. And that’s kind of funny because. Oh, wow, we are still doing Elgamal in 2025. Okay.

Thomas: This is the last place.

Matt: There are others.

Deirdre: There are others.

Matt: It’s not the only end to end voting library that uses ElGamal. In fact, there are two others that I know of that are used.

Deirdre: It kind of makes sense because of the pro, because literally elgamal is basically like public key encryption with. I’m assuming it’s elliptic curves. It’s not, you know, finite field or something like that. Maybe it’s.

Thomas: You’re assuming.

Deirdre: I looked at the paper and it just, it just said elgamal. And I was like, okay, I have to go dig into the code to actually figure out if it’s, you know, something not as fancy, but we can go see.

Thomas: We could find out on the voting site Right now. So the whole thing is done via a web app.

Deirdre: It is to be a web app.

Thomas: All of this cryptography is cosmetic.

Deirdre: Oh, shush. We have an old, old episode where we can refer to whether or not that you believe in that or not. But no, I do not think the Helios hosting is doing any of the fancy pinning and hashing and website web app transparency stuff that we all recommend for secure delivery of client based apps in the browser. We’re just going to leave that aside.

David: We all recommend.

Thomas: Nope.

David: It is.

Deirdre: Well, you know, if you want to really try to get application level security for a web app, a client side web app anywhere close to like what you can get for a mobile app or a desktop app with, you know, comparable security, you need some extra stuff on top because it’s. Otherwise it’s just tofu, whatever the server gives you. Right.

Thomas: It is. The code for the Helios version that is run for this election, which is hosted on heliosvoting.org is public. There’s a link to at the top of it. And it’s finite field elgamal.

Deirdre: Yes, it is finite.

David: I was going to say this is from 08. Definitely finite fields.

Deirdre: Yeah. Okay, so we have finite field elgamal and as far as I can understand it, it’s using elgamal to basically commit to this stuff and to voting values in these ballots. You have a ballot and you can tick more than one value or you can tick yes or no for a ballot position or whatever, a referendum, which is one of the things in this most recent election. The nice properties of algomal is it lets you add up stuff that is still encrypted. It lets you tally these things in a private way. Then at the very end, if you know the secret, you can decrypt these final values or you have to know enough of the secret or all of the secret. I thought that in this day and age, they were using a T of N threshold of key holders to decrypt because that’s a thing that we’ve known how to do for a very long time. They’re not doing that.

It just sounds like they just have. You have a third and you have a third and you have a third and you have to smush them all together to just get the decryption secret of the tally. The hormone warfare added up Elgamal ballots and then you can decrypt them at the very end.

Thomas: So hold on a second.

David: So to be fair, that’s still a threshold.

Thomas: I feel as if I might be learning. I feel like I might be learning something here. Right. So RSA is famously homomorphic with respect to multiplication. There’s like, there are attacks that work that way. Right. So El Gamal is additively homomorphic.

Deirdre: I think so.

Thomas: Mac Bernard is.

Matt: Well, it’s, it’s, yeah. Added homomorphic by multiplying ciphertext together.

Deirdre: So okay, yeah, yeah. So like you, you multiply the things together but underneath the value is like, you know, here’s, you know, one for Thomas, one for David and yeah, yeah.

Thomas: Matt started this whole thing by saying. Matt started this whole thing by saying that we’ve forgotten more cryptography than he had that he, he’d ever had. But like I didn’t, it’s still true.

Matt: This is the one small sliver of it that I, I know sort of.

Thomas: Well sometimes if it’s cryptography that no one would ever have to pen test, I know nothing at all about it. And Elgamal exists nowhere in industry other than apparently this.

Deirdre: And it’s tough because the papers, the documentation is from the paper from 2008 and we are looking at the updated maintained source code, but there’s not a lot of docs in between here and there that I can see. But yeah, this was a. There are other ways to do private balloting, private computation, private tallying that do involve a T of N sort of decryption scenario. And this is using a slightly different way of doing cryptography that makes it so that you may configure the system all system, not necessarily Halios Halo doesn’t support that yet to have say two out of three. If you have two out of three key shares, because three of the cryptographers that you have trusted to run the election and decrypt the results are available and one of them lost their share, you can still decrypt the tally underneath. And this uses fun stuff like Shamir secret sharing and things like that and lovely polynomials to make it happen. But that is not implemented here. If any one of them lost their share, or not even share, but piece of the key no one can decrypt, everything’s fucked.

Thomas: Why is this the one sliver of cryptography you actually have? What I was asking Matt why this is the one sliver of cryptography actually.

Matt: Has that I actually know about.

Thomas: Yes.

Matt: It’s because when I was an undergrad I had to implement a slightly newer variant of it for the Star Vote project, which so, you know, even before Helios came out, there’s been, you know, the stream of Internet voting and of enabling voters to vote on their phones for all variety of reasons.

Thomas: Right.

Matt: And Helios was a really big and kind of surprising, I think even to Ben himself, step forward in that realm. It was like accessible. He actually productionized it in a way that people like IACR could use it. But it did have some very obvious and serious drawbacks. And so a bunch of people in the academic community picked it up and ran with it pretty much immediately. Like, there are pretty sure forks of the Helios GitHub that have threshold fully implemented.

Thomas: Right.

Matt: There are like, and there have been, you know, maybe not dozens, but a dozen papers written about how to do certain things with Helios and they’re still being published today.

Thomas: Right.

Matt: Like there’s, there are new attacks on Helios all the time, but there are other, other systems that have come out since then. Star Vote was one that, you know, like Ron Rivest and a bunch of folks worked on. Election Guard is probably the biggest name right now in our industry, in the elections industry that came out of Microsoft. It was Josh Benilo who way back in the 80s wrote his PhD dissertation on how to do basically what Helios is. And then with Mixnets at the time, and then it’s come forward a lot.

Deirdre: That’s a thing that I didn’t realize was built into Helios. I thought Helios was just homomorphic stuff, like the niceness of the underlying, like, I, I didn’t think it was like some fancy schmancy, like fully homomorphic encryption going on, but I knew that there was, you know, leveraging the homomorphic properties of whatever the math was under the hood to tally the stuff up. But it does involve some sort of mixing as well to get, to give you more anonymity. Can you tell us a little bit about that?

Matt: Yeah, that I’m not super clear on. The like, you know, the kind of off the cuff read of it that I can give is, you know, when you’re tallying the mixnet typically, and I think Helios publishes a bulletin board of ballots too. Right. So when you, when you vote, your, your vote gets encrypted into a homomorphic ciphertext that when they run the tally, they, you know, multiply the ciphertext together and then decrypt the final tally. But they also publish the encryptions of all the ballots. Yes, individually.

David: Right.

Thomas: I just, I just cast my vote before we started recording and you get, you, you see the whole bullet port of all the votes that are there. Right.

Matt: And so theoretically, after the election is run, the administrators can provide a way to decrypt to sum and decrease. Right. You can implement your own verifier is what they call. You know what this is typically called and I don’t think Helios does it, but newer systems have like Nizix and other fancy things that you can do to. You can prove that this contest was a vote for one. And so there’s only one valid vote in this ciphertext and all that stuff. I don’t know that Helios does that or not.

Deirdre: I don’t see anything to indicate that. And especially because if it has to be completely in the browser sounds doable. Like I know that like fancy cryptocurrency wallets will be able.

Matt: It’s doable.

Deirdre: We’ll be able to do it. But I don’t. I have a feeling that’s just not going to be supported in this Source.

Matt: Like a 2008.

Deirdre: Yeah, yeah. Or, or, you know, even that sounds like a big chunk. That’s a big upgrade and a big chunk of work. And like, I think it’s Ben Adida, who is the. The creator of Helios. He’s still maintaining it just sort of in his copious spare time. I don’t know if that would be supportive. But yeah, having real zero knowledge proofs or at least some sort of.

Maybe not the zkSNARK or some sort of proof on top of it, I think would be a very cool evolution of these sort of systems. But yeah, they have some independent implementations to audit all the ciphertext for valid, which is cool. I don’t know if anyone uses them.

Matt: It’s always the challenge with that kind of technology. And that’s true for not just Helios, but Scantegrity or Predovote. There are a bunch of these kinds of protocols that have been proposed or even mostly implemented and used, but have never been. It turns out that there aren’t enough people who know enough about this stuff, who care enough about the outcomes of the elections and who have the time and ability to do it that they go and do it.

Thomas: I’m 80% sure that Helios itself does verification of whether the ballots are well formed, but I’m not seeing it in the original Benedita Helios paper well formed, huh?

Matt: This may be me like munging several papers together.

Thomas: Yeah, but you’re the only one here that actually understands all this stuff, so we’re just going to take your word for it.

David: I was distracted. Distracted voting. I feel like this, this failed election is really just going to act as a way to get out the vote.

Thomas: Did you vote for, did you vote for the referendum?

David: I did vote for the referendum. Yay.

Matt: This is one of the other, one of the other major problems with, with a lot of these is privacy. Right. And, and Helios has a coerce me function that you can expose how you voted. I don’t think your ballot gets counted when you click that, but yeah, maybe it does.

Deirdre: Yeah. I think they spoil it. I think they explicitly spoil it, or at least that’s what the UI says to the human. They include information to prove how well the ciphertext was formed. But I don’t think there’s anything else about, you know, making sure that things are well formed when you’re not spoiling your ballot to prove that you are able to create the ciphertext with your public key and the randomness that you use to create it. That’s one kind of, well, formedness.

Thomas: And I just checked my intuition on this. So the idea here is if you’re relying on the additive homomorphic property of alchemy, then you can tally the votes without decrypting them. So the well form in this thing is really important because when you’re tallying the votes, you’re not actually decrypting them, you’re just trusting that whatever’s in there. So if it’s like a pick two of three, then you really care about whether somebody did three of three instead of two of three or whatever. Right. And so some kind of system would have to get built to let you check, you know, let you verify the integrity of the votes themselves to make the system secure is that you could.

Matt: Do all kinds of things like have, you know, minus five votes for a candidate or something in a ciphertext that cancel out votes or, you know, it.

Deirdre: Seems like a hard problem to. Well, I don’t know about the specifics of finite field algomal, but it does seem like a difficult problem to verify anything about a ciphertext until you actually have like all this. All you have like the plaintext and the inputs and the randomness and like a public key or something like that and the ciphertext. Otherwise you just have a ciphertext. And as long as it’s like in a range, like you can’t really say much about it until you can actually decrypt it. Right?

Matt: Yeah, there’s typically several. Like in the systems that do publish proofs, there’s like several components, like the ciphertext, we call it the ciphertext, but really it’s like four different things that get published and it’s, there’s like a commit pin and some other stuff that I’m a little vague on at the.

Deirdre: Moment, but okay, that sounds better because there are other systems that use these homomorphic properties like zcash where you’re doing all of these balance computations of like I’m trying to spend a note and I’m going to send it to this thing and you know, here’s all the balances that are, you know, fully encrypted on chain, but you’re doing all this other stuff at the same time. You’re doing a full ZK snark about all the witnesses of all the inputs and you have knowledge of your spending key authority and like all this sort of stuff along with all of these little commitments. And those commitments are with elliptic curves that let you get a lot of that stuff for free.

Matt: Yeah, and that’s actually sort of the central problem in voting in particular is like you both have kind of an extreme need for privacy and a really also an extreme need for public transparency. Right. A way to like you can’t allow any voter to prove how they voted in most constructions because it leads to things like vote buying or you know, vote my way or I’m going to break your kneecaps or whatever. But if you don’t have that, it’s really hard to prove later that everything was well formed if you’re doing, especially if you’re doing homomorphism, that kind of thing. And that’s also where the coerce me thing that I talked about, there’s this notion of voters can kind of prove to themselves because as a voter, why would you believe that the system is accurately recording your vote?

Deirdre: Right, right.

Matt: I vote for candidate A. How do I know that it did that? And so the idea is that you can kind of iteratively spoil your ballot and make the system decrypted. And usually it’s decrypted with proofs of correctness that it did the right thing. Or you can rework the math yourself I guess to show. And so hopefully over time you build statistical confidence that if it was gonna cheat some amount of the time, I would have caught it by now where I’m like 90% confident or 99% or whatever that it’s recording my vote correctly.

Deirdre: And at least that gives you a system wide trust.

Matt: If people are doing it right.

Deirdre: There’s, there’s a possibility that any one ballot could still be, you know, messed with by the system. But like that is a, that is a one off ballot in a Vote that’s hopefully, you know, many, many, many, many more than that. It will not throw off the results. Yeah, and this is, this kind of gets into the, like the difficulty of voting in any, with any technology that’s not just here is my paper ballot. Here it is. Go figure out how like, I created it myself. Maybe I used my pen, maybe I used some, you know, assistive device to produce my marked paper ballot and I hand it in to somebody either via by mail or literally handing it to a human being at the, you know, at my local precinct.

Matt: Putting it into the thing that counts it yourself.

Deirdre: Exactly. And like, you know, in theory, if the computer who is counting my ballot and scanning my ballot is just like totally fucked up and like full of malware or something like that, you still just have a big pile of paper ballots that I, you know, I saw with my human eyes or, you know, my, my human senses that I produced a ballot and then I gave it to you try. And then all of these other dynamics about transparency but privacy, but also, like, I can’t like prove, you know, I voted a certain way, but I know I voted a certain way because I voted and I handed you my vote. Like, all of these dynamics are part of why voting online or voting digitally or, you know, remotely or even with encryption is like a harder problem than basically anything else that we do online, including banking, including cryptocurrency. We’re private cryptocurrency. Like, are we getting any closer? Like, you know, we can skip Helios, but like, are we getting any closer to something that we feel pretty good about, gives us anything close to the kind of like the feel good nature of. Here is my paper ballot that I produced somehow and handed to a human.

Matt: Yeah, I think in the US maybe in many countries, not as much. So. So it’s. US elections are ridiculously complicated compared to most of the world. Like, we have hundreds of items on ballots. Whereas if you vote in Germany, for example, maybe there’s two or three contests on your ballot at a time. Which is why when people say we should hand counter that kind of thing, it also doesn’t really make a ton of sense. Germany, you know, I picked them for a specific reason.

I believe it’s their constitution explicitly says, like, no election can be held with technology that the average German couldn’t understand. And so that’s where they. So like, yeah, so like homomorphic encryption gone.

Thomas: Right.

Matt: In the US because we vote for so many things. We vote for dog catcher. Right. In some jurisdictions we have to use technology to Administer elections. Right. It’s not really optional. We vote for lots of things. We have lots of different languages.

Matt: We’re a very diverse population. We have the Americans with Disabilities act that guarantees your right to. And the Help America Vote act, which tie together to, if you’re a blind voter, for example, you have to be offered the same voting experience that everybody else gets. As it turns out, that doesn’t work very well in practice.

Thomas: But.

Matt: But because of all that stuff, we have to use computers in some facility. Right. And so we have a lot of robust methods to use computers and check them that all rely on right now on paper ballots. Right. As you mentioned. And so Internet voting is still, I think, a pretty far, a long way off. We’re a lot closer to it than we were in 2008, right. When Helios came out.

But there’s still so many. Even, even just the, you know, the specific cryptographic challenges are pale in comparison to all the other problems that we have to. Not every voter has a smartphone to the coercion problem. And this is actually true for absentee voting at home as well to some extent, where if you’re filling out your ballot, not in a booth that is under watch of poll workers or whatever, you could be coerced. And even if you are, we have smartphones now, so you can take a picture of your ballot as it goes into the scanner or something, which may or may not be legal, depending on where you live. It’s complicated. But, you know, there’s that stuff. There’s.

Okay, so I’m voting on my phone. I also have client side malware on my phone that’s watching me vote. You’re creating a single point of failure. So there’s like one server or many servers that are taking in votes. What if they go down on election day? What if Cloudflare or Amazon or Microsoft have an outage? You know, let’s say just to pick an example totally at random, that’s never happened before. So there’s all of these kind of problems that stack up on each other that it’s not. It’s not even just the public evidence secret ballot problem. Like, specifically, there’s so many other challenges that we’re maybe starting to kind of solve in some ways, but not really robustly enough for everyone to vote.

Right. Like if it becomes the single. If you people are doing it, it’s probably okay because the margins are going to be wide enough or whatever. But yeah, there are substantial challenges.

Deirdre: Yeah. And like, there is legislation on a lot of, you know, different Jurisdictions, books of like, there is one voting day. Like you must vote on a day and you know, maybe they have, you know, absentee ballots or something like that. But like, everything else is like you have a single day, it must not fail. Like, you know, what do you do if someone, you know, d some critical service and you know, etc. Etc.

Matt: And so which happens, right? I mean, that’s what causes lines at polling places, right? It’s not just. Yeah, you know, there’s all manner of crazy things that happen. But the fun fact is many jurisdictions in the US and not just here, Canada also has this as well, and a couple of other countries, Estonia’s also at the top of the list, also require Internet voting for certain voters. If you are on a battleship overseas, right, or you’re in an active war zone or just in a country that doesn’t have robust mail, we can’t nail you a ballot. It’s not going to get there in time. And even if it does, it’s not going to get back to us in time. So, you know, Internet, Internet voting scare quotes, right? Has been a thing in the US for 20 or 30 years. But what it has meant historically is I’m going to fax my ballot or maybe email a PDF of my ballot, right? And so we are getting closer to making that situation better, right? Because like, you know, we can talk about, you know, homomorphic encryption all day, but if you’re faxing your ballot at the end of the day, like, so we are getting that, that is already getting better just because it has to, right? Like it’s, it’s too big to fail or whatever you want to call it.

Deirdre: I honest to God, don’t hate the idea of like filling out a PDF of my ballot and like sending it somewhere. Like, I don’t like, security wise, reliability wise, even privacy wise to a degree. I don’t mind that that much. Like all this other stuff, I’m just like, oh, that’s going to, we’re going to fuck that up. Something’s going to go wrong. But like, literally, like, here’s my ballot. I emailed it or I digitally faxed it. Like there has to be some sort of, you know, digital service that gets between that, you know, turns my PDF into like, you know, a dial tone on the back end to fax it to a number. I don’t hate that.

David: It’s all fun and games until you don’t sanitize your PDF file names. Oh God.

Deirdre: Oh God, that’ll be, that’ll be. The next thing is like, we found this terrible PDF parser vulnerability in the critical, like, absentee voting system of such and such an election.

Matt: Well, and we have. Right. I mean, it’s not just the fax and email, but also there have been several vendors who have tried to do some flavor of. Of vote by app.

Thomas: Right.

Matt: Votes is the most poignant one to me because they were a blockchain voting app right in the. And they’re still around, but their heyday was, like, right before COVID and, you know, a couple of security researchers started looking at their stuff and found out they didn’t even use a blockchain, right. Like, it’s. It turned and, you know, when they were transmitting the data, they weren’t masking it. So you could literally just watch the bytes go across the wire and tell who someone voted for because, you know, they weren’t. They were scrambling it or whatever. But it wasn’t like, actually robustly encrypted. So, like, the longer the candidate’s name was, the longer the bytes were that went to the server.

Matt: And so, you know, like, so, you know, it’s.

Deirdre: It.

Matt: You know, it wouldn’t support you voting by PDF necessarily, but, you know, there are, there are better ways to do it.

Deirdre: Oh, gosh, I, I hate, I hate that you didn’t even use the blockchain. You could, you could have. It would have been better than that.

Thomas: I have, I have a, I have a Helios question, even though none of us are necessarily Helios experts here. So if you look, there’s, if you look at the Helios paper or the first Helios paper, there’s like a, like two, four of that paper is what the whole process is and just a couple of bullets. Right? So it’s like, you know, the person who’s voting prepares a ballot for themselves. You can prepare as many ballots as you want, right? When you, you know, when, when you feel comfortable with that the ballots are valid or whatever, you’re like getting predictable thingies on the ballots. You can cast that ballot, which is essentially encrypting that ballot to the private key of the election administrators, to the trustees, effectively. So far, so good. That’s right. That sounds good.

Deirdre: That sounds. They have to do that in some fashion.

Matt: Right?

Thomas: So the key thing on the system, like all of the, you know, the voting systems of this vintage. I guess that’s going to be true of blockchain voting, too. But you cast a vote, it gets recorded by the server on a bulletin board for the vote. Right. Which is what I see when I Cast my ballot for my CR Just now is like, you don’t see people’s names. You see like an identifier. You get like a voting ID or whatever. You see the bulletin board of all of the votes cast.

That’s step two. Everybody can check that and see who’s voted. And then when the election closes and they’re about to go tally all the votes, shuffle all of the votes in the bulletin board. So the votes on the bulletin board as cast are linked to the voter, if only by metadata. Right. Like, you know, when it was cast, you can do traffic analysis to see when it was cast to count all the votes. They’re going to decrypt them, right? They’re going to.

Matt: Not individually, I don’t think.

Deirdre: Not in. Yeah, not individually.

David: Going to multiply all of them together to add them and then decrypt that.

Deirdre: Yes, yes.

Thomas: Yeah, they’re going to decrypt the tally vote thingy. Right. So they do the shuffle step because they don’t want to be operating directly on the bulletin board. Entries which are linked to the identify the identities of the voters, which is why they have all this mechanism to do the shuffle and then to produce a proof that there was a shuffle, which seems like a big part of the core of the system is like the verifiable shuffle. And the safeguard is if you don’t have that verifiable shuffle, people will know the election wasn’t valid. They’ll just say it wasn’t, it wasn’t. Right. But if you, if you skip the shuffle, you can violate the privacy of everybody that voted.

Deirdre: Yeah, it’s, it’s. I don’t think that if you don’t do the shuffle and have a verifiable proof of shuffle that you can’t still do the homomorphic tally and then decrypt it. You just lose the privacy of the, of associating IDs, times of ballot and like literally the order in which those, those encrypted ballots came in, you lose the privacy, but you don’t necessarily lose, like, quote, the integrity of the actual, of the actual results.

Thomas: So leaving the server itself, like the code behind it aside, which might enforce arbitrary policies. Right. From a cryptographic perspective, it is possible to tally all the votes that were cast without shuffling them?

Deirdre: I think so, yes. Yeah.

Thomas: And the only cryptographic safeguard that they give you is you would at least know that that happened because you wouldn’t get the cryptographic proof that they did the shuffle. This is also why they have multiple trustees. So multiple trustees can Provide a cryptographic proof that they did the shuffle.

Deirdre: Oh, I didn’t know that.

David: I mean, you could just like, take a backup, right? Like, you know, cryptographic proof that the unshuffled version.

Thomas: Well, this is kind of my. This is. This is my whole question. Right. And this, this, this gets more generally to voting systems and not just Helios. And I’m also saying this because maybe Benedicta will hear this and yell at me, but, like, do I care that much? Like, it seems like you want more safeguard then. Okay, I know the election was manipulated, right. It’s still a pretty grave privacy violation to decrypt somebody’s vote, right? To know how somebody voted.

If that’s the attack you’re worried about, that’s not an attack on the integrity of the vote. It’s an attack on the safety of individual voters. I’m wondering what I’m missing about this.

Deirdre: So I don’t think the executors of the election, the ones that you encrypt your ballot, 2. Can decrypt individual ballots.

Thomas: No. Yeah.

Deirdre: Your. Your individual ballot, clearly they cannot.

Thomas: Clearly, individual trustees cannot be cripped or.

Deirdre: Else we wouldn’t in this situation. Yeah. So it’s. There’s still a level. It’s. Yeah, like. Like you mentioned there. There’s still a level of like, this value that you cast as your ballot is still protected by the elgamal, the fact that you like it.

Deirdre: You can get a lot of meta information, metadata about the voters and when they voted and at what time they voted, and you can associate. This encrypted ballot was cast first. And based on the server logs, we can see that it was cast from somewhere in European central time or whatever.

Matt: Or somebody tweeted, hey, I just voted in the yes.

Deirdre: Yeah, so I think it’s that sort of thing. But I do not think you can decrypt literally what the very first vote cast by someone who tweeted that they did that, what the value of that vote is.

Thomas: Well, if you didn’t do the shuffle, right, like, just. Just assume you’re doing everything homomorphically. Right. You’d still know roughly what the votes were. Right. Because you know the before and after state of each one of the. Yeah, see, you’re all making faces at me. Let the record show for people listening to this, they’re all making weird faces at me.

David: I’m with you. So I guess you could homomorphic with all but one Y.

Deirdre: Like, you. Like, in theory, you could just be like, cool, the vote, like one. One vote cast. Decrypt the entire thing. Two votes cast. Decrypt the entire thing. And so on and so on.

Thomas: Yeah, so like. And like, this is not like a new attack on the system. Like, this is the whole reason they do this.

David: You would need all three.

Deirdre: Yes, you would. You still need all. All the shards or whatever, you know, the three of three. I’m not even fully sure if it’s three of three or if it’s.

Thomas: I think it.

Deirdre: I think it’s literal. Like, this version of Helios is literally.

Matt: It’s just three.

Deirdre: It’s just like, I need this chunk. It’s not even like three of three, you know, with Shamir polynomials under the.

David: Hood, it’s just everyone gets a third.

Deirdre: Yeah, I think so.

Thomas: Okay.

David: I think so.

Thomas: Even if you. Yeah, okay. So even if you wanted to, like, even if you wanted to break the whole election and violate somebody’s privacy, you need to get all three trustees to do it. After you did that, there’d be cryptographic proof that that happened, or at least there’d be cryptographic proof that you didn’t do the shuffle. But as long as any of the.

David: Trustees are doing the shuffle, there wouldn’t be cryptographic proof that you did the shuffle.

Deirdre: Right?

Thomas: That’s what I mean. Yes.

Deirdre: So the wikipedia page says 2.0. Helios abandoned the shuffle and switched to a homomorphic encryption scheme to make sure that that was kept private. So we may be out of date.

Matt: You could still do this because couldn’t you still, like, decrypt as you went, and then at the end, you still have the original ciphertext? Just add them all together and decrypt the final tally or do the shuffle or whatever, right?

Deirdre: Yes, I think so.

Matt: So I think there’s like, two things going on here.

Deirdre: Yes.

Matt: One is the privacy concern and one.

Deirdre: Is the integr integrity.

Matt: Yeah.

David: Maintain the privacy. On this podcast, we’ll have an indeterminate amount of time in between when we record this episode and when we release it. So you can’t figure time and figure out which vote came from.

Deirdre: Me and Thomas provide non interactive, zero knowledge proof that we, you know, of the time. I don’t know. Something like that.

David: Well, you just messaged Deirdre and she says yes or no, depending on if you’re on the right or left side of the time.

Thomas: I just like understanding why there are three trustees and how they’re actually, like, what the roles of these people are or what the roles of these. These components in the system are.

David: One trustee always tells the truth. One trustee Always tells lies.

Matt: Two trustees. Yeah, three trustees is a party, right? What’s the.

David: All of them are trying to cross the river to get to real world crypto.

Matt: One of them is a wolf and.

David: One of them has a chicken. One of them threw their USB stick in the lake.

Deirdre: I think what I heard is literally there was a file and it got saved down somewhere and they just couldn’t find it. I wish it was just literally there’s a USB stick and I have to plug it in and I can’t find it anymore.

Matt: Yeah, the shuffling thing is still confusing to me in that because I don’t. Does the paper talk about Elgamal?

Deirdre: The 2008 paper does.

Matt: Yeah, it does. Okay.

David: I’m just impressed. Ben has maintained a Python project for like what, 17 years? Like, that’s pretty good.

Deirdre: A solid Django project.

David: We’re even on Python 20027 in 2008.

Deirdre: Like, I don’t think so.

David: Might have been 25 still or 23242.

Deirdre: So unfortunately, even if we do the fancy whiz bang version with like fully homomorphic encryption and threshold decryption and 2 of N or, you know, however, T of N for actually decrypting the. The ballots, the full. The full tally and everything like that, it still reduces down to. You have a key and you gotta maintain that key. Sounds like a very human issue that we just don’t quite have a good way to solve. So. I don’t know, Matt, you seem to have the most experience in this field. Like, are we getting any.

Deirdre: Getting anywhere into a future where like, don’t lose this key is not just like the root of all of our problems.

Matt: I think you’re. You know, there’s. It always devolves to somebody maintaining an X509 cert in an HSM somewhere and then deriving keys from there. I don’t really know.

Deirdre: Yeah, I do think that the actually getting threshold encryption, threshold whatever, working helps so that if you lose one piece, you’re not totally fucked. You can have a configurable T of N. The trouble is that actually setting up all of those thresholdized keys is a whole other rigmarole. You can have a trusted dealer usually, and that’s maybe if you all sit in one place and you do it and you just trust each other, you could just do that. But if you’re not, you either have to just send them via some other secure confidential channel that you authenticate a.

Matt: Channel that you have another key bootstrapping.

Deirdre: Problem, or you do some sort of fancy Distributed key generation thing, which is very, it’s very popular. And they try to make that happen in like kind of the blockchain world where you don’t really trust each other and there’s. You don’t want to have any centralized, trusted authority who’s generating keys and handing them out. But depending on the kind of cryptographic system that you’re using, that can get real complicated too. Like you might have DKGs that have multiple rounds and can fail and on and on and on. And, you know, maybe you need to use something called a broadcast channel. And if you ask a cryptographer who publishes a distributed key generation algorithm in the paper, and you’re like, where can I get. Where can I pull an implementation of a broadcast channel from like GitHub? They’re like, what? What do you mean? Because that thing doesn’t exist.

So, you know, to quote Lee Kistner, cryptography tends to take security or other problems and turn them into key management problems. And that could. But it continues even down the rabbit hole of the threshold stuff, which in theory would help mitigate the. Someone loses their part of the key thing. To a point. And I don’t know, we might be improving it a little bit, but not completely.

Matt: Yeah, I mean, I can say like Election Guard does threshold, it does K of N or T of N. And yeah, you literally sit in a room with your Microsoft Surface tablets. You know, all the trustees come and they, they do a key generation ceremony. So it’s not, it doesn’t really get better than that, as far as I can tell.

David: What. What is Election Guard?

Thomas: Sorry.

Matt: Yeah, yeah. So Election Guard is an open source specification and implementation of end to end. So Helios is like classified as an end to end verifiable voting system. There’s like three properties of end to end verifiability, or it depends on who you ask. But there’s a bunch of different definitions in the literature. I think the most widely adopted one is there’s three properties. There’s cast as intended, collected as cast, and tallied as collected. Cast as intended means I’m the voter, I voted for Bob and the system recorded my vote for Bob correctly.

That’s the Helios coercing thing, where you can decrypt your ballot. There’s collected as cast, which is I submitted my ballot and I now have proof that it was received by the server. So that’s the bulletin board thing where I have the ciphertext and I can see that the ciphertext is in the same place. And again, I’ve convinced myself that the same inputs produce the same ciphertext or whatever, you know, a correct ciphertext and then there’s tallied is collected which is the homomorphic encryption thing. Anyone can grab all the ciphertexts and munch them all together, produce a tally and verify that the ballots, it’s garbage in, garbage out. Right. If the right data went in, then the right election outcome comes out. So Helios is part of a broader constellation of these end to end voting systems and Election Guard is sort of the most not, it’s definitely not the only robust.

Swiss Post actually has an implementation that I believe Olivier Pereira, who also worked on Helios did an analysis of with Vanessa Teague.

Deirdre: Heard about that one. Yeah, yeah.

Matt: And they found a bunch of problems. They went through an open process because it’s a governmental process, so they had to submit for feedback and all that kind of stuff. So Swiss Post is one variant. And Microsoft kind of their goal was like how do we make election security better? Why don’t we just put out an SDK that supports all the end to end primitives so that any vendor like a voting machine vendor or an Internet voting vendor can use it and actually do better than just beating votes and not using a blockchain and saying you’re using a blockchain.

Thomas: Right.

Matt: And there’s actually literally a couple weeks ago there was another competitor SDK kind of thing launched that also is. It was written by Free and Fair and it’s you know, Election Guard and this new thing by Free and Fair that I can’t remember the name of are, you know, they’ve done like, they’ve written up proofs in like COQ and stuff and they’ve like, you know, it’s verifiable, et cetera. Supposedly it’s correct. Yeah. So Election Guard is Microsoft versions of that, Microsoft’s version of that is probably the most widely used in the United States. It’s been taken up by one of the major voting hardware vendors. My employer reuse it for our, one of our applications. And yeah, it’s just, it’s kind of like Helios with a few more bells and whistles. That is just an SDK that you can use instead of hosting it as a web as a wholly self contained app.

Deirdre: So if it’s an SDK like is there like how does it fit into some sort of backend or is it just sort of like all sitting on, you know, basically like a, like a PC that you sit in your precinct or something like that?

Matt: Yeah. So there’s many different ways you can run it. Right. So there’s. That is one of them. And I think that’s what like Heart Intercivic, the vendor that has integrated it, VotingWorks actually also did a pilot with it as well where you have, you know, there is an Election Guard app that is what does the key ceremony and all that stuff and exports the cryptographic material and then whatever thing on the other end of it is, takes in that material and uses it to generate ciphertexts and then you export the ciphertext from whatever that thing is back to the Election Guard machine to tally, you know, and do the crypto. So like we use it for Internet voting for military and overseas voters. Right.

Harden or Civic is using it for paper ballots. Right. So you, you put your paper ballot through the scanner and it, it has a little bit of Election Guard code local to the scanner that encrypts the ballot there. And you can do, you know, the whole challenge decrypt process I think locally as well there.

Deirdre: But that’s, that’s really cool because I hadn’t heard of like the only systems that I heard of was like the Swiss Post 1 and Helios, which is like we have the whole thing and I completely understand the value of that. But also it’s like a big thing that you have to take on if you decide you want to support that. So having kind of like the SDK version, that’s really cool.

Matt: Yeah, it lets the cryptographers focus on what they’re good at and it lets like human factors people or hardware engineers or whoever focus on what they’re good at. And I think that was a really important lesson that came out of like the Star Vote project, which Josh Benilo was one of the cryptographers on. And he is the driving force behind Election Guard as well. Realizing that voting systems are really, really complicated and trying to do all of it at once is maybe not the right approach to get started.

Deirdre: Oh yeah, this is really cool. And I’m looking at that you even support ranked choice voting and all the risk limiting audits and stuff like that. Can we, can we not to completely go off of, you know, Election Guard and things like that, but can we at least talk about how if there’s anything in cryptography you have to get a quote from Ron Rivest and the New York Times got a nice quote from Ron Rivest and he was very nice about it. But Ron, like Ron Rivest is the R in rsa. So if you, if anyone knows anything about cryptography, they’ve probably heard about RSA and Ron rivest is the one, is the RSA, is the R&RSA in his like later academic career he basically has switched to secure voting and verifiable voting. And I remember when I was getting into cryptography like in 2015 or so or whatever, I went to go see a talk by Ron Rivest and he’s just talking about risk limiting audits of paper ballots whole time and he’s not talking about any math or any cryptography at all. And like at the very end he.

Matt: Kind of like handles my jar of ten sided dice that are used for risk limiting audit because you use a random number generator to draw the ballots. You have to generate a random seed as input.

Deirdre: I love, oh my God, I love that so much. And even for that you’re using, you’re just using a jar of dice, not even like a computer based seed. Like what do you think about like, like I complete, at this point in my career I completely am just like, yeah, let’s like as much as possible like try to like collapse down to paper. Like maybe you have to like fax in a P like whatever your ballot from overseas, maybe you have to have some of it is you know, via systems powered by election Guard or something like that. But like at the end of the day you’re, you know, you’re pulling everything down to paper and then you have, you have your paper record and you have like automatic risk limiting audits and things like that. What do you think about that sort of approach, especially in America? Because I’m, I’m an American and so like I’m thinking about our extremely diverse voting systems and all of that stuff.

Matt: Yeah, I mean simplicity is king. I think wherever it can be. The, you know, there are too many challenges. I don’t think we can get rid of technology altogether. Like I said, you know, if you want to know how hard hand counting is, go buy a ream of paper at Staples and count how many sheets of paper are in it and see if you get the same number as the outside of the package, you know, so I don’t think that’s ever going to be super viable. But you know, it’s sort of, this is another one of these problems where there’s like two really important things totally in tension with each other. It’s like the need to accommodate every voter and the need to be intelligible by anybody. So like, you know, there will always be blind voters who need assistance filling out a ballot in some capacity, whether it’s a paper ballot that they mark on a screen and then it gets printed out or, you know, it’s totally electronic. Whatever it turns out, if they print it out, they’re still blind, so they can’t read the paper.

Deirdre: Yeah. Yeah. Awesome. All right. Did we. Did we miss anything fun about the cryptographers not able to run their fancy or at least 2008 flavor of fancy online voting election? We kind of. We kind of touched on, like, voting is a very interesting. It’s a very social process, and there’s a lot of other.

There’s a lot of other things that we do online or do, like, extremely assisted by technology that, like, it’s different. Like, you. You want to talk to your bank. You want to do banking online. Like, cool. That’s between you and your bank. Making recommendations of specific, you know, very. We have very powerful cryptography and technology that we can try to apply, but sometimes that’s not the important thing.

It’s all these other social dynamics that matter a lot more to trust in the system. So I can both understand why people recommend it and also just sort of like, not yet, maybe not yet. We miss anything.

David: Is there a funnier thing for a group of scientists or specialists to do besides, like, cryptographers lose key and can’t count election? Like, like, physicists get stuck in a dumbwaiter. Like, like, can. Can we top this? Like, chemists, like, eat poison berries off of a bush.

Thomas: Yeah.

Deirdre: Being. I feel like the. The demon core criticality experiments, when they were. They had just started making nuclear weapons, and they’re literally. They’re literally like, twiddling two halves of a plutonium sphere with, like, a. Like a flathead screwdriver. And, like, several people died because someone went oopsie. And they.

Deirdre: They have achieved criticality of the nuclear core, like, twice. I feel like. I feel like we can’t really top that one. Matt, thank you very much for hopping on with us to. To giggle about cryptography and nerds who can’t handle their own keys because apparently we’re all human and handling keys and things like that is still difficult for real human cryptographers to do.

Thomas: Pretty sure that anybody could have gotten this right. Twitter is pretty sure that anybody could have gotten this right.

Deirdre: Anybody? Yeah, Anybody. Yeah, sure. Yeah.

David: Yeah. Yeah.

Deirdre: Cool. No, not. Not yet. Maybe we’ll make it a little easier with threshold, but still we have to figure out how to distribute the keys.

David: No, no, no, no, no, no, no, no, no. No one has ever made anything easy easier by introducing threshold cryptography. Maybe you have at best made something possible, but you haven’t made anything easier.

Deirdre: I yes.

David: No one’s taken an existing thing and been like, you know what would make this easier? Well, I would argue some groups and more people.

Deirdre: I would argue. Yeah. And then yes, because literally it goes from this failure mode, which is if one of one of them is lost, everything’s fucked to if one of them is lost, not everything is fucked, but if two of them are lost, everything’s fucked. And then you have to do all the other stuff of distributing the key shares in the first place. So anyway, thank you, Matt.

The IACR Can't Decrypt with Matt Bernhard

Latest Posts

The IACR Can't Decrypt with Matt Bernhard

Apple’s Memory Integrity Enforcement