Slashdot Mirror
MIT's New 5-Atom Quantum Computer Could Make Today's Encryption Obsolete (pcworld.com)
An anonymous reader writes: In traditional computing, numbers are represented by either 0s or 1s, but quantum computing relies on atomic-scale units, or "quibits," that can be simultaneously 0 and 1 -- a state known as a superposition that's far more efficient. It typically takes about 12 qubits to factor the number 15, but researchers at MIT and the University of Innsbruck in Austria have found a way to pare that down to five qubits, each represented by a single atom, they said this week. Using laser pulses to keep the quantum system stable by holding the atoms in an ion trap, the new system promises scalability as well, as more atoms and lasers can be added to build a bigger and faster quantum computer able to factor much larger numbers. That, in turn, presents new risks for factorization-based methods such as RSA, used for protecting credit cards, state secrets and other confidential data. "If you are a nation state, you probably don't want to publicly store your secrets using encryption that relies on factoring as a hard-to-invert problem," said Chuang. "Because when these quantum computers start coming out, [adversaries will] be able to go back and unencrypt all those old secrets."
Way back in 1972, before many Slashdotters were even born, I remember hearing about how quantum computers were just "5 years away".
Then in 1977, I remember hearing about how quantum computers were just "5 years away".
Then in 1982, I remember hearing about how quantum computers were just "5 years away".
Then in 1987, I remember hearing about how quantum computers were just "5 years away".
Then in 1992, I remember hearing about how quantum computers were just "5 years away".
Then in 1997, I remember hearing about how quantum computers were just "5 years away".
Then in 2002, I remember hearing about how quantum computers were just "5 years away".
Then in 2007, I remember hearing about how quantum computers were just "5 years away".
Then in 2012, I remember hearing about how quantum computers were just "5 years away".
I have a strong suspicion that in 2017 I will be hearing about how quantum computers are just "5 years away".
You first have to get a copy of the encrypted data before you can start trying to hack it. Are there any governments that actually store their state secrets in a fashion where they rely purely on encryption? Encryption tends to be an extra layer.
I can factor 15 as well, in my head, near instantly. The only speed problem is I/O.
Yes, this MIGHT be a threat to encryption systems one day, might not as well.
Surely they mean Decrypt, right? I mean, these are supposed to be the best and brightest, MIT "creme de la creme", right?
Now they're just 5 atoms away.
Mostly random stuff.
Totally irrelevant versus symmetric encryption (private key only). At least the summary makes this somewhat clear. This is a threat (and a known one) to at most public key methods and probably public key methods that rely on certain one way functions. Not going to fuck with, say, Truecrypt/Veracrypt/LUKS.
Seriously /., you are insulting to the community.
Achille Talon
Hop!
I am still pretty convinced that the "quantum computer"-hype is based on fundamentally flawed assumptions, and that they won't break RSA (or other practical problems) of any reasonable size, that are not also easily solved with conventional computers.
Just because a model works with probabilities of "uncertain states" does not mean reality will reveal a "solution" based on all possible combinations of such states in no time. There is no compelling evidence yet that a quantum computer will find solutions quicker than it takes the real, physical hardware of that computer to take on all relevant input state combinations.
I'm prepared to bet the safety of my encrypted data on that, and I am convinced that 40 years from now, we'll look back at the hype around quantum computers the same way we today look back on the era of analog computers in the 1960s/1970s, when it was a plausible approach to solve some (back then hard-to-compute-digitally) equations, like for numerical calculus, by building physical systems (electronic circuits) that were known to behave in a way that equations could be solved by carefully adjusting some input voltages, then measuring some output voltage. We know that the precision achievable by such analog computers is very limited, and see the same problem preventing "quantum computers" from ever providing solutions that need to process a significant amount of information.
and when will we see this be put to use in reality? 10 or 20 years? or never?
are luckily Zuckerberged to near infinity so the NSA won't be snooping on me
The link points to a science article which is closed.
Why are we advertizing an article that can't be read?
For an actual summary of this research see http://www.scottaaronson.com/blog/?p=2673 by Scott Aaronson who is a quantum computing expert. The key thing here is that they factored 15 with high probability without having to sort of cheat by making a circuit that was more likely to work if one suspected that 15 had factorization resembling 3*5. As usual, this is getting completely overblown by the popular press. It is an important step towards actually making quantum computers that can factor big numbers, but it is nowhere near anything that would make RSA or other factoring based crypto obsolete.
"...publicly store your secrets..."
So the NSA, the CIA, the FBI and probably a few others placed orders for 10 MIT quantum computers each? when it comes to the government and "security, think of the children!" money is no object.
If you actually read the scientific article (which is available as a preprint unter [1]), what the authors discuss is how to significantly improve Shor's algorithm, the quantum algorithm for factorizing prime numbers. They show that the number of qubits needed to perform Shor's algorithm is actually quite a bit lower than what previous versions of the algorithm required - and they claim that their version is much more scalable than previously known versions.
They demonstrate their algorithm by factorizing the number 15 using trapped ions. That elementary qubit operations can be performed with trapped ions has already been demonstrated [2], that part is nothing new. Factoring the number 15 with Shor's algorithm is has also been done before. But since their algorithm doesn't need nearly as many qubits as the previous formulation of Shor's algorithm, specifically they only need to have a single ancillary qubit in addition to the qubits required to represent the number to be factorized (in contrast to 3n ancillary qubits), and given the fact that the quantum Fourier transform operation that was previously required to be performed on the ancillary qubits is difficult to pull of in practice while keeping quantum coherence, they argue that their algorithm will be much easier to implement in real quantum systems.
So their research is actually a big step forward when it comes to a potential actual practical realization of Shor's algorithm, and what they did is still very impressive (even the experimental part of their work), but their work doesn't address the problem of actually scaling up the number of qubits: 5 bits have been done before, and while their work means that less qubits are needed, it's not like even a (512+1+error correction) qubit computer with quantum coherences is around the corner (note that to break 512 bit RSA you don't need a quantum computer). Furthermore, there's a huge debate in the community as to what the best design for a scalable qubit architecture is: the authors of this paper seem to follow the school that wants to use ion traps, but there are also other approaches to implementing qubits: superconducting qubits (in various variants), spin qubits (including nuclear spins), semiconducting qubits, adiabatic quantum computation, and a couple more. A lot of people in the community are working on all of these different approaches, and it is not clear to me which of these will be the most effective way to implement a quantum computer in the end. And scaling this up beyond 100 qubits with full quantum coherence and quantum control of qubit operations (from all reports e.g. the D-Wave machine "only" does quantum annealing with ~500 qubits, and doesn't implement a universal quantum computer) is something that's still quite a bit away. How long? I don't think anybody can really predict. Could be 5 years, could be 10, could be 50.
To reiterate: the paper is a breakthrough, because (if we leave out error correction for the moment, which increases the number of qubits required) to factor a 1024 bit RSA key, one would previously have needed 1024 + 3 * 1024 qubits and a very difficult to pull off quantum operation (quantum Fourier transform) on 3 * 1024 qubits simultaneously. This paper reduces that to 1024 + 1 qubits, where the KQFT operation only has to be applied to the 1 additional qubit. We still don't know how to actually manufacture a quantum computer that maintains coherence well enough with that many qubits, so there's no need to start panicking when it comes to this, but these kind of improvements do show that research towards asymmetric cryptography that is safe against quantum computing is required - and that we should really start implementing these kinds of algorithms NOW, so that when somebody actually has breakthrough in this regard, we have the technology in place to switch at that point. A good starting point for people that are interested is the pqcrypto.org site [3] and the excellent talk by Dan Bernstein and Tanja Lange at 32c3. [4]
[1] http://arxiv.org/abs/1507.08852
[2] https://en.wikipedia.org/wiki/Trapped_ion_quantum_computer
[3] http://pqcrypto.org/
[4] https://www.youtube.com/watch?v=6XeBvdm8vao
The key will be scalability. Its an interesting experiment as it taps into the fundamentals of computing. It could however well be that the effort of keeping things disentangled grows exponentially (something which Shor's algorithm does not address). Like in dynamical systems theory, where computing the 10th iterate of f(x)=4x(1-x) with some initial condition like x=0.4 is no problem. It gives 0.297... already for a a hundred iterations the result become ambiguous and the answer becomes hardware and software dependent. No error correction can bypass these fundamental sensitive dependence of initial condition difficulty. So, it could well be that it is possible to factor a 10^10 digit number nicely but that things become more and more difficult larger numbers like integers with 100reds of digits and that RSA will remain save from quantum computer attacks. But who knows? The nice thing is that if it will be faster, one will be able to demonstrate it by factoring otherwise not yet factored numbers.
https://what-if.xkcd.com/13/
Issac Chuang is a Chinese
Having a Chinese in a leading role developing cutting edge quantum computer only means China will be one of the first nation to deploy quantum computers
Quantum is the new Alchemy
http://www.crystalinks.com/alc...
~ People that think they are better than anyone else for any reason are the cause of all the strife in the world.
Time to sweep away all the monsters and demons!
First, most encryption is not even really affected. For block-ciphers a working and large enough QC halves the key-length. AES-256 would still be perfectly secure and AES-128 would still be hard (but maybe possible) to break. And second, factoring RSA-2048 (which is regarded as too short today) would need around 2200 qbits to factor with this "breakthrough". They are at 5 qbits now. Where where they 10 years ago? Oh, right, at the same low number. If progress is made at this rate, they will be able to break RAS-2048 in x years, where x goes towards infinity, i.e. _never_.
This is about as valid as claiming the invention of paper threatens RSA, after all you can do attacks far faster with paper than with stone tablets.
Can we please stop the moronic and false "success" stories about quantum computing?
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
And scaling this up beyond 100 qubits with full quantum coherence and quantum control of qubit operations (from all reports e.g. the D-Wave machine "only" does quantum annealing with ~500 qubits, and doesn't implement a universal quantum computer) is something that's still quite a bit away. How long? I don't think anybody can really predict. Could be 5 years, could be 10, could be 50.
Could also very well be "never". Just look at the lengths CPU manufacturers have to go to get to 5GHz. A bit more is likely feasible, but, say, 100GHz is likely completely infeasible unless a mythical new technology presents itself. It has not, despite now 50 years of intense research, so what we currently have in CPUs may very well be close to the end of the line in this universe. It is quite likely that quantum computing (if it even works at all, factoring 15 could well be some other effect), runs into pretty hard scalability limits at 100 qbits or so and will never be a threat even to yesterday's RSA key lengths.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Could also very well be "never". Just look at the lengths CPU manufacturers have to go to get to 5GHz.
This isn't an accurate statement at all. multi-core architectures have made pushing the ghz barrier uneconomical and for the most part pointless, much higher rates aren't just possible they have been achieved many times and current theoretical limits are due to the materials used which a lot of research is going into alternate materials, I would say we will see clock rates many times higher in coming years when we transition to other materials. They have had CPU's in labs that went up to and beyond 8Ghz a decade ago even on current transistor tech, but they simply aren't worth the effort to refine at this point as there is a much higher and faster return on multi core at lower speeds.
Yes but when they do actually get here today's strongest encryption will be a complete joke. As I said before in 100 years a 5 yr old with their equivalent of a cell phone will be able to decrypt anything encrypted today. The absolute weakest computer in 100 years will make today's biggest super computer look like the original printing press. Yet so many people can't seem to fathom just what changes will happen in the next century. Technology is moving faster and faster and we've more advances in tech and medical knowledge in the last 100 years than all of human history. The next 100 years will even more. The human race is at the very beginning of huge exponential growth of knowledge yet so many people can't seem to grasp that.
100 GHz is feasible, it's not done because it's easier to have the same clock for the entire chip. But it's possible to have small areas running at 100 GHz and to use asynchronous communication between different areas.
With such monstrous computing power, they could mine bitcoins and fund their R&D entirely through Bitcoin mining.
All those moments will be lost in time, like tears in rain... time... to... die...
whipslash, we have another case of abusive modding. The parent comment is extremely relevant, and should not be -1. Can you please fix it? Whoever downmodded that comment, which is perhaps one of the most insightful here, should never be allowed to moderate again. Causing good comments here to be hidden due to bad moderating is inexcusable, and whoever committed this abuse should be punished severely. They have brought direct harm to Slashdot.
Okay, this may be a foolish question, but if you encrypted something and then encrypted it again (with a different key) how would you know when you had gotten through the first layer of encryption? How would you know that you'd successfully decrypted the first layer?
The first set of decrypted info would still presumably look like encrypted data (or random shit), so how would you know that it had actually been decrypted?
Just cruising through this digital world at 33 1/3 rpm...
Setec Astronomy
Long-term change is often greatly overrestimated and short-term is underestimated.
I used my quantum computer to solve the problem of cold fusion, which allowed me to finish my flying car design!..
the encryption world will just start using 16.
Things that don't yet exist may make things that currently exist obsolete.
the quantum algorithm for factorizing prime numbers.
That problem may be simpler than you think.
In 100 years we won't have the energy to tun this techno-based world anymore so we'll have reverted back to agriculture. No computers. No technology. No science, except for basic biology and simple weather forecasts.
Meanwhile, in my Universe they've existed since the 90s and now even my local University has a few qubits. When I was a kid, all we had was a few q*berts.
Alchemy is the new alchemy, too.
http://www.scientificamerican....
Oh, boy.
In another reply from you in a different sub-thread of this post, you accuse your parent poster of making two assumptions.
Here, in your own post, you make far more assumptions of your own.
You are a hypocrite, gweihir.
100 years from now people will be growing crops with Brawndo - The Thirst Mutilator
Your post conveniently ignores the fact that quantum computers actually are a thing, and have been for a while.
Wtf is a quibit?
The NSA has a 300 qubits by 50 qubits by 30 qubits sized quantum-cluster computer, aptly codenamed The Ark.
I was alive in 1972, albeit just 15. I attended a fairly well-to-do preparatory school. At that school we actually had a connection with a distant university, a forerunner of the Internet. I was not nearly as interested in computers then as I am today, but that's okay because I'm not professing to be an expert on the subject.
What I am saying is that if there were any serious talk about quantum computers in 1972 then there's a good chance I'd have heard about it. I was (and still am) an avid fan of science fiction and I don't even recall reading about any quantum computing in science fiction, at that time. Granted, there are still vast numbers of bodies of work that I've not read. Again, I don't claim to be an expert on the subject.
So, if you don't mind... Who was telling you, in 1972, that quantum computers were five years away? I recall Feynman talking about it in the early 80s and I want to say that he wasn't quite the first but one of the first to theorize about them. There was some ado about them in a very specific task, as I recall, a few years prior to 1972 but that was not something that anyone was proposing would be in just five years.
As near as I remember, even Feynman was cautious about such - including his concepts of nano-technology and, in the early/mid-1980s was postulating that such were, "50 years out, at least." One of his lectures, a neat one by the way, had horribly drawn machines comprised of just a few atoms and the machines were doing replication and building smaller machines out of atoms. I'm just a layperson, or so I claim and believe, but I'm going to add that his time-frame estimates might not be all that far off.
Anyhow, if anyone was saying that they were five years away, in 1972, you were either listening to crazy people or are taking things woefully out of context. The device proposed (maybe even built) in the late 1960s was so different from this as to be an entirely different concept. I do not recall any serious speculations about a time-frame until the mid/late-2000s but, again, I am not an expert on the subject.
"So long and thanks for all the fish."
i am always hearing it is about power consumption, not clocking....
It got elektrolights!
Probably one of the best comments I have ever read on /.
This comment was written with the intention to opt out of advertising.
OK, maybe 6, tops.
Well done abstract.
Large number factorization is one of integral-nature's greatest frontiers. I find it amazing that within my lifetime a curiosity of mathematics of interest to theorists and puzzle-makers has become the keystone of privacy in the world. For me there was a single 'Eureka' moment. Along with many others I caught a glimpse of today's world back in August 1977 thanks to a column by Martin Gardener in Scientific American: "A new kind of cipher that would take millions of years to break" Read it! . You can sense the author's excitement. I remember carrying this issue around with me for days, trying to wrap my head around the concept... to me these few pages are among the greatest that ever appeared in a magazine. I'd just devoured David Khan's The Codebreakers which describes centuries of cat-n-mouse games with substitution, transposition and polymorphic ciphers augmented in the end by devilishly simple mechanical apparatus that became devilishly complicated as it scaled... and on the other end the mathematical attacks of cryptanalysis (greetz to Friedman and Sinkov) that can de-construct these, often unseen. It was a brilliant game and had seemed to reach its end. RSA was like a bolt of lightning from clear sky. We knew then that factoring was hard. This had to be the way out.
Back then sieving seemed the only practical attack, and anyone could see how progress in sieving degrades so quickly as to represent a (practically) solid barrier. Then a number of novel ideas for parallelizing the attack were proposed, even such flights of fancy as a 'pond' of biological computers, like bacteria, working on a single problem. But even such approaches run into bottlenecks, as the amount of inter-thread communication necessary to manage the attack turns a time problem into an inter-node bandwidth problem.
Then another bolt of lightning! Shor's algorithm turns a classic dilemma into yet another (quantum) engineering challenge in much the same way that Turing realized enigma would fall in reasonable time, if he could only get the necessary part together and make them work. Since we're down to atoms this may even be the last frontier. Here's hoping that some where along the way to solving the problem, that day when the fence of RSA falls, we will have evolved into a more considerate species.
Because, as you all know deep down, it is impolite to read others' mail.
Imagine a world in which we could tear open any digital envelope, yet fail to do so from simple human restraint.
What a world that could be.
<blink>down the rabbit hole</blink>
Quantum is the new Alchemy
http://www.crystalinks.com/alc...
Except that quantum things are real, alchemy is imaginary.
Two things. First, exponential growth can't continue indefinitely. Second, once all the easy problems are solved, the ones left will require 90% of the total time. We have the lessons of AI and fundamental physics, where all the "easy" problems were solved decades ago, both disciplines becoming pretty stagnant since. Ergo, for all we know, the world 100 years from now might not look all that different.
You're post comes across as something said by a teenager who barely understands what they're talking about. You know that? You're aware that there is every reason to push the ghz barrier, right? You see, the vast majority of real problems have an inherent limit of how parallel you can make them. Not only that, but the more parallel you make the problem, the less speed up you get. For example. Take a task that runs on a single core at X speed, running on two cores you might see 1.9X speed, and four cores you might only see 3X speed. And those sorts of scaling imply that it's very good at being paralleled. As apposed to if a piece of code runs at X speed on Y ghz, it will run at 2X speed at 2Y ghz.
What you don't seem to understand is why they don't increase the clock speed. Remember, thermal dissipation increases at the square of the clock speed. Any increase in clock speed anymore must be accompanied by an improvement in the thermals. Yes, you can make an 8ghz chip today, as they did a decade ago, but like a decade ago, it needs to be cooled with liquid nitrogen in order to keep the internal resistances low enough that the chip will actually function (the faster you go, the lower the resistance needs to be so the gates can charge in time, but as things get warmer, resistance increases). This isn't exactly practical in any environment other than a lab. My 4GHz i7 produces a hell of a lot of heat. To take it to 8GHz would be 4 times as much heat, and at that point water cooling is no longer a fun PC mod, but minimum and potentially insufficient requirements. 16 ghz, and you're talking about something nearing the temperature of the surface of the sun if left uncooled, how the hell do you cool that?
For factoring prime numbers? I can do that in my head, instantly.
It is unhackable
>something nearing the temperature of the surface of the sun if left uncooled, how the hell do you cool that?
Hold it against Hillary's tit ?
Unicode killed the ASCII-art *
I think I need to hack the Drumphinator to also replace all instances of the word "could" in headline font with "kud", as in "I kud you not".
Best comment ever!!
I would like to suggest that the moderation process be revised, so that usernames are kept hidden until the moderator is finished. This should certainly help prevent the bias against ACs. The validity of a comment should have nothing to do with the poster's history.
It should also prevent users from stealing mod points by plagiarizing a comment under the claim that they are "pulling it out of moderation hell". There is nothing I less respect for than a thief.
Fusion has been 40 years away for longer than that.
(-1: Post disagrees with my already-settled worldview) is not a valid mod option.
It's what plants crave.
It will be proprietary and half a dozen well-placed accidents could wrote out that progress. Very few people today actually know how to do the most advanced things. Such thinly distributed knowledge could very easily be lost in a single accident.
Only boring people are ever bored.
"Except that quantum things are real", but not until you open the box. Before that they are both real and not real.
Not all encryption. -some- encryption, namely RSA and public key based algos that can be factored with Shor's algorithm. We will just wind up moving to UOV (Unbalanced Oil and Vinegar), lattice-based crypto, new ECC based encryption, or another method, and life will go on, just like it did when MD5 was weakened, and DES's short key space was found to be easily run through.
Life will go on.
As for symmetric encryption (AES, IDEA, BLOWFISH), quantum crypto won't do much for this, so there is no need to worry here.
Sigh, I just used my last mod point (in this thread, so anon so as to not undo them).
when they get past 20 qubits. Until then, it is all media hype. Even then, if it takes 10 minutes to read the result, it would be pretty useless.
What I am saying is that if there were any serious talk about quantum computers in 1972 then there's a good chance I'd have heard about it.
Sorry, not this time...
According to that esteemed, peer-reviewed (and CIA-owned) publication, Wired, David Deutsch is the father of Quantum Computing, and first postulated same "in the 1970s".
In all fairness, I never heard about Quantum Computing until the 1990s; so what do I know?
Elementary failure of physics (or history) knowledge : Quantum computers were only seriously proposed in the early 1980s. Fiction authors may have used the term earlier, but without meaning.
Birds are not dinosaur descendants;birds are dinosaurs, for all useful meanings of "birds", "are" and "dinosaurs"
Careful, make sure you don't lose it.
Yeah, it looks like some mention of it in the 60s (according to Wikipedia) and then not much of anything until the 1980s and it does look like Feynman was speculating about fifty years out (if I remember the talk well enough). So no, no serious discussion of it in the 1970s was speculating that it was five years out. At least not that I can find. Your link doesn't change that.
"So long and thanks for all the fish."
Except that quantum states are potential realities until measured. Then reality is the only one that ever was with the exception that it's been observed by entities that give a shit about the *potential state* to begin with.
~ People that think they are better than anyone else for any reason are the cause of all the strife in the world.
Someone better call Bill Gates quick and have him shut that darn quantum computer and stop those researchers at the border.