Slashdot Mirror
Code-Breaking Quantum Algorithm On a Silicon Chip
Urchin writes "Shor's quantum algorithm, which offers a way to crack the commonly-used RSA encryption algorithm, has been demonstrated on a silicon chip for the first time. The algorithm was first demonstrated on large tabletop arrays 3 years ago, but the photonic quantum circuit can now be printed relatively easily onto a silicon chip just 26 mm long. You can see the abstract from the team's academic paper in the journal Science; the full text requires a subscription."
So, this is really impressive. I'd also like to know how many (useful, as opposed to error checking) qbits they can manipulate in total using this technique, and traditional techniques, for that matter. Those are the big limiting factors in this technique's use.
Side question: Which asymmetrical encryption algorithms are safe(er) against quantum algorithms (Some algorithms do not benefit from a tremendous quantum speedup, only a large one)?
md5sum
d41d8cd98f00b204e9800998ecf8427e
they are still factorizing the number 15 :)
17779 eligible voters in a district, 17779 'vote' as one. This is Russia.
The IBM test-tube quantum computer from a while back used the spins of several atoms in a specially-crafted molecule as qubits. This one is "an integrated waveguide silica-on-silicon chip that guides four single-photon qubits through the computation". Does this approach scale better to larger numbers of qubits than do designer molecules?
shortly after, secret service agencies worldwide have decided to make the day a holiday and call it man in the middle day (MIM)
Never antropomorphize computers, they do not like that
They only factored the number 15 here as well--- in fact what they implemented was a version of the algorithm compiled to a specialized implementation for the input "15". Their claim from why it's an improvement is (from the full article):
Essentially they claim that, while their demonstration here is as small-scale as the previous ones, it's at least plausible that it might scale up, while the previous demonstrations have inherent limitations that prevent them from scaling up.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
my darknet effectively utilities rsa/blowfish. not for long apparently.
int a = 0, b = 0;
if (x == 14) { a = 2; b = 7; }
else
if (x == 15) { a = 3; b = 5; }
if (a == 0)
printf ("%s\n", "more funds required");
else
printf ("%d, %d\n", a, b);
All Discrete-Logarithm and Factoring based public key algorithms are vulnerable.
THe current known safe alternatives are hash-based (Merkle), code based (e.g. McEliece), lattice based (NTRU) or multivariate equation based (HFE). All of them have quite the disadvantages and comparatively less research on them.
You really don't understand the impact world wide reliable and fast code breaking has. Cryptology has won wars.
Anything above "4" is represented as "A Suffusion of Yellow"
Outside of science fiction novels, where did it do that? If you're thinking of WWII, the Allies had a gigantically larger industrial base than the Axis could ever summon, and basically won by throwing enough men and materiel at the problem. At most, crypto might have shortened that war, but even that's not crystal clear.
What part of "A well regulated militia" do you not understand?
Well, a truly random 1-time pad that is used properly and never compromised is mathematically unbreakable.
PRACTICAL one-time pads suffer two vulnerabilities: 1) If stored in the clear or encrypted with a defeatable algorithm, they can be compromised, and 2) if re-used they can be compromised. They are useful for sharing small amounts of data, such as passphrases.
One way to make one-time pads more practical for certain applications is to use shortcuts to describe the pads. For example, if you and I both collect Linux distros, then we can use the distros as one-time pads. Sharing a pad becomes as easy as saying "CentOS-5.3-x86_64-bin-4of7.iso start at byte 134,379,001 and wrap around" and poof, we've got ourselves a 629MB pad to play with. When that pad nears the end, one of our messages could be "ubuntu-8.04.1-dvd-i386.iso offset 1,423,783,047 backwards and wrap around" and that gives us another 3.9GB worth of pad. This relies on security through obscurity to work, which is notoriously fragile, which is one reason it's not a general-purpose solution.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
Outside of science fiction novels, where did it do that? If you're thinking of WWII, the Allies had a gigantically larger industrial base than the Axis could ever summon, and basically won by throwing enough men and materiel at the problem. At most, crypto might have shortened that war, but even that's not crystal clear.
Breaking Enigma helped get those men and materiel past the U-boats. If they hadn't D-day wouldn't have happened (and it was almost a failure even with the resource there) and the Germans wouldn't have been caught in a pincer between the allies and the soviets. I wouldn't discount its influence.
If all else fails, immortality can always be assured by spectacular error.
http://en.wikipedia.org/wiki/Ultra#Battle_of_the_Atlantic
It is commonly claimed that breaking of German Naval Enigma shortened the war by a year, but given its effects on the Second Battle of the Atlantic alone, that might be an underestimate.
An exhibit in 2003 on "Secret War" at the Imperial War Museum, in London, quoted British Prime Minister Winston Churchill telling King George VI, "It was thanks to Ultra that we won the war." Churchill's greatest fear, even after Hitler had suspended Operation Sealion and invaded the Soviet Union, was that the German submarine wolf packs would succeed in strangling sea-locked Britain. He would later write, in Their Finest Hour (1949), "The only thing that ever really frightened me during the war was the U-boat peril." A major factor that averted Britain's defeat in the Battle of the Atlantic was her regained mastery of Naval Enigma decryption.
echo -e 'global _start\n _start:\n mov eax, 2\n int 80h\n jmp _start' > a.asm; nasm a.asm -f elf; ld a.o -o a;
Sweet, thanks for the awesome pointers. You've given me a whole lot of stuff to look over as a research starting point.
I claim first use of "Error No. 0B" - or "No. 0B error." It'll be the new ID 10T!
The short answer is "It depends". It depends on what features you want. (Some crypto systems provide security but not authentication. Others do the opposite. Still others provide neither but give plausible deny-ability or even it's opposite, non-reputability.) It depends on what resources you have. (Do you have couriers to hand deliver your new keys?)
The reason quantum is scary is because it breaks a large number of public key systems. Public-key systems have been the most economical systems developed to date. Thus if quantum were to break all the public-key systems, it wouldn't necessarily kill all crypto, but it would make implementing crypto more expensive (e.g. couriers or quantum hard lines).
However, quantum might not break all public-key crypto. Public-key crypto only requires the existance of a function, f, such that f is easy to compute but the inverse, inv-f, is hard to compute. Usually "easy" is defined as "polynomial". Thus it is a trivial corollary that if someone can prove P=NP or that quantum can solve all NP in polynomial time. As far as I know no one has proven either so there is a glimmer of hope.
However, even if P=NP, I may still be possible to build a public-key crypto. While "n^100" time is technically polynomial, it really isn't computationally "easy". So even with P=NP there may exist functions that can be computed in a low-degree polynomial time (e.g. linear or quadratic) but who's inverse requires a high-degree polynomial.
All of this is a long winded way of saying "quantum breaks the public-key currently in common use but there is the theoretical possibility that someone may develop a public-key that won't be broken by quantum".
You're right, it isn't currently known either way.
To review briefly,
P problems are those solvable in polynomial time on a regular computer.
NP problems are (one definition) those verifiable in polynomial time on regular computers. That is, if you gave the answer to the problem, in polynomial time I could tell you if it was the correct one.
QBP problems are those solvable in polynomial time on a quantum computer.
It is not known whether any of these classes are equivalent. However, the possibilities are constrained by,
NP-complete, which are problems in NP to which all other NP problems can be reduced (provably!) in polynomial time.
Traveling salesman is NP-complete. Therefore, if we found a polynomial-time algorithm on regular computers, P = NP. If we found a polynomial-time algorithm on quantum computers, QBP = NP.
Integer factorization is in NP, but not known to be either NP-complete or in P. Therefore, a polynomial-time algorithm on regular computers could exist without P = NP--- but we don't know of one. Shor's algorithm (the subject of this article) is a polynomial-time algorithm for quantum computers, so integer factorization is in QBP. However, since integer factorization isn't NP-complete, this doesn't have any implications for whether QBP = NP or not.
So it's not provably known that integer factorization is easier than traveling salesman on any kind of computer. But on quantum computers, the fastest known integer factorization algorithm is polynomial, while the only way we could do that for traveling salesman is if QBP = NP. On regular computers, no polynomial algorithm is known for either problem. But in a sense it'd be more surprising if one were found for traveling salesman, because that would imply P = NP... while finding one for integer factorization wouldn't have such wide-ranging implications on other problems (though it might have implications for other not-yet-known-to-be-in-P problems, if the technique were transferable).
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
It's only frightening when operating a quantum computer becomes trivial.
"Congratulations on your purchase. To begin using your quantum computer, set the power switch to both off and on simultaneously."