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."
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!
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.
Recursion (n): See recursion
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
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.
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.