This week's book giveaway is in the Java in General forum. We're giving away four copies of Beginning Java 17 Fundamentals: Object-Oriented Programming in Java 17 and have ishori Sharan & Adam L Davis on-line! See this thread for details.
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?
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.
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.
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.
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...
WHAT is your favorite color? Blue, no yellow, ahhhhhhh! Tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop