Who owns data? Who can read which data? At the center of some of the most vexing problems confronting the internet are a set of encryption algorithms that hold everything together. The routines are mathematically complex and often difficult for even the experts to understand, but stopping fraud, protecting privacy and ensuring accuracy depend implicitly on everyone getting those algorithms right.
Their role in governing cyberspace attracts plenty of researchers who are trying to improve them while also attempting to reveal their weaknesses by breaking them. Some of the newest approaches offer new opportunities to protect everyone with more sophisticated protocols and more robust algorithms. The newest tools bundle better privacy and more agile applications that will do a better job withstanding attacks, including those that might be launched using the largely hypothetical quantum computers.
The burgeoning world of cryptocurrencies is also creating opportunities in securing not just money and transactions but all stages of digital workflow. The exploration and innovation devoted to creating blockchains for immortalizing all interactions are some of the most creative and intense areas of computer science today.
The good news is that for all this exciting innovation, the core foundations remain remarkably stable, strong and secure — as long as care is taken implementing them. The standards last decades making it possible for enterprises to rely upon them without recoding or redesigning protocols very often.
The standard algorithms like the Secure Hash Algorithm (SHA) and the Advanced Encryption Standard (AES) were designed with careful public competitions managed by the National Institute of Standards and Technology (NIST), and the result has been remarkably resistant to endless public attacks. While some of these have grown a bit weak thanks to the progress of technology — SHA1, for instance, should be deprecated and replaced with SHA256 — there are no catastrophic collapses in security to report.
Quantum resistant encryption
The fears of something breaking the protocols and algorithms wide open, though, drive the push to harden the algorithms against attacks that might come from quantum computers in the future. A big push from NIST is aimed at creating a new collection of “quantum resistant” or “post quantum” algorithms with a competition that is unfolding right now.
Last summer, NIST announced the beginning of the third round of a competition that started at the end of 2016. Sixty-nine different algorithms began the process and the list was winnowed to first 26 algorithms and now 15. Of these 15, seven are called the “finalists” and the other eight are alternatives that are aimed at niche applications or are still being studied because they, according to the announcement, “might need more time to mature.”
The selection process is difficult because the researchers are trying to imagine attacks that might come from machines that don’t exist, at least at a useful scale. The RSA digital signature algorithm, for instance, might be broken by a successful factoring of a large number. In 2012, researchers reported success in using a quantum computer to split 21 into the product of 7 and 3, two numbers that aren’t particularly large. Many assume it will take a long time to develop enough precision to successfully factor longer numbers and it seems that many of the standards like RSA are threatened more by easily accessible cloud computing than hypothetical quantum machines.
Much of the focus in the contest is on algorithms that are resistant to Shor’s algorithm, the most commonly described way for quantum computers to attack algorithms like RSA. The publicly announced quantum machines take many different forms, and no one knows if other algorithms or designs may appear.
Still, for all the uncertainty, researchers are finding that some of the quantum resistant designs may still be useful even if the quantum attacks never reach fruition. Paul Kocher, a cryptographer, said in an interview that digital signatures based on hash functions can be easy to deploy in both dedicated hardware and software environments that must run with underpowered processors. “Verification requires only a tiny state machine and hash function, making them nicely suited to hardware implementation,” he said, adding that the approach’s “robustness against quantum computers is simply based on the hash function, rather than all the other quantum-safe algorithms which involve new math.”
NIST said that the final round may take a bit longer because of delays from the pandemic, but they hope to announce new standard algorithms for encryption and digital signatures in 2022.
Homomorphic encryption
Another big push by researchers is working directly with encrypted data without requiring access to a key. More and more information lives in cloud machines that may not be as trustworthy as those located on-premises. If the data is never unscrambled while the algorithms work, secrets can be preserved but work can be distributed to untrusted machines.
It’s been possible to do a limited number of operations on encrypted information for some time. Chapter 14 of my book Translucent Databases, for instance, describes very basic systems that can support addition but not multiplication or vice-versa.
Interest exploded in the last decade thanks to the announcement of algorithms that can apply a wider range of operations. The first round of what some call “functional encryption” or “fully homomorphic encryption,” though, have been so computationally expensive that they aren’t usable for common work. Basic computations could take days, weeks or months.
The effort is paying off, however, and now practical implementations are appearing. IBM, for instance, released its Fully Homomorphic Encryption toolkit for MacOS, iOS, Android and Linux this summer. The code includes examples for privacy-preserving searches of bank records to prevent fraud.
Microsoft released its own library using a different approach that is best for mixing addition and multiplication operations but not searches. It might be used in accounting applications, but not those that require searching through the data for matches.
Differential privacy
Another approach called differential privacy is often lumped together with encryption because it shares a goal of protecting personal information. The underlying mathematics, though, are different because the tool offers only statistical guarantees of privacy by adding just enough noise to the data to make it difficult to connect data elements with their owners. The data is not locked in a safe but lost in a sea of noise. Users can be happy because their information will probably be safe using limits that are bounded by statistics.
Both Microsoft and Google have recently released open-source toolkits for anyone who wants to experiment with the algorithms. Microsoft’s core tools has samples explaining the best way to produce privacy protecting reports from SQL-based data sources. They’ve also begun to add the tools for adding these features to data stored and analyzed in Azure.
Google’s libraries can deliver basic statistical results from a data source by counting elements and computing a mean and standard deviation. The most feature rich version is implemented in C++, but they are porting the various functions to Java and Go.
One of the most high-profile applications for differential privacy is run by the US Census Bureau, which plans to release statistical summaries of the nation after the full count is completed. The bureau must balance a tradition of protecting the privacy of citizens with the desire for communities and companies to use the data for planning. They were one of the first to start building production applications and they aim to use the algorithms on the results of the 2020 Census.
"In 2008, we were the first organization worldwide to take the concept of differential privacy from theory into practice for one of our data products," says the Census Bureau's chief scientist John M. Abowd. "Since that time, it's become more apparent that the old privacy protection systems are no match for today’s digital, data-rich world. That's why tech giants like Microsoft, Apple and Google are using differential privacy, which is built to protect against these kinds of threats. And it's why more and more companies with identifiable information to protect are turning to this solution every day."
Blockchains
One of the hottest corners of cryptographic research are the various virtual currencies like Bitcoin or Ethereum and the blockchains that govern them. These naturally rely heavily upon cryptographic algorithms and many of the companies developing currencies or governance mechanisms are looking for novel ways to push the various algorithms. Some want to build casinos and others want to create venture investing funds. Everyone wants to find the best ways to leverage the mathematical power of the algorithms to create business systems that everyone can trust.
One of the most active focuses is adding layers of privacy by mixing in zero-knowledge proofs into the blockchain. The earliest protocols used basic digital signatures to authenticate transactions, a feature that linked together all transactions signed with the same key. Lately much more efficient versions of zero-knowledge proofs with names like ZK-Snark have been developed that make it possible to confirm a transaction without revealing any information about your identity. Tools like Zokrates are just one example of how developers are integrating extra privacy and authentication into the blockchains.
Developers want to engineer a new generation of products that do more than just sit there. The earliest blockchains simply tracked ownership. The newest ones add software layers to build elaborate contracts allowing sophisticated workflows that track modern supply chains. Some of the coins or tokens can pay interest and track real world assets.
David Chaum, one of the original developers of anonymous digital cash, believes that we’re just beginning to understand what we can do with the math. The algorithms will take over more and more aspects of life while increasing the level of trust and security. “Secrets have long been key to power.” he says. “This kind of cryptographic infrastructure is not just a better old thing, it’s a really new thing. A new world, by and for us, in which to flourish.”