Slashdot Mirror
Cryptographers Brace For Quantum Revolution
Tokolosh writes: An article in Scientific American discusses the actions needed to address the looming advent of quantum computing and its ability to crack current encryption schemes. Interesting tidbits from the article: "'I'm genuinely worried we're not going to be ready in time,' says Michele Mosca, co-founder of the Institute for Quantum Computing (IQC) at the University of Waterloo..." and "Intelligence agencies have also taken notice. On August 11, the US National Security Agency (NSA) revealed its intention to transition to quantum-resistant protocols when it released security recommendations to its vendors and clients." Another concern is "intercept now, decrypt later", which presumably refers to the giant facility in Utah.In related news, an anonymous reader points out that the NSA has updated a page on its website, announcing plans to shift the encryption of government and military data from current cryptographic schemes to new ones that can resist an attack by quantum computers.
007 movie title
all your secrets are belong to us.
This is a First Post, and yet it is not... I have successfully achieved the simultaneous on/off state of First Posts....
to typewriters and safes.
Said the main behind the curtain!
axolotls?
... "radioactive" and "nuclear" were the popular buzzwords. In general, people knew next to nothing about these things and thus they made highly interesting topics for speculative fiction. Today, that new buzzword is "quantum." The world didn't end in the 1950's and the world won't end now. Technology will grow, people will learn it, and we'll move on with the times. Nothing to see here.
Ying and Yang are restored.
I achieved simultaneous on/off state by smoking a fat bowl of pot.
This is exactly the sort of situation where the NSA could be the most useful/helpful to us - but no one in tech will trust them to provide actually secure encryption protocols because of their elliptic curve shenanigans.
#DeleteChrome
They'll force us to have passwords like "$myBigLongPassword47367@#LongLongOhHolyMoley!528"
Table-ized A.I.
I suppose it was bound to come to this, but even if they intercepted petabytes of data, how are they going to decrypt it uber fast when storage media is slow even by today's computers' standards?
It would be an incredibly fast process, but first you have to find the needle in the hay field and then splice it open, and whilst the latter would be solved by quantum computers, the former is still in the works.
...it would be a breakthrough of *Gaussian* proportions!
http://www.imdb.com/title/tt0105435/quotes?item=qt0448962
RSA factorization using today quantum registers is more than useless; The last year largest number processed was: 56,153. The quantum decoherence is faster when the number of particle increases; And to defeat the RSA some huge quantum registers are required. The only question: is a quantum machine that can process useful computing operation is even possible?
Quantum computers capable of cracking the higher keysizes that we we have now will never exist, and thus this concern is pointless. People who think otherwise aren't aware of the physics involved, and how the only people left researching making this shit don't believe it will ever work the way people want, they just keep going because it is their bread and butter now. Gotta feed the family.
Proudly brought to you by the singularity, powered by cold fusion.
Unless it's based on a one-time pad, a message can be decrypted.
They are not talking about breaking AES or Two Fish encryption. They are worried about breaking the key agreement. Currently when a communication channel is set up the two parties agree on a key for encrypting the communication. This is normally done by Diffie-Helman (D-H) key agreement or one party could select a key and then give it to the other party using the other parties RSA public key. Both RSA and D-H are based on the difficulty of solving math problems that quantum computing should be able to easily solve.
.
Your AES encrypted file on your hard disk is safe. What the NSA is doing is storing your conversations and the key agreement. Years from now they might crack the key agreement and then decrypt your communication..
.
Things like Elliptic curve Diffie Helman are secure. So your Black Berry communications will still be safe, not sure who else widely uses EC (your ZigBee electric meter in the USA and UK)
"If you have something that you don't want anyone to know, maybe you shouldn't be doing it in the first place"
Don't forget Wassenaar also bans and classifies quantum computers as military munitions. Just search for "quantum" in the munitions list pdf.
Since that bans things which are considered possible but dangerous, I'd say it's a good hint that our government already has them.
From the first commercial transistor to commercial integrated circuits six years. Nine years later, we had Intel CPUs.
Right now we have machines with a few cubits, analogous to a 1960 IC. It wouldn't surprise me too much if, in six years, we had machines with 2300 qubits. Maybe it'll be called the Intel Q4004. :)
As you probably know, for decades after, transistor counts doubled every TWO years. If the cubit count doubles every two years, that's going to be a problem for cryptography.
We don't know if that's possible, but we didn't know that 386 was possible in 1970.
Right now we have machines with a few cubits, analogous to a 1960 IC. It wouldn't surprise me too much if, in six years, we had machines with 2300 qubits. Maybe it'll be called the Intel Q4004. :)
In six years assuming anyone is still willing to waste their time and money there will very likely be "topological" quantum computers with 2300 qubits and they will be just as useless as desktop computers at cracking RSA. Real machines with 2300 entangled qubits would be able to perform operations that would not even be remotely possible in the current life of countless trillions of universes if every atom in every universe were a transistor operating at a trillion trillion trillion thz. It's completely bullshit.
As you probably know, for decades after, transistor counts doubled every TWO years. If the cubit count doubles every two years, that's going to be a problem for cryptography.
Moores law is a reflection of market forces. Doubling was enabled by halving cost enabled by market pressure to reduce costs enabling people to afford more capabilities for the same cost which fueled a never ending feedback loop.
There is no analogue to QC and BTW number of entangled qubits are NOT doubling every year.
We don't know if that's possible, but we didn't know that 386 was possible in 1970.
Nonsense it was then and mostly continues today to be an engineering problem.
Nobody has any idea how to scale out QC without being drowned out by noise.
Quantum Computing does _not_ scale, as it cannot subdivide problems. You argument is completely bogus and in fact shows the opposite of what you think it shows.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
What will they use to encrypt and protect their proof-of-works and studies on quantum-resistant algorithms?
Don't worry. It ain't going to happen.
Quantum computing is the geek version of snake oil.
Every decade has its futuristic buzzword. In the '60s it was "flying cars". In the '80s it was "artificial intelligence". Now it's "quantum computing". Don't you find relevant that the people claiming that quantum computing is just around the corner, and will break any encryption known are the same people who are trying to build quantum computers (and are seeking funds to do it?)
The article references a paper which does not say much to me.
http://pqcrypto.eu.org/docs/initial-recommendations.pdf
The basic problem is that a QC potentially makes an O(2**n) problem O(1).
So if you can entangle enough Q-bits, fixing it is not just a matter of picking a bigger key.
An non-QC encryption implementation can be thought of as a set of flops interconnected by a set of gates.
Breaking the code requires one to know the gate wiring and deduce the state of the flops.
The strong suite of a QC is deducing these flop values when there is only one possible set of values.
I suspect, to make the code QC safe, one needs to either make the gate wiring not knowable, or make the flops have more than one set of values.
If this is so, then what protects the new new code from some sort of transformation that makes it look like one friendly to the QC?
Perhaps a QC safe algorithm is one where the transformed version is so big that it can't run on possible QC's, while the un-transformed can run on regular computers if you know the keys.
I wonder if there is any work in this area?
ps,
The really interesting thing here is that money being poured into QC might tell us something fundamental about the quantum universe.
For example, if entanglement really works at scale, then there may be a lot of it in how the physics we can observe works.
Maybe there is no need to travel at faster than light, be cause we are already there.
Just kidding, but it will be interesting to see how this technology evolves!
I'm doing mostly security work these days, and really the situation is very bad.
Military and government computers are most vulnerable to various non-algorithmic vulnerabilities in the hardware/firmware, which gets little scrutiny and nary an update. Some of these are likely backdoors that the NSA itself probably paid (carrot & stick) to have installed. Meanwhile they have buildings full of people who are paid to do nothing to find breaks in our infrastructure, but tell nobody about them, courtesy of the American taxpayer. I'd be really surprised if there's a computing device today (that's not home-built) that the NSA can't break. Crypto-algorithms don't need to be broken except in the case of assets seized after the fact.
I guess the proposals to separate NSA into military and NIST-ish groups are better than the status quo, but really I'd rather see all those people working to make society better rather than spending their lives supporting the corrupt politicians.
My God, it's Full of Source!
OUTSIDE_IP=$(dig +short my.ip @outsideip.net)
Gosh, I think I've heard this one before. Wasn't this the whole thing behind Y2K? "Get ready, folks, because if you aren't then the whole world will go right back to the middle ages".
Fool me once, shame on you. Fool me twice... and I'm not quoting Star Trek (or Bush).
The government wants to keep their data safely encrypted? But I thought they were saying that only bad people with bad things to hide need to use encryption? Are they admitting to being bad guys doing bad things?
i'll be waiting.
Already "they" are decrypting everything, or so you should assume. If "they" had working effective quantum computers they wouldn't tell us. And all the stuff they do and say now would be the smokescreen hiding the quantum computers. In WW2 Churchill had to let the German subs intercept the convoys despite the secretly decrypted Enigma messages telling him where the subs were. And the WW2 decryption remained secret for decades. It's just the same now. IF(!) "they" have effectively working quantum computers then we won't be told. The only element of paranoia about this is my worrying about who "they" are, and whether "they" truly are acting in my interests.
Paul Beardsell
I don't think it's quite that simple. While my intuition tells me that quantum error correction can't work once the number of states becomes too large, when I tried to prove that mathematically the results showed that I was wrong. (That is, they showed that the *particular* argument I was attempting to use was wrong, not that QEC can definitely work.
I'm also doubtful that quantum mechanics is really linear at that sort of scale - historically, linear theories have always proved to be only approximations. But while a quantum computer that fails due to non-linearity would not be useful for cryptography, it would be a huge step forwards for physics - and even a negative result (yep, still looks linear!) would be interesting. So if the experts think that quantum error correction is possible in principle, I'm all in favour of the research.