Quantum-safe communication over the internet infrastructure? Yeah, that’s doable
Shlomi Dolev is the Chair Professor and founder of the Computer Science department of Ben-Gurion University of the Negev. He is the author of Self-Stabilization. Shlomi also is a cybersecurity entrepreneur and the co-founder and chief scientist of Secret Double Octopus.
More posts by this contributor
The quantum meltdown of encryption
The quantum computing apocalypse is imminent
Quantum computing promises to do many things for business and industry, processing data at far greater speeds and rates than today’s binary computers can accomplish. But it also promises to do something else — essentially render current security standards useless, as hackers will be able to utilize quantum systems to crack the cryptographic schemes that are used to protect systems today.
We’re closer than ever to the deployment of a commercial quantum computing system — which means that we need to develop a security scheme that will protect data exchanged between quantum computers on the existing internet infrastructure.
Researchers have developed ideas and theories about how to proceed, but we believe that the basic components of a solution are already out there — and it won’t require the development of new hardware or mechanisms to accomplish. Using a combination of overlay security, blockchain, advanced cryptographic systems and Merkle trees with Lamport signatures, we believe we can develop a practical, inexpensive — and even easy to implement — quantum-safe security system for internet exchanges.
That commercial-grade quantum systems are almost — if not already — here, as at least one quantum system has been sold, and a Maryland firm has recently developed a 79-qubit system. One of the operating principles of qubits — the quantum bits that are the bedrock of quantum computing — is the quantum entanglement that allows quantum gate operations over non-neighboring quantum bits (enabling teleportation of qubits). As a result, operations are completed far faster than in standard bit computers — meaning that, given Shor’s algorithm, hackers should have no problem breaking current security systems. Even without quantum computing, some of the algorithms that were thought to be impenetrable were found to be vulnerable; with the power of qubits at work, the danger is even greater.
The asymmetric encryption schemes proposed by Merkle, Diffie Helman and Rivest and Shamir and Addelman, pioneers in the use of cryptography for computer security, brought about a revolution in cryptography. Asymmetric encryption enabled the creation of a symmetric key among communicating parties in a communication link, and is even able to identify the intervention of a malicious party in the communication. This is possible because these encryption schemes allow for the signature of certificates, monolithically associating a public key with the description of the entity to which the public key belongs. The signature is issued by a trusted third party, the certificate authority. This public key infrastructure is the de facto security infrastructure in use today, securing the entire internet — including sensitive and super-secure communications for the military, government and financial institutions.
Open up your favorite tech website on any given day, though, and you’ll likely find news of a breach — sometimes a big one that compromised the data, finances and livelihood of millions. Clearly, even before the quantum computing era, there is work that needs to be done to shore up the internet.
Overlay security as a model
A model for quantum-safe communications is already in use — in the concept of overlay security, used by many services to secure their communications. Let’s take as an example the sending of credit card information to a web site. Clearly, sending that data in clear-text via a single message is asking for trouble. One alternative would be to send the data via different segments — i.e. sending one email with the first digits of the credit card and then another email with the rest. But savvy hackers could compromise the data on a server, essentially using the email servers and the internet server providers to carry out a man-in-the-middle or “tap in” attack, capturing part of or all the digits of the credit card.
But overlay networks provide a window to a solution. Overlay networks provide “closed” networks utilizing security protocols for services atop an existing network (in this case, the internet). As internet services have proliferated, each one — e-mail, SMS, push notifications, messengers such as WhatsApp, Facebook Messenger, Skype, Snapchat, LINE, LinkedIn, Telegram, Weibo, Slack, etc. — have created their own logical secured channels. Each channel, even if using the same physical infrastructure, is secured in its own overlay, with trust in identification and authentication of communications through the channel taken as a matter of faith.
This overlay system provides what could be a model for quantum-safe communications. If, for example, we were to send part of our credit card data (encrypted, of course) via WhatsApp, and another string via Gmail, we would in essence be reproducing the entangled aspect of quantum communications. In this sense, we are using the overlay network these services provide — with the accumulated secrecy, authenticity and identification of the diverse capabilities of the communication channels, applications and protocols — to ensure security.
With that, there are some flaws with this approach. Overlay security uses several channels and random numbers to obtain a high level of confidence in identification, authentication and secrecy. In a quantum-safe security system, security protocols could be used over each channel that would be part of the encrypted data that needs to be reassembled in order to get at the data. If the channels are known — i.e. if hackers know we are using SMS, e-mail, etc, and in which order to authenticate communications — each of those channels could be compromised, with the communication at the very least blocked.
Secret sharing the secret to Quantum-safe security?
One way around this is with the secret-sharing protocol developed by Professor Adi Shamir, which utilizes a variable number of channels to reconstruct a message, depending on the message. Shamir’s secret sharing is based on using polynomials over a finite field, where each “participant” — in our case each channel — receives one point of the polynomial; the secret is the free coefficient of the polynomial. For example, if the polynomial is a random linear function with the secret being the free coefficient, any two participants/channels can reveal the secret, but no single participant/channel has the information needed to reveal the secret. Following the logic, the more polynomials and the more channels, the more “esoteric” the secret becomes, and the more remote the possibility that a hacker can get at it.
One of the “keys” (pun intended) for the public key infrastructure upon which the authentication systems we rely on are built is the certificate authority. A trusted authority signs off on a certificate that associates a public key with the entity description, thus providing assurances that the entity we are contacting and providing authentication to is indeed the entity we intend to contact, and not a rogue pretender. However, the certificate system is far from perfect, and there have been plenty of compromises (see here, here, here and here) over the years.
One way to bolster authentication is to entrust the verification to blockchains. Combined with secret sharing, blockchains could prove a formidable challenge to even the most talented of hackers.
In a blockchain, the identity of a trusted party would be carried out by numerous already trusted entities, including governmental, financial and notary entities. Each trusted entity would have a portion of the security secret (as described above) in its portion of the ledger; when a user seeks to ascertain the trustworthiness of a service or site that relies on this scheme, the security system searches through the ledger for the required polynomials, enabling the creation of a new random symmetric key that can be used in an advanced encryption standard (AES) authentication scheme over a single channel. Unlike the asymmetric encryption largely used today, AES is considered quantum-safe, and a long-enough key length should be enough to protect the communication from the super-charged quantum hacking software that will be working very quickly (taking into account the quadratic search speed-up implied in Grover’s Algorithm). Along with AES, secure hash algorithms (SHA) are also considered to be quantum-safe.
Finally, we need a way to sign messages and transactions, like financial transactions, in a way that hackers will not be able to compromise. There are numerous signature schemes already in use, including Lamport one-time signatures, which can utilize a secure hash function, such as secure hash algorithms (SHA). Lamport signatures are fine for single-use authentication, but even better are Merkle trees, which include many private keys in the leaves (which also can be produced by several nested hash functions). Those leaves offer infinite possibilities for private keys, with the root of the tree serving as the public key. Distributing that public key over a blockchain ledger would provide even more security — giving even quantum systems a run for their money in trying to guess authentication information.
There’s been much wringing of hands in recent years about the seemingly inevitable Quantum Apocalypse — the end of security as we know it. In a sense, that’s accurate; if we are using standard systems that utilize standard bits and standard security protocols, then yes, quantum systems will probably kill them on the first day their superior computing power is unleashed.
But it doesn’t have to be that way. There are schemes and technologies — overlay, secret sharing, blockchain, advanced signature systems, etc. that can protect communications even over the standard, open internet. Those technologies are not theoretical; they exist, and are in use in some capacity or another right now. By implementing these systems now, we can segue into the quantum computing era with nary a worry.