Programming Quantum Computers: Encryption Algorithms

[Bruce Alspaugh]

I have a question for the book authors. Which encryption algorithms in common use today will be effectively broken once powerful enough quantum computers become available? Will RSA, Blowfish, AES, SSL or SSH be broken? Will Bitcoin be broken?

Bruce

[Campbell Ritchie]

Bruce Alspaugh wrote:. . . . Which encryption algorithms in common use today will be effectively broken . . .

I thought all encryption would be broken by any quantum computations.

[Stephan van Hulst]

Everything.

Pretty much all crypto algorithms in use today depend on the assumption that there are mathematical problems that are hard to solve, but have solutions that are easy to verify. This is known as the famous P = NP question.

Quantum computers cheat. When you have a loop, you can imagine a quantum computer being capable of running every loop iteration at the same time, instead of one after the other. That means they can easily find solutions to Euler's totient function, the elliptic curve problem, or can easily prime factorize large numbers. These are problems that all crypto algorithms you know are based on.

To thwart quantum computers, we need quantum encryption algorithms.

Update: I've learned a little bit more about quantum computing since wtiting the post above.

Quantum computers do NOT break all conventional cryptographic algorithms. Yes, they can solve discrete logarithm and prime factorization problems quickly, which means an algorithm like RSA is out, but they aren't better than a plain old classical computer at solving all classes of problems. In particular, they don't run "every loop iteration at the same time".

An algorithm like AES-256 should still be safe, because it is based on pseudo-random permutation, which is not something that quantum computers excel at.

Off the top of my head, I can't currently think of any asymmetric encryption algorithms that are quantum resistant, although I'm sure they're there or in development. Something with vector fields of very high dimensions.

[Mainak Biswas]

Campbell Ritchie wrote:

Bruce Alspaugh wrote:. . . . Which encryption algorithms in common use today will be effectively broken . . .

I thought all encryption would be broken by any quantum computations.

while this is true, there would quantum encryption coming up

[Campbell Ritchie]

Stephan van Hulst wrote:. . . mathematical problems that are hard to solve . . ..

What would a quantum computer make of something like calculating Graham's Number?

[Stephan van Hulst]

Hard in this context literally means that the run time can be expressed as a polynomial when the problem is solved by a non-deterministic finite automaton. I don't know how quantum computers perform on problems that classically require exponential run time, and I also don't know in what category calculating Graham's number falls.

It would be moot anyway, because you wouldn't be able to print out the answer.

[Campbell Ritchie]

You mean I would need a whole molecule to store Graham's Number?
Let's see what the book's authors have to say about it.

[Ivan Jozsef Balazs]

Campbell Ritchie wrote:I thought all encryption would be broken by any quantum computations.

Well, maybe not forcibly *all* encryption would be broken by *any* quantum computation.

[E Johnston]

Aaaaah nice. It makes me happy that the first question posted is the hardest. Or rather, one can hope that's the case. :]
(These comments are mine; I'll be taking point this week, relaying these questions to the other two authors, who are traveling.)

This is a giant topic of ongoing research (of course). While I can't provide a direct and simple answer to Bruce's original question, the following notes may help you to think about the issue and explore it a bit. I'll start by hitting some of the top-line issues you've raised, and see where we go from there.

FT vs. Raw Qubits: I tend to assume that serious codebreaking algorithms (ones which actually break encryption we care about) will require error-corrected fault-tolerant QPUs (Quantum Processing Units), just as serious computing applications require reliable RAM. I may be wrong in this; Craig Gidney and Martin Ekerå published a paper in May this year entitled How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. FT machines don't exist yet (they will), and 20M-qubit machines don't exist yet either. The state of the art today is 53-70 noisy qubits. Although the code samples in our book do run on present-day QPUs, the book is written primarily with upcoming FT machines in mind.

Factoring vs. Logic Search: A lot of emphasis is placed on Shor's Factoring Algorithm (chapter 12 in the book, code sample here), however (just my personal view) I think people tend to overlook generalized logic reversal. As Stephan mentioned, most crypto is built on digital math (such as multiplication) which is easy to do forward and difficult to do in reverse. All QPUs (including both gate-based systems like the IBM Q, and annealers like D-Wave's machine), can take classical forward logic functions and with some efficiency determine the inputs, given the outputs (there are really fun examples of this in chapter 10 in the book, code sample here). The strength of this is that it's more general than factoring, and still demonstrates a quantum advantage.

Quantum Encryption: Of course as Mainak mentions, the new forms of encryption introduced by QPUs (QKD, uncopyable data, etc) are very interesting as well, primarily because they're based on physical properties of information itself, not on math problems (code sample: "Spy Hunter" in chapter 2, here).

Bitcoin: In an effort to form my own opinions on this, I recently picked up Programming Bitcoin by Jimmy Song. It's the Bitcoin hands-on programmer's equivalent of our book, with a good explanation of elliptical encryption, proof-of-work, etc. I used Jimmy's book side-by-side with ours; I was doubtless re-treading existing research, but for me that was the right way to explore the problem.

None of this answers your question directly, but hopefully it gives you some starting material for thinking about the issue.

[E Johnston]

Also, this is really good timing, just today: https://www.scientificamerican.com/article/new-encryption-system-protects-data-from-quantum-computers/

[Frank Röber]

Mainak Biswas wrote:

Campbell Ritchie wrote:

Bruce Alspaugh wrote:. . . . Which encryption algorithms in common use today will be effectively broken . . .

I thought all encryption would be broken by any quantum computations.

while this is true, there would quantum encryption coming up

To my knowledge, quantum encryption is not the answer to that problem. It's actually not a method to encrypt a payload of a reasonable size, but a procedure to transport a little secret physically to another location, e.g. by entangled photons. This secret is currently meant to be a symmetric key like AESS.

Some months ago I listened to a talk of a french QC scientist who told us that, yes, there is currently a known QC-algorithm to break AESS, but they expect only a speed-up of factor two compared to current super computers. So his recommendation was: Simply double the length of your AESS keys! And, yes, get rid of RSA...

[Aldiyar Chirock]

Quantum computing poses some interesting challenges for encryption algorithms. RSA and some symmetric encryption like AES might become vulnerable due to their reliance on factorization and discrete logarithm problems, which quantum computers excel at.

[Stephan van Hulst]

Aldiyar Chirock wrote:some symmetric encryption like AES might become vulnerable due to their reliance on factorization and discrete logarithm problems

Except AES doesn't rely on the difficulty of prime factorization or solving the discrete logarithm, meaning AES is conceptually safe against quantum computing, assuming you use a large enough key size.