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."
Now they're just 5 atoms away.
Mostly random stuff.
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.
Surely they mean Decrypt, right? I mean, these are supposed to be the best and brightest, MIT "creme de la creme", right?
Isaac Chuang is professor of physics and professor of electrical engineering and computer science at MIT. He is NOT professor of English at MIT. So step the fuck off, Chris Boyd. And stop unnecessarily capitalizing your Ds.
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.
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/
"Don't publicly store your secrets".
FTFY
~ People that think they are better than anyone else for any reason are the cause of all the strife in the world.
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.
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...
I used my quantum computer to solve the problem of cold fusion, which allowed me to finish my flying car design!..
Governments, corporations, and groups of people need to communicate securely. Quantum crypto breaking destroys the one way math based crypto systems but other systems still exist and will still be secure. Given the low cost of bulk data storage we might consider moving to one time pads.
Things that don't yet exist may make things that currently exist obsolete.
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.
Shit happens when you post AC. If you won't own your comment and risk your reputation on it, then don't complain when it gets modded -1.
Human Rights, Article 12: Freedom from Interference with Privacy, Family, Home and Correspondence
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.
>how, exactly, we'll be able to secure our data once quantum computing becomes widely available
Look here
Summary..
Encryption and symmetric signing will need to double the key size for the same security bound.
RSA, ECDH and ECDSA will be insecure.
So key management goes back to the pre-DH days.
I should use this sig to advertise my book ISBN-13 : 978-1501515132.
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.