The so-called Election Administrator’s Prayer has nothing to do with ballot results or even turnout; it’s all about margin: “Lord, let this election not be close.”
The closer a contest is, the more significant any number of possible concerns become — be they the kind of voter manipulation via social-media interference we saw in 2016, or undermined confidence stoked by unfounded claims that vote-by-mail expansion will lead to mass voter fraud.
Microsoft’s new encrypted ballot-verification technology, ElectionGuard, cannot solve either of the above challenges. But it appears to do an effective job of battling at least one potential act of voting sabotage: hacking voting systems to alter votes. It does so by leveraging one of the most buzzed-about, longest-gestating cryptographic schemes in existence: homomorphic encryption.
Why are encrypted ballots important?
In the simplest terms, homomorphic encryption allows computation to be performed on encrypted data, including in cloud environments, and produce an encrypted result, which can then be decrypted, with the end result being the same as if you did math on unencrypted data. Throughout the full cycle, from storage to analysis, the data could be interpreted and never be decrypted. (Think of a person being able to work with material inside a locked glove box, to borrow a metaphor favored by one HE pioneer.)
That portends a genuine breakthrough in privacy-preserving big data analytics, although it still has some growing up to do before it reaches commercial scalability. But when it comes to elections, it’s far closer to primetime.
Here’s what it looks like in a voting context: ElectionGuard encrypts a voter’s choice, then produces a paper ballot to deposit, a paper ballot confirmation and a tracking code. The voter can then enter that tracking number online and confirm that their vote was counted correctly. If their vote had somehow been altered or tampered with, they’d have the receipts. Discrepancies would be readily apparent, and officials would have a back-up of real votes.
Even if only a few voters double-checked their votes, that could go a long way.
“If just 1 percent of voters nationally check that their ballots are correctly encrypted and tallied, it would be almost impossible for anyone to tamper with more than 100 votes out of 100 million without being caught,” wrote Microsoft’s Alex Thornton on the company’s blog.
Of course, the introduction of new tech into the voting process by nature has the potential to raise eyebrows. That fact isn’t lost on Josh Benaloh, Microsoft Research’s senior cryptographer and the visionary behind ElectionGuard.
“The pedagogy of explaining this has always been a challenge,” he told Built In. “There’s mathematics involved, [so] most voters don’t want to hear about it. Certainly putting in electronics where electronics weren’t before might create suspicion, even if we’re putting it in in a verifiable way.”
“Election officials have justifiably gone from an innovation, what-can-we-do-better mindset to more of a preservation, how-can-we-have-a-vote-at-all mindset.”
But the encryption scheme at the heart of ElectionGuard has long been considered a great match for voting security. And it appears to have performed well in its first major rodeo, a test pilot run during the spring primaries in Fulton, Wisconsin, in February. Microsoft didn’t come across any major blind spots, and each voter that used the system was able to verify their vote.
Still, chances are low you’ll see ElectionGuard in your ballot booth in November’s general election. “It’s definitely a longer play,” Benaloh said. The hope was to have more pilots in 2020. That might still happen, but it’s not likely.
“Election officials have justifiably gone from an innovation, what-can-we-do-better mindset to more of a preservation, how-can-we-have-a-vote-at-all mindset,” he said.
A Better Way to Do Ballot Comparison
That’s not to say ElectionGuard and homomorphic encryption will be completely sidelined in November. The same HE scheme that underpins the confirmation system for the voter can also help election officials verify votes on their end.
After elections, officials perform risk-limiting auditing to ensure that physical ballots correspond to tallies. That includes a process called ballot comparison, wherein officials compare a number of randomly chosen individual ballots with an electronic record of ballots. That electronic record needs to be — to some degree — public-facing, to inspire voter confidence. But ballots show patterns, which means even an anonymized record is not secure enough.
ElectionGuard’s homomorphic encryption can bridge that gap. “We can encrypt the electronic records in exactly the same way they’re encrypted for end-to-end verifiability during the vote, release the encryptions, and release a proof that these encryptions matched the announced tallies,” Benaloh explained. “Anytime a ballot is audited, we can open the encryption on that ballot and show that [the plain text] matches.”
It’s not the most exciting manifestation of ElectionGuard, Benaloh lamented. That would be the individual, voter-facing verification system — and even that has hurdles to overcome, particularly for vote-by-mail. But it’s a promising step and a noteworthy achievement for a researcher who’s devoted his professional life to election cryptography. (ElectionGuard is, in effect, a maturation of Benaloh’s 1987 thesis, and he studied under Ron Rivest — the R in RSA — who has also worked extensively in election-focused cryptography.)
And even a qualified win is notable, considering our non-nationalized election infrastructure infamously runs on such thin financial margins.
“Asking election equipment vendors to spend any extra money [on innovation] when they’re basically [constantly] retooling their solution because every jurisdiction is difficult,” he said. “It’s a hard ask for anybody.”
A Brief History of Homomorphic Encryption
One of the reasons homomorphic encryption is such a hand-in-glove fit for election security is because, at its core, voting tabulation is straightforward. It’s just addition. ElectionGuard is an example of simple homomorphic encryption. Fully homomorphic encryption combines addition capabilities with multiplication capabilities. But even just those two primitives together have big consequences.
“It’s the only type of encryption that gives you those two properties, which is why it’s often considered to be the Holy Grail of cryptography,” said Ellison Anne Williams, a former National Security Agency cryptographer who in 2016 founded Enveil, which focuses on bringing HE to the commercial sector.
Getting to that point was a long time coming. Simple HE has been around for more than 40 years, nearly since the arrival of RSA. “For years, people said, well, this multiplication-only doesn’t have a lot of applications. Addition has a few, but it’d be really nice if we could do both at the same time. And people looked at it and said, ‘yeah, but that’s probably not possible,’ and sort of swept it away.”
“It definitely is reaching — and has reached in many use cases — that level of maturity and commercial readiness, having been computationally impractical for the better part of 30 years before.”
Then in 2009, cryptographer Craig Gentry finally successfully bridged the two and constructed the first fully homomorphic encryption scheme. It didn’t take long for dreams of computing and analyzing encrypted data on commercial clouds to rev up again, and Gentry was awarded a MacArthur Genius grant for his groundbreaking research a few years later.
But even though Gentry had proven FHE was possible, it was still far from practical — a computation under Gentry’s 2009 scheme would have taken some trillion times longer than the same computation on unencrypted data. That “absurd” time overhead has come down some in the years since, from around 1025 to around 108 or 107 in some cases, according to Benaloh. Better, but still not practical.
The Commercial Angle
Despite the challenges, homomorphic encryption research is already finding its way to the commercial sector. At the aforementioned Enveil, Williams (left) has brought the expertise she refined at the NSA, where she researched encrypted search, mainly to finance. The company is also exploring healthcare and other industries with heavy privacy regulations. (Genomics analytics has attracted notable attention from homomorphic encryption researchers.)
At the center of Enveil’s services is the company’s API-based software, which, as Williams explains, sits atop an organization’s data at rest and data in transit and allows for some encrypted search and encrypted analytics — sometimes over encrypted data, sometimes over unencrypted data.
“We can take those searches or those analytics or those machine learning models, encrypt them, and then go run them anywhere our software is installed without ever decrypting them at any point during processing,” she said. “That’s powered by homomorphic encryption.”
The secure-data-sharing aspect has applications in fighting money laundering, and in customer due diligence when financial services companies vet and verify new customers. A bank in the midst of these processes could securely gather data from banks in other jurisdictions or within its organization but across national lines, which would otherwise be impossible given privacy rules.
That’s essentially what Enveil demonstrated at a couple of tech sprint victories last year, when it ran an encrypted query across three banks in different jurisdictions to modify a risk score in a few seconds, “which is unbelievable for homomorphic encryption return,” said Williams, whose company’s investors include MasterCard and Capital One Growth Ventures.
“It definitely is reaching — and has reached in many use cases — that level of maturity and commercial readiness, having been computationally impractical for the better part of 30 years before,” she said.
Ever-More Open-Source Libraries
In recent years, there’s also been a steady drip of open-source toolkits and libraries intended to get early adopter developers experimenting with fully homomorphic encryption. Those include Microsoft’s SEAL and OpenMined’s SEAL extension, TenSEAL, aimed at bringing homomorphic encryption to machine learning tensor operations. Last year Julia outlined a handwriting-recognition ML model using homomorphic encryption. And just this month IBM unveiled its HE toolkit for MacOS and iOS development.
The fact that IBM’s toolkit was greeted with a mix of excitement and trepidation is perhaps emblematic of where things currently stand, especially in terms of general purpose fully homomorphic encryption. That remains “almost never practical,” but more and more specialized problems can be shoehorned in, Benaloh said. The trick involves structuring computation as much as possible toward addition and away from multiplication.
“But that’s not general purpose; that’s case to case,” Benaloh said.
Simpler computations — think addition, averages, linear and close-to-linear — are the present-day sweet spot on the way to, “as they put it — aptly I think — the Holy Grail,” he said.
In the meantime, working toward more secure elections will have to suffice.