The Holy Grail of Encryption Can Help Secure Elections And That’s Just the Beginning – Built In

The so-called Election Administrators Prayer has nothing to do with ballot results or even turnout; its 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.

Microsofts new vote-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.

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, its far closer to primetime.

Heres what it looks like in a voting context: ElectionGuard encrypts a voters 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, theyd have the receipts. Discrepancies would be readily apparent, and officials would have a backup of real votes.

Even if only a few voters double-checked their votes, that could go a long way.

If just one 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 Microsofts Alex Thornton on the companys blog.

Of course, the introduction of new tech into the voting process by nature has the potential to raise eyebrows. That fact isnt lost on Josh Benaloh, Microsoft Researchs senior cryptographer and the visionary behind ElectionGuard.

The pedagogy of explaining this has always been a challenge, he told Built In. Theres mathematics involved, [so] most voters dont want to hear about it. Certainly putting in electronics where electronics werent before might create suspicion, even if were putting it in ina 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 didnt come across any major blind spots, and each voter that used the system was able to verify their vote.

Still, chances are low youll see ElectionGuard in your ballot booth in Novembers general election. Its definitely a longer play, Benaloh said. The hope was to have more pilots in 2020. That might still happen, but its 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.

RelatedA Tech Companys Guide to Deleting Personal Identifying Information

Thats 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.

ElectionGuards homomorphic encryption can bridge that gap. We can encrypt the electronic records in exactly the same way theyre 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.

Its 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 its a promising step and a noteworthy achievement for a researcher whos devoted his professional life to election cryptography. (ElectionGuard is, in effect, a maturation of Benalohs 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 theyre basically [constantly] retooling their solution because every jurisdiction is difficult, he said. Its a hard ask for anybody.

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. Its 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.

Its the only type of encryption that gives you those two properties, which is why its often considered to be the Holy Grail of cryptography, said Ellison Anne Williams, a former NSA 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 doesnt have a lot of applications. Addition has a few, but itd be really nice if we could do both at the same time. And people looked at it and said, yeah, but thats 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 didnt 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 Gentrys 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.

RelatedIs Noisy Data Good Now? Differential Privacy Proponents Think So.

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 Enveils services is the companys API-based software, which, as Williams explains, sits atop an organizations 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. Thats 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.

Thats 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 companys 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.

In recent years, theres also been a steady drip of open-source toolkits and libraries intended to get early-adopter developers experimenting with fully homomorphic encryption. Those include Microsofts SEAL and OpenMineds 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 IBMs 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 thats not general purpose; thats 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.

RelatedYour Checklist for Switching to Kubernetes

More:
The Holy Grail of Encryption Can Help Secure Elections And That's Just the Beginning - Built In