What Does Quantum Safety Mean? - QuintessenceLabs

What does Quantum Safety mean, how do we get there, and what does this have to do with Bitcoin?

The Threat that Quantum Computers pose to Cryptography is the “killer app” for Quantum Computing. This topic strangely receives both a lot of attention on one hand, but not enough on the other hand. It receives a lot of attention because big improvements are being made both to the Quantum Computing Hardware, but also to the algorithms threatening our Cryptography fundamentals, and that attracts attention. However it doesn’t receive enough attention in actually addressing this challenge, because sometimes fixing the problem is not as easy as it sounds (and finding a technical solution is the easy part).

There is however no argument that Quantum Computing is on its way and the pace of innovation is staggering (just in the last days, Xanadu raised $32m to build a new photonics based quantum computer and British quantum computing experts moved their HQ to Silicon Valley to raise money to support their mission to (quote) “… develop a large-scale … quantum-computer … based on photons as qubits, with 1 million qubits as its first go-to-market product in five years”)

So, the consensus now, is that Quantum Computers will be a reality, and the debate has moved to the question of when it will occur. Will it be within 5 years as PsiQ believes? Or do we believe the more pessimistic view that it is 15 years out? I’m not going to argue one way or the other, but let’s agree that there is no disagreement that it will happen.

Having said that, let’s now focus on what is needed to bring our current infrastructure to a quantum-safe place. What do we need to do to make our world operate in a safe and coordinated way in the future. We all want to leave this place in a better state than we found it in, so let’s look at what is needed to make this happen.

What do we need to upgrade to become quantum-safe?

Well, it looks like that we literally need to upgrade everything. We basically use cryptography everywhere and we encrypt everything, so there are lots of things we need to look at. A few examples:

