Slashdot Mirror
Quantum Computing Not an Imminent Threat To Public Encryption
Bruce Schneier's latest blog entry points out an interesting analysis of how quantum computing will affect public encryption. The author takes a look at some of the mathematics involved with using a quantum computer to run a factoring algorithm, and makes some reasonable assumptions about the technological constraints faced by the developers of the technology. He concludes that while quantum computing could be a threat to modern encryption, it is not the dire emergency some researchers suggest.
While I'm critical of Schneier's work in general security consulting, he is still a god in the cryptography world. His book Practical Cryptography is a friendly guide to encryption that doesn't assume too much knowledge of the heady math involved. Plus, the man invented Blowfish, one of the most popular and fast algorithms around.
The day PKIs that use factoring or discrete logs become easy to crack is the day when there's going to be a lot of tremendous amount of money spent on stop-gap security measures until someone figures out something new...
Am I part of the core demographic for Swedish Fish?
loser....
quantum computers fail at NP-hard problems. But no one has made a cryptosystem for which breaking is NP-hard. So the eventual transition is going to be a bit tricky.
Inventions have long since reached their limit, and I see no hope for further development.-- Frontinus, 1st cent. AD
There's a whole class of algorithms for which quantum cryptography isn't very useful.
Those based around multivariate systems of equations (e.g. HFE), coding theory (McEliece and friends) and other esoteric stuff like lattice based systems (NTRU) are pretty much immune to quantum approaches.
It's just a matter of changing the whole infrastructure to something else, not the end of the world.
I think the fear is that by the time we get around to having decent PKI for stuff like credit cards etc, quantum computing will bust everything wide open. PKI is the only practical method of identity management these days, and while algorithms in the PKI are being tweaked, they are all pretty much based on the same principals, which quantum computing is a real threat too.
you disconnect it. First posts are encrypted by mod down, taken out of sight.
The best encryption is disconnection. Its unbreakable even by quantum computers to the nth power.
the next best is perhaps a sequence of seemingly unrelated actions followed by a false positive... or other such use of seemingly unrelated data/actions.
A few might remember the seemingly different things you could do to cause a developer hidden message to come up on the Amiga.
This calculation illustrates a good point about the difference between asymptotic analysis of algorithms and real-world implementation of the same algorithsm. Computer science defines "efficient" as "bounded polynomially in terms of the input size". In practice, even if polynomial has a small degree (like a cubic) it already means that the resource rquirements are very large. Theory and practice are only the same in theory.
...the rate of increase of power of quantum computers isn't faster than Moore's law. I've written more on this here.
-- SIGFPE
Are these shorts in question fruity?
To multiply 2 numbers together to get a k bit product takes a gate count proportional to k**2.
If you built a multiplyer out of magic logic,
and constrained the output and enough of the input bits so that there is only one solution,
then maybe the magic logic could figure out the rest of the multiplyer state.
I don't know if quantum logic can/will be the magic logic,
but as long as we choose algorithms with only one solution,
we will have to worry about it.
Well, even if it were to be true that quantum computing algos can break the existing encryption algos, I think it is being paranoid for two reasons: (1) Quantum computing is not yet mainstream and I doubt if mischief mongers (aka thieves who wish to break into financial sustems) have the wherewithal today to work with quantum computing algos, and (2) By the time QC moves to anywhere near mainstream, I have little doubt that encryption methods would have handsomely moved along too.
nTru has signing and encryption algorithms based on the shortest vector problem, which I believe is NP-hard. I don't know if they have a reductionist proof, or if its just based on SVP like RSA is based on factoring. But, they're probably the way to go if someone were to develop a working quantum computer tomorrow.
Can somebody with physics background help me? For quantum computers to work you need entanglement and Heisenberg principle.
1. Entanglement. Is this a fact or a theory? Looking on web I found only few experiments with some possible loopholes. I found the principle hard to grok.
2. Heisenberg principle. It mainly states that observing an object you are changing the state of the object. The Heisenberg example from wikipedia is using a photon for measuring the position of an electron and the photon is changing the position of electron. What is happening if you are using a smaller particle that is not impacting the electron so much? Are you going to change the constant? Looks mostly like a limitation from a time when the atom was considered to be indivisible.
I have some background in learning physics in university but I was not very good at it. My personal opinion is that superposition is just a nice way of doing statistics using discrete values for covering the not so discrete results of experiments.
Presumably the article is alluding to Shor's Alorithm, which is a a method to factorize integers which uses quantum computation to yield a worst-case complexity significantly better than any existing deterministic methods.
If that's the case, it's probably worthwhile to discuss Pollard's Rho algorithm, which has a poorly understood worst-case complexity (as a Monte Carlo method), but has a potential average case complexity that is comparable to the quantum.
wow, this is just like my comment in the last quantum computing FUD artcile. You've still got bus speeds, cache speeds, memory speeds and capacity, and even hard drive speeds. You're not gonna crack some encryption that would take a normal computer 100 billion years but you might be able to render and encode Finding Nemo a lot faster.
Google's Super Secret Search Algorithm: SELECT @search_results FROM internet WHERE @search_results = 'good'
What I get out of the article is that he seems to be saying that quantum encryption technology that could effectively factor numbers of the size we use for effective public key cryptography is far enough off that it isn't going to be a problem anytime soon. But isn't that reasoning just postponing, rather than actually dealing with the problem?
File under 'M' for 'Manic ranting'
It appears from the first comment on the post that it's likely that this post isn't really accurate. Shor's factoring algorithm is O(k) in number of qbits and O(k^3) in number of operations. This doesn't mean that the number of gates in the quantum computer is O(k^3), it means that the time it takes to execute the algorithm is O(k^3). It appears this discrepancy may be a result of not agreeing on terminology. I haven't checked this out thoroughly, but glancing at my copy of Mermin's "Quantum Computer Science" confirms that it's k^3 in time, and only k in space.
While it's clear a quantum computer won't be breaking your RSA keys any time soon, there's a big difference between remarking that a 4096-bit key will require "billions" of qbits and the more correct claim that it will require thousands of qbits (at least 20k qbits).
Botnets folding md5 between the 8-12 character spectrum for rainbow hacking are more of an imminent threat....between the estimated 4-10 million machines you could probably crack any unsalted hashes within a month.
Trying to install linux on my microwave, but keep getting a kernel panic...
If we can use quantum computers to decrypt..
Why can't we use them to come up with an equally mind-blowing way of encrypting?
I don't mean single photon secure fibre channel stuff. That seems fairly impractical to deploy to the whole internet.
I mean, why can't some mathematical genius come up with a new encryption algorithm that you
can only implement on a quantum computer, and which produces a cipher text so random that it
can't be decrypted even by another quantum computer unless it knows the secret.
Does anyone have any ideas how such an algorithm might work?
Where are we going and why are we in a handbasket?
Since the Sci Am article is subscription-only, you may want to check the complete draft-version of Scott Aaronsons article for Scientific American (before editors changes) here:
http://www.scottaaronson.com/writings/limitsqc-draft.pdf
Scott posted it on his blog on 2/18, see http://www.scottaaronson.com/blog/
(The blog is often quite technical as you can expect but funny and worth following just for its non-techical bits. Circumcision and Australian models are also discussed on frequent basis.)
I doubt that we will ever figure out - and I suspect that even if we did figure out we couldn't do much about it
Heavier-than-air flight is impossible; a train will never go faster than a person can run or the passengers will asphyxiate; there is no reason why anyone would want a computer in the home; etc.
It's a bad idea to discount future technological advances wholesale.
In what ways is this a problem? I'm not knowledgeable about cryptography. My only knowledge and understanding (due to complex math involved) is Simon Singh's Code Book.
I would consider that if Quantum computers exist, it would pose a serious threat to security and military applications as your enemy would always be listening. I don't know if E-Commerce would grind to a halt, since governments would initially be the only ones to afford it. I would think that instead of hitting e-commerce the better thing to go after -for a government- would be banks and securities exchanges, military and state secrets.
Personally speaking, I don't have a great deal of information that needs unbreakable encryption (neglecting the computer were stolen, etc). Were it financial data, I would keep it on a PC off-line. Of course, if banks are vulnerable, that's another consideration altogether. If I lived in a communist state or a dictatorship, I think the issue would change yet again. There would be information you would want to keep away from the government such as attempts for a coup or rebellion. Or plans to destroy the Death Star!
He makes an extremely cogent argument, but it is hampered by the lack of information we have about the state of the art in quantum computers.
Domestic spying is massively popular with western governments right now, and if you think that the NSA and GCHQ aren't doing secret research into quantum computers you are out of your mind. Furthermore, it is a commandment of signals intelligence that you do not let the enemy know you have broken his code - and in this case the enemy is us. We have no idea how far along they are. We have no idea what the generational length is for the quantum computers that are certainly being developed in secret.
Basically, this essay could be published and make just as much sense either before or after a critical breakthrough had been made by one of the aforementioned agencies and they hadn't told anyone. Thus, we have no way of knowing if we are already past that point or not.
Given that it has already been shown that quantum computers are not infallible, would it not make sense now to start working on encryption methods designed to flummox them?
If we can put a man on the moon, why can't we shoot people for Apollo-related non-sequiturs?
http://www.schneier.com/blog/archives/2008/03/quantum_computi_1.html
Now how would you explain it to magazine editors who keep writing articles on how quantum computing is the future of gaming?
No sig today...
How are you going to get the pads to the other person? Encrypt them?
If you have a way of transmitting the pads securely then you could just use the same system to transmit the messages - no encryption needed!
No sig today...
No, you...
http://imagecache2.allposters.com/images/pic/145/HR0148~The-Simpsons-Eat-My-Shorts-Posters.jpg
hardeeharhar
Parent post is absolutely correct; grandparent is absolutely wrong.
;-).
Read Scott Aaronson's blog to get a clue about quantum computing.
Also read about Schor's algorithm, which is the known algorithm to factor large numbers in log(n) time *if your quantum computer has enough entangled qubits to represent the number*. Again, though, remember that FACTORING IS NOT NP COMPLETE, only NP hard. Other NP hard problems are harder than factoring (for example, any NP complete problem
Also read about Grover's algorithm, which is a general algorithm to solve NP complete problems, and which HAS BEEN PROVEN TO BE THE FASTEST way to solve the NP complete problem of lookup in an unordered dictionary. Grover's algorithm finds the answer in n^1/2. Obviously if the fastest algorithm to solve a specific NP complete problem is n^1/2, you cannot have a way to solve all NP complete problems in log(n).
Look up Grover's algorithm and Schor's algorithm on Wikipedia, and you'll see that the GP is speaking beyond his knowledge.
I should say that I also made the mistake of thinking factoring was NP complete, and made a fool of myself on Scott's blog before the many, many people more knowledgeable than I about QC on that forum corrected me.
Do you have an example of asymmetric encryption that is secure against quantum algorithm? PK is broken by Schor's algorithm (if you have a big enough quantum computer), and per Scott Aaronson (an algorithmic complexity professor at MIT), elliptical encryption is also demonstrated to be vulnerable. He appeared to imply in that same discussion that all asymmetric algorithms were vulnerable...
(No need to point out technicalities. I'm joking.)
[of which I know nothing]
It all depends on how long you need the stuff secret.
If all public key crypto except for nTru's is bust in possibly 25 years, and your stuff needs to be secret for 50, then you better be using quantum-resistant (did I just invent that term?) crypto Right Now(tm).
Believe it or not, the world record for factoring using a quantum system is currently 15 - that's right, 5 and 3.
http://cryptome.org/shor-nature.htm
http://en.wikipedia.org/wiki/Shor's_algorithm
That was in 2001. I'd like to remind everyone that these charlatans are currently drawing in millions of research dollars (both public and private) and still haven't published anything meaningful since. Quantum computing is the closest thing to a platonic ideal of vapor-ware. While we sink money into buildings, offices, fine wine and caviar, sports cars, etc... for these "world class" researchers, the people in the labs doing real science barely get by.
Public key ciphers aren't used for encrypting data, they're used for digital signing, authentication, etc.
Your encrypted files will be safe against quantum computers.
No sig today...
Well, you could, but then you might have to wait!
You can securely exchange OTP when you're physically in the same room with someone, and then use it when you're not in the same room. This seems like a very reasonable thing to do with people that you know and regularly meet in Real Life (e.g. your wife).
That case obviously doesn't apply with most of the people you know on the 'net, and yet it probably does apply to a vast majority of personal communications.
As copyright owner of this comment, I authorize everyone to defeat any technological measure which limits access to it.
Bruce needs to read more before he posts stuff like this: http://scienceblogs.com/pontiff/2008/03/shor_calculations.php