Margin of Safety #36: Quantum and Cryptography

Let's talk about post-quantum security

Detour: This week, we’re going to outline why people keep talking about quantum computing and post- quantum security instead of AI. If you’re curious to learn more, read on! If not, come back next week.

Also, an update thanks to the inimitable Neil Costigan: We called out forward secrecy as the major driver for current post-quantum security initiatives. We should have also mentioned that owners of hardware systems with baked-in cryptographic protocols need to be thinking about rollout timing now, because such systems can live for decades and be hard to update! But it may be wiser to focus on generic update capabilities, because the security community regularly needs to update its set of permissible cryptographic protocols due to discovered vulnerabilities.

Source: Google

To get into the quantum weeds, we first need to outline some high-level cryptography. Beyond its role in cool movies, cryptography and public-key cryptography in particular are fundamental to cybersecurity. We use public certificates and signing for everything from verifying the identity of remote servers to confirming that a distributed binary is unmodified, and encryption protocols are the reason why your credit card can’t be siphoned off the wire every time you buy something online. At a high level, these capabilities all rely on public key cryptography and “trapdoor functions.” A trapdoor function is something that’s easy to compute in one direction, but only computationally feasible to undo if you know a secret (the thing contained in the private key). This makes it so anyone can perform an operation in one direction – like encryption or verification – but only the person with the right private key can perform the corresponding inverse operation – like decryption or signing.

Classically, to find a reliable source of secrets, cryptography turned to integer factorization: it turns out there are classes of math problems involving large numbers that are easy if and only if you know the prime factors of those numbers. Factorization, in turn, turns out to be very hard for silicon computers. But multiplication is grade-school level easy! This is the core of our traditional trapdoor functions. By picking two random, large prime numbers and multiplying them together, people can generate a number N where only they know the factorization. This factorization becomes the private key¹ while the multiplied result is a public key.

That leads us to quantum computers. Quantum computers are generally not more useful than classical computers. They’re harder to maintain, require super cold temperatures, can’t currently be mass produced... but they have massive potential in a few very specific domains, especially:

1. Helping smart students get PhDs and then cool post-docs, in part to expand this list

2. Predicting quantum effects, which are meaningful for many nano-scale processes (drug development, material science, silicon manufacture, etc.)

3. Factoring large numbers, thanks to Shor’s algorithm.

There are a few more domains, but we think they’re relatively niche: for example, quantum effects allow creation of secure communication channels in which anyone attempting to snoop on the channel is easy to detect. But such channels rely on first having exchanged traditional symmetric cryptographic keys, so we view them as valuable but not revolutionary for most workloads.

Within the set of computational problems quantum computers are good at, there are two categories of strength: quantum supremacy, in which a quantum computer can do something that’s basically impossible for a transistor-based supercomputer (factoring a sufficiently large number would fall into this bucket) and hard quantum advantage, in which a quantum computer can do something dramatically cheaper than a classical machine. Google’s recent announcement is more of the latter: using a quantum computer, Google was able to produce a dramatic efficiency improvement in our ability to calculate nano-scale molecular properties. Because even state of the art quantum computers only have a handful of quantum bits (‘qbits’), Google’s calculations were necessarily on a small molecule; some of that size could have also been simulated with a few years of classical supercomputer time. But as quantum computers slowly scale, this result could potentially also scale to molecules that are too complex to ever be simulated with silicon-based computers.

The question for security is similar; when will quantum computers become large enough to factor cryptographically significant numbers? This date is sometimes referred to as Q-Day, though we are suspicious of Q-Day for several reasons. The first is that different systems use different size cryptographic keys, which can imply significant variation in the size of the number that needs to be factored. Bigger numbers will require bigger quantum computers, and as a result their Q-Day will come later. That said, estimates for the date at which quantum computers become a threat to some modern cryptographic implementations often fall in the 2030s or 2040s, with significant uncertainty. The second, more important reason is that of forward secrecy.

Forward secrecy refers to the concept that encrypted data captured and saved now cannot be decrypted in the future. You can imagine this is more important for some use cases than others. Your credit card number, for example, has 0 need of forward secrecy beyond its expiration date²! On the other hand, nation states may want the ability to maintain classified information on 50+ year time horizons; this implies a tremendous need for forward secrecy of any information that can be captured and logged in its encrypted form. This difference in underlying need is why we’ve seen such specific interest in post-quantum cryptography from military and federal sources; if you think there’s a chance of quantum computers being able to factor large numbers in the next 15 years but you want 20+ years of forward secrecy, you need to be using cryptographic schemes that don’t depend on factorization today³. This becomes even more of a concern when you start to assume that nation states may be highly motivated to invest in quantum computing for offensive crypto, and also that they are unlikely to announce when they have achieved sufficient capability to attack current public key systems. Civilians are unlikely to have good information on the current quantum capabilities of the NSA or the PLA.

So what does this mean for investors or practitioners? For practitioners, we think the answer is relatively straightforward; the more you are worried about long term forward secrecy and the more your threat model involves state actors, the sooner you should look to roll out post-quantum algorithms across your tech stack (and demand them of your vendors). The more cryptography is serving to protect things like credit card numbers, which are naturally expiring, the more runway you should expect to have. From the investor PoV, we think there’s ample evidence of the future value of quantum computing, but we expect any inflection points in value to be contingent on quantum reaching the scale to broadly move the economic needle for one or more areas, be those cryptographic, nano-scale manufacturing, or other.

The big open question is when those inflection points will come. For cybersecurity, we expect inflection points to be driven by the risk and uncertainty tolerance of individual use cases – how much are they willing to tolerate a .1% chance of Q-Day in the next 15 years? A 5% chance in the next 20 years? Exacerbating this uncertainty is the fact that AI will likely help with the design of quantum computers, but we don’t yet know how by how much. And in practical terms, there are probably more unknown unknowns in what it will take to scale a cryptographically significant quantum system than there are known ones – this makes predictions for the level of AI-driven technological acceleration we’ll see especially challenging (and supports the real possibility that good old fashioned human genius, like we’ve recently seen in results from Caltech and Harvard/MIT, ends up being a major factor). That said, we think there’s clear evidence that some workloads, especially federal, are already hitting their tipping points⁴, and the potential for other segments to hit theirs in the coming single digit years.

If you agree, disagree, or have your own predictions for when quantum will hit that scale, we’d love to know what you’re thinking.

1. Technically, sometimes the private key is a more-convenient derivation of the factorization. But it’s something that’s roughly equivalent, and you can reasonably think of the private key for this class of functions as representing someone’s knowledge of how to factor the public key.

2. Though depending on your level of privacy sensitivity, you may quite reasonably desire longer term forward secrecy for your purchase history – or the shipping address associated with it.

3. Technically, you needed to be using them 5 years ago…

4. Current US legislation is proposing that key federal systems begin transitioning to quantum resistant cryptograph by 2027, with the EU targeting a full migration of critical infrastructure by 2030. Because these sorts of migrations take time, EU member states will need to begin work ASAP to hit a 2030 goal.