• Every IoT device communicates with its parents via a HTTPS connection, which involves cryptography.
• Every piece of data at rest that is encrypted can be harvested today and decrypted once the capabilities are there (applies to databases, bitcoins, cryptocurrencies at large, data dumps, financial records, stolen information, …)
• This area is massive as every single website that collects anything from you has to store it somewhere. Most likely in an encrypted fashion to comply with privacy regulations such as GDPR or California private act, …
• Every internet connection uses cryptography, whether it is a browser-server session (e.g. https), server-to-server protocols (like noise), or VPN tunnels (like IPSEC, OpenVPN)
• Every application communicates to the cloud via TLS (uploads your iCloud photos, or Dropbox, Google, Azure

And these are just some examples, the list is much, much longer.

So, let’s fix it!

If only it were just that easy to do.

To upgrade the fundament of cryptography is like open heart surgery. There is no easy drop-in replacement of Algorithm A for Algorithm B. It is unfortunately quite complicated as every mistake could be fatal. There are three big categories we need to consider

• Technical work
• Operational work
• Social/Economic work

Technical Work

Having always been a techie, I used to believe that once we found a technical solution to a problem, we are kind of “done” (in the sense that we have achieved the hard part and the rest just follows). Unfortunately, I learned over and over again that this isn’t quite true.

The main work that needs to be done here is a thorough review of all the cryptographic functions used in an organization to assess whether they need to be changed at all, when they need to be changed or how they even can be changed.

In 2015, the NSA kicked things off when it announced that it wants to move to new quantum-resistant algorithms and this triggered a whole range of initiatives – including NIST’s Post-Quantum-Cryptography working group, which was setup in 2016 and has been working since then to identify algorithms that can be considered safe from the Threat of Quantum Computing. The list is expected to be finalized in 2022-2023.

This activity underlines a critical fact: we don’t even know today what quantum-safe algorithms we should be using… Although analysis has shown that we “only” need these new algorithms for public-key-cryptography (like RSA or ECC for encryption and digital signatures) and not for symmetric algorithms (like AES encryption) or hashing (like SHA2/SHA3). “Only” is in quotes as PKI is very widespread, used for example in nearly all key exchanges, and is hence an integral part of all our security, affecting maybe 95% of cases.

Outcomes of this workstream may be something like the following:

• Nothing to do. E.g. we assessed the cryptographic operations and we have assessed that we don’t need to do anything (e.g. we are already using algorithms deemed to be quantum safe, such as using AES encryption with longer than typical 256-bit keys.
• We have some incremental work to do, which can happen behind the scenes. E.g. we are using AES encryption with 128-bit keys and we need to increase the key length. In order to do this, we need to update our database scheme to increase the size of the column that holds the keys. Once we have done that, we can run a script over the database to change AES-encryption from 128-bit to 256-bit and change the software to create only 256-bit encrypted fields
• We need to change our PKI infrastructure, but we have assessed that we have plenty of time to do so. Let’s wait until NIST approves a quantum-safe-algorithm and revisit this once this is done.
• We need to change our PKI infrastructure and we need to do something now. E.g. to address the “Harvest now, decrypt later” attack, we simply cannot wait for a replacement to our PKI infrastructure as we need to ensure confidentiality of documents for 20 years, which cannot be guaranteed at the moment. Let’s use a hybrid encryption strategy, where we use the current state-of-the-art encryption (ECC) together with a candidate for a quantum-safe-algorithm. This approach guarantees that the current bar is as high as it previously was (we are still using ECC), but even if that can be broken, we have some additional protection from the quantum-safe alternative candidate. Because the quantum safe alternative is not yet formally approved, let’s develop this in a way where we can replace the algorithm at any time without much fanfare.

Operational work

Let’s assume we have assessed what we need to do from a technical point of view. Let’s look at the operational aspect of this outcome. I alluded to this a little bit already, but this may include things like

• Because the key sizes for the private and public key are larger, can we still store the keys in our database? What operational impacts does this have? Can we still maintain our transaction-per-second ratio and our SLA?
• What is the operation impact of a new encryption scheme? How much slower is it? Is just the average slower or are there special cases to consider? A lot of work is being spent right now on the browser piece of this, with Internet Companies using hybrid signature schemes for HTTPS to test the impact (see e.g. https://blog.cloudflare.com/towards-post-quantum-cryptography-in-tls/ in June 2019, or Google in 2018 https://www.imperialviolet.org/2018/04/11/pqconftls.html)
• What is the impact on the users of my system with this change? For example, for cryptocurrencies, the Coin address is directly derived from the public key. If the public keys changes, the addresses will change too. Bitcoin and Ethereum use 256-bit private keys and because they use Elliptic-Curve-Cryptography, the public key is a point on a curve (represented by 33 bytes in compressed form). Any new algorithm will fundamentally change this, meaning data structures will be invalid, new addresses are needed, … As a result, funds from every single bitcoin address may need to be transferred to a new quantum-safe address. This is a huge undertaking that in most cases threatens the underlying system. What do you do if that’s not possible, such as for all Bitcoins where the private key has been lost? Do you let them expire or leave them laying around for any quantum attacker to collect?

Social/Economic work

So, let’s assume we have worked out all the technical bits and pieces and we have sorted out the operational challenges. What about the implication of this from a larger social and economic point of view? Are there cases where this change would fundamentally alter the use of my system. Could it even be that this change fundamentally threatens my business model?

What about the $10bn USD in Bitcoins that includes Satoshi’s bitcoins? Remember, these Bitcoins have their public keys exposed and a Quantum Computer can derive the private key to it, which will give them full access to them. What impact will it have on the Bitcoin ecosystem when somebody moves these coins? Some Bitcoin purists see it as a “social contract” from the “founders” that these coins will never be spent. Nobody really knows whether Satoshi has even the private keys for them, or whether he threw them away. If these coins end up being spent, how can we know whether it was Satoshi or a rogue Nation State that happily invested $5bn into a Quantum Computer because they’ll get immediately $10bn back? We don’t even know who Satoshi is, so nobody can ask him/her anyways.

And if we have decided in the Operational section that all Bitcoins need to be moved to a Quantum-Safe-Address, how long do we give users to do so? 1 year, 2 years, 5 years, forever? Do we say: You can move it until we believe a Quantum-Computer is viable and then we lock it down? Who decides that? How is this being communicated to the account holders – considering nobody knows how these account holders are? What impact does this have on Bitcoins that are time-locked for many years? Could a smart attacker simply wait until the time-lock expires and then steal them a few seconds before the “real” holder? How can the Bitcoin network even distinguish between the “real holder” and an attacker? Is my crypto-currency obsolete because all the money will be gone? Is my crypto-currency obsolete because smart people moved to another quantum-safe crypto-currency?

All these questions are part of ‘Crypto-Agility’

For those readers that are still with me here, thank you for reading this far 🙂

Everything I described here in this article falls under a phrase that is well known – yet unfortunately not well defined. This article was my attempt to define it in a bit more detail. Everything here is known as “Crypto-Agility”

Crypto-Agility is not just replacing one algorithm with another. It certainly includes that too, but it is much, much more. In virtually all cases where someone says “Well, let’s not worry about this, because we have plenty of time”, they are only looking at one part of the equation (e.g. the technical part) and not about the rest. Crypto agility needs to look at the full picture of technical, operational and socio-economic impacts as described above.

Back to Bitcoin

I’ll close by revisiting the topic of Bitcoin, which is a really interesting use-case and illustration of the broad range of impacts that the quantum threat poses, and of the need for a cohesive, crypt-agile strategy to address them. Bitcoin has established itself as an economic force, but will be sorely challenged by this fundamental threat of quantum computers. There have been some discussions here and there about this topic that range from “there is nothing to do here…”, “Once Quantum-Computers are powerful enough, we simply move to Algorithm XXX“, or “We have lots of time to figure this out“, or “Let’s do it like this… 140 characters of plan… and if somebody doesn’t move their coins, bad luck…“

Clearly none of these strategies are comprehensive or thoughtful enough to really work by themselves. And while I agree that there is time to address this issue, I fundamentally believe that we need to have a Quantum-Safe Manifesto for Bitcoin that clearly outlines the road-map of how this will play out. That includes non-technical items such as how this is communicated, but also commitments to not include new code that hasn’t been reviewed for its quantum-safety and the impact it may have.

There needs to be a consensus between all major players in the Bitcoin ecosystem (such as core developers, miners, wallet providers, users) how this should play out. And that s a challenge, because even just agreeing to a consensus can take years. This work needs to start ASAP as there are “improvements” on the table (such as Schnorr Signature and Taproot), that may or may not be such great improvements in the long run.

For those of us not involved in Bitcoin, now is not the time to relax. The types of issues listed above will challenge many industries, so its time to roll up our sleeves and not just look for technical solutions, but really ask the challenging questions to understand the full potential consequences of this threat, how to deploy operational solutions and limit negative socio-economic impacts.

Andreas Baumhof, Vice President of Quantum Technologies