This week's book giveaway is in the Artificial Intelligence and Machine Learning forum.
We're giving away four copies of Machine Learning with R: Expert techniques for predictive modeling and have Brett Lantz on-line!
See this thread for details.
Win a copy of Machine Learning with R: Expert techniques for predictive modeling this week in the Artificial Intelligence and Machine Learning forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Junilu Lacar
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Ganesh Patekar

Programming Quantum Computers: Encryption Algorithms

 
Greenhorn
Posts: 28
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Marshal
Posts: 65821
250
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.
 
Saloon Keeper
Posts: 10675
228
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Author
Posts: 44
7
MyEclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Marshal
Posts: 65821
250
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Saloon Keeper
Posts: 10675
228
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 65821
250
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Rancher
Posts: 1041
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.
 
Author
Posts: 28
10
C++
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Author
Posts: 28
10
C++
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also, this is really good timing, just today: https://www.scientificamerican.com/article/new-encryption-system-protects-data-from-quantum-computers/
 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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...
 
Onion rings are vegetable donuts. Taste this tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!