Slashdot Mirror
Quantum Computing Breakthrough in Japan
An anonymous reader writes "A research team funded by NEC and RIKEN, Japan's Institute of Physical and Chemical Research, are the first to demonstrate a Controlled NOT (CNOT) quantum gate. The CNOT gate when coupled with a rotational gate would create a universal gate. The universal gate would be the basis for quantum computing. ETA for the first quantum computers: 10 to 100 years." When quantum computers first come to fruition, the best part will be reminiscing about how terrible computers were "back in the day."
Actually, we know lots of things that can run on these computers. For example, Shor's algorithm. Quantum computers are hard to program, but the killer app has already been written.
The availability of quantum computers for encryption cracking will just result in a change to another type of cryptography that does not rely on the unproven assumption that factorizing large integers is NP hard. These future encryption methods may be less mathematical and more physical.
taken! (by Davidleeroth) Thanks Bingo Foo!
Yeah but encryption will catch up just as fast. You can break codes from WW2 now with what? A 486DX and 15 seconds of CPU time? It's all relative. Besides, we should all be using OTPs anyway
A little knowledge is a dangerous thing... keyword here being "little". Allow me to correct a few points:
1. No, encryption won't catch up just as fast. Currently, encryption enjoys a Big-Oh advantage over brute force cracking. Encryption is O(1) and cracking is O(n). [n is keyspace, not key bits]. If quantum computers take away that advantage, encryptions will not "catch up just as fast".
2. No, you can't break codes from WW2 with 15 seconds of CPU time on a 486. Enigma was broken in WW2 due to a weakness in the cipher. The later Enigma machines had 67 key bits. That's a fair bit more than DES. No way could you crack that (by brute force) on a 486.
3. "Besides, we should all be using OTPs anyway." Not sure if this is ignorance or a weak attempt at a joke.
-a
In a regular computer, data flows through "static" gates. In a quantum computer, the data (qubits) is stationary and the "gates" are in fact carefully crafted laser pulses (the article is not very specific about this particular CNOT gate though)
1-2 qubits is easy. More qubits are quite difficult to put together. That's why most of the current quantum computers barely do 10 qubits.
Errors are of analogical nature. Correcting them (with Q-ECC codes) is quite expensive - a more reliable qubit requires a couple normal qubits and gates (I say more reliable because the whole thing is probabilistic)
Quantum data is very "transient" - it cannot be copied. It can be teleported however (teleportation destroys the source). Storage is however difficult (keeping a superposition of qubits coherent for humanly-observable times is almost intractable)
A quantum computer can do an operation on 2^k superpositions at the same time (in other words, exponential work in constant time). Selecting the "right" answer from the superposition of 2^k results takes however 2^(k/2) (Lov Grover's algorithm) - so it's still exponential. This is one of the reasons quantum computers were not shown to be more powerful than regular ones (i.e QP != P) . Yes, Shor's factorization algorithm works in polynomial time on quantum computers, and is furthermore quite efficient, but factorization has been shown to be in P anyway (although the current "regular" algorithm is not efficient at all)
The Raven
Modern schemes wouldn't be necessary because quantum cryptography would become the standard and is proven to be unbreakable by the laws of quantum mechanics. Any interaction (malicious or otherwise) of a third party is noticable to the proper parties and the message/key transmission is just repeated until a clean send is achieved.
Here, here and google (of course) provide some good reading if you're interested
If You Drink, Don't Park, Accidents Cause People.
One of the problems they have found with radio noise is that if you take your samples too close together you get too many strings of either 1111, 0000, or 10101010. While all three of these strings, as well as many of the permutations are perfectly normal as part of a truely random process, it doesn't do much for your encryption process if you xor your raw text with a string of zeros.
The problem with most algorythmic random number generators is that if you can collect enough samples you can figure out what function created those samples, and reproduce the original OTP and decrypt the original message.
For messages that are not extreamly complex, it is often better to use a code instead of a cypher. The difference being a cypher takes the original message, and sends it encrypted with a key that when applied properly returns the original message. A code is generally harder to decrypt simply because the original message is not transmited. Only a reference to that message is sent.
As an example if you and I agree that one light means that the rascals are going to road march into town, and two lights means that they have figured out how to use boats, you have a simple code that can be used to send a simple message many miles without having someone in the middle. The rascals using the boats are also very unlikely to decode the message.
More complex messages would require more complex codes being sent. A CD, or a DVD would potentially provide enough raw space as a code book, but you would want to be very sure that no-one who was not supposed to, got copies of the disk. (no sharing them via p2p networks).
The longstanding myth was that you could recognize the Russian spy operatives because they always carried around big heavy books. War and Peace might have been long, dull and boring for a reason.
-Rusty
You never know...
You shouldnt confuse quantum computing with quantum cryptography. Quantum cryptography, even with a quantum computer, would still be unbreakable because of how it utilizes the randomness of photons, one time pads, and one hell of an anti-easedropping mechanism.
Quantum computing would also have a far more severe impact on modern cryptography than breaking it "really quickly". With the ability to instantly factor every large prime, for example, it would nullify the best we've got.
Recursion (n): See recursion
The problem with most algorythmic random number generators is that if you can collect enough samples you can figure out what function created those samples, and reproduce the original OTP and decrypt the original message.
Yes, but with a decent strong pseudo-random number generator, this is equivalent to breaking the crypto algorithm they're based on. Consider even the most basic counter-mode cipher, where output block n is e_k(n), where k is the secret key. Predicting the next output from a bunch of data (other than that it's not one of the ones you've already seen) is equivalent to a known-plaintext attack on the cipher.
There are ciphers called "stream ciphers" that generate random-looking data from a short key, then you XOR it with your message. RC4 is the best-known one, and many programmers have the (very simple) algorithm memorized. There is no publically-known way to figure out the key from the samples.
More complex messages would require more complex codes being sent. A CD, or a DVD would potentially provide enough raw space as a code book...
This is just silly. If you want theoretical unbreakability, you put a one-time pad on the CD. If you want practical unbreakability (as far as anyone knows outside the government), you encrypt the message with a symmetric key, then encrypt the symmetric key with the recipient's public key and send it.
The longstanding myth was that you could recognize the Russian spy operatives because they always carried around big heavy books. War and Peace might have been long, dull and boring for a reason.
War and Peace would make a lousy codebook, because anyone can get a copy. Once they guess you're using War and Peace, and how you're using it, the code is broken, so the secret might as well be just the code itself.
I hereby place the above post in the public domain.
Anyway, RSA can be broken by factorization. Diffie-Hellman however requires the inversion of the discrete exponential function. While quantum computing can factorize in P-time, it cannot inverse an arbitrary function in a reasonable amount of time. It can do it more efficiently than a normal computer (2^(k/2) time as opposed to 2^k with Lov Grover's search algorithm, where k is the number of bits), but it's still exponential.
In any case, I wouldn't worry yet ... Shor's algorithm, for 512 bits, requires in the order of tens of thousands qubits (with realistic quantum error correction). So far the highest number of qubits that were put together is around 10.
The Raven
as long as a solution exists. not matter how improbable, it can be arrived at, as the gates in superposition go through all the possibilities simultaneously.
Well that's the catch. Yeah, a solution exists, but it's impossible to know if you have found it. If you have a message of length N encoded with a one time pad, then any possible message of length N is an equally valid solution. So if I send a message where n is 23, it could be decoded as "We attack at one thirty" or I could be saying "The pizza was real good", or any number of other solutions. To someone without the pad it's impossible to tell which is right.
We hope your rules and wisdom choke you / Now we are one in everlasting peace
OTP works by having a completely random key that is as long as the data itself. It is then combined with the data in some way (say, for example, XOR) and reversed at the other end given the correct key.
The key (no pun intended) here is that there is no way to know when you have the correct key. With the XOR example, there exist keys that will produce every possible combination of output bits, and no way to tell which one is right. So trying to decrypt it is no different than generating random bit patterns the length of the data and seeing which output "looks right" - even looking for outputs that are valid English, you will encounter every possible sentence of the given data length.
Didn't the Polish Resistance do it first?
Just reading in the number and printing it is O(n), unfortunately (takes time proportional to the number of characters of the input).
I believe posters are recognized by their sig. So I made one.
- Current architectures don't scale past about 7 qubits, which is barely enough to factor the number 15. Part of the problem is letting all the qubits in the system interact with each other. It's not even certain that a scaleable architecture can be developed.
- The quantum state of the machines decays very quickly, requiring a lot of error corrections for sustainable calculations. It's not a given yet whether such architectures are possible.
- Shor's algorithm is algorithmically faster than classical sieve methods for factoring numbers. However the constants involved are huge. No one knows where the curves cross yet (mainly because no one's built a large enough quantum computer to extrapolate from yet). It may require impossibly large numbers to benefit from Shor's speed advantage. I.e if Shor's is only faster than sieves on composites of 50,000+ bits, asymmetric crypto is safe.
- Symmetric crypto will barely notice when/if quantum computers appear. Grover's may be able to effectively halve the key size for brute-force searches, but it's gonna be much, much slower than a classical computer on that reduced size. A 256-bit key would be at least as immune to brute-force from quantum computers as a 128-bit key is to conventional machines.
- Quantum cryptography is a misnomer for the BB84 and BB92 protocols. These should be called quantum key distribution because that's all they do. You can't encrypt information with them, just exchange keys. You still need conventional crypto to use the keys with.
- There are indications that the quantum world might provide equivalents to digital signatures and possibly other asymmetric crypto primitives. However like quantum key distribution it requires a dedicated quantum channel (e.g. a single fiber optic cable) between the two parties. It's gonna be expensive to setup.
Basically, quantum computers and quantum cryptography will have little effect on the security world. Quantum crypto is only useful in ultra-paranoid, damn-the-expense applications (military, govt). Worse case scenario, the rest of the world has to give up asymmetric crypto and fall back on symmetric methods. Some infrastructure gets replaced and life goes on.I don't expect to see non-trivial quantum computers in the research lab for a minimum of 3 decades, though the professor sees them in 1.
Democracy is two wolves and a sheep voting on lunch.
Nah - you first send a random one time pad through the link. If not intercepted you send the real message off the link, encrypted with the one time pad. You need both to crack the message. If the pad was evesdropped you just toss it and try again. You could even keep using the same line hoping that the evesdropper would ignore one of the messages - if he lets a message pass unintercepted you could use that key to safely transmit the real message.
It seems to me that quantum computing will mean the end of privacy for consumers like you and me. Currently I can use a 4096 bit PGP key to encrypt something so that pretty well noone on earth, even those with the most massive supercomputers, will be able to see my secret message. Once quantum computing comes out this goes down the drain. If my 4096 bit key can be cracked in a few hours then I need to get a bigger key. Unfortunately at first these quantum computers will be reserved for governments only, for many people who use encryption that is exactly the type of people that they don't want spying on them (government conspirists). In order to match the raw computing speed of the governements massive quantum computer my athlon tbird 1400 may have to generate a 4294967296 bit key. A feat which may take days, even worse when this key is used for encryption. Personal privacy worked when computers merely scaled linearly (if you double the computing power , you basically double the processing power) but with the advant of quantum computers those rules just don't apply any more
History will be kind to me, for I intend to write it - Sir Winston Churchill
You may be thinking of Polish Military Intelligence, but they did not "break" Enigma as such. They managed to break an Enigma system - the combination of machine and method of operation - which was to modern eyes fairly weak. Just before the invasion of Poland in 1939 the Germans changed they system and the Poles could not read it anymore (not because they couldn't figure it out, but that the methods used to crack it were too slow - they couldn't build the bombes which were an essential part of the cracking).
The most significant thing they did was to workout the wiring of the Enigma machine itself. There are 26! ways to wire the machine, and one of the Polish mathematicians - Marian Rejewski - in a stroke of genius - managed to work this out.
The British Intelligence built on the work of the Poles at Bletchly Park duing WW2. Turing in particular produced what was called "The Prof's Book" which was a systematic method for breaking Enigma regardless of the system being used with it. Note that the cracking couldn't be done cold - in particular the woring of the rotors in the enigma machines were required (as well as the wiring of the machine itself - although oddly this was never changed).
What both the Poles and the Allies realised was that Enigma had a huge weakness - it could never encipher a character as itself. The German's knew about this, but thought it was just a quirk.
Later on Shark appeared. This was a cypher system similar to Enigma except it worked on teletype messages. To break this Colossus was born, but the same general idea worked. Ironically, although this was the first Turing machine*, Turing actually had very little directly to do with it.
Thus ends the "Miniature Guide to Codebreaking in Europe in WW2"
* Actually, the German Z3 was the first Turing machine, in 1941. This is not the usual case of "to the victor the spoils" as nobody was sure that the Z3 was a Turing machine until about 1990, althought Conrad Zuse, its designer, thought it might be. I've always vaguely wondered if, by using the same tricks, you could get the difference engine to become a Turing machine.
You can do it in open air, even during the daytime using optical frequency photons. That's what the folks at Los Alamos are doing. They have a range of about 10km now, and think that a satellite implementation should be feasible. If that happens (and you can trust the satellite) it would in principle enable secure communication anywhere.
Of course, right now the bit rate is pretty low (about 45,000 secret bits/hour in daylight, better at night), but that is mostly due to low yield on the detectors, which could hopefully improve over the next several years.
This is not the first controlled-not gate for a quantum computing system but rather the first in this solid state system.
Other implementations of a controlled-not gate (or its close relative, a controlled-phase gate) include:
Caltech Quantum Optics implemented a controlled-phase gate between photons using a strongly coupled atom in a cavity.
Serge Haroche's group implemented a controlled-phase between an atom and a photon using microwave cavities and atomic Rydberg states.
NIST Ion Storage Group: implemented a two qubit gate (which could be turned into a controlled-not) and a four qubit gate using trapped ions.
NMR quantum computing has been implemented by various groups including the biggest quantum computation to date, factoring 15, done by Isaac Chuang's group (IBM and now MIT.)
A proof of principle implementation of a controlled-not in the linear optics quantum computing scheme has been implemented at the University of Queensland.
I'm leaving out quite a few other cool experiments: but the above links should give you a good idea of the what early steps have been taken in quantum computing.