Code-Breaking Quantum Algorithm On a Silicon Chip 133
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."
How many qubits? (Score:3, Informative)
Re:Is this really a big deal? (Score:5, Informative)
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.
Re:Interesting and a qustion (Score:5, Informative)
Currently, they and the traditional techniques can each manipulate 4 non-error-checking qubits. =]
The article argues that their approach is more promising for scaling up, though, and has fewer inherent limits to doing so. That of course is still to be demonstrated, but the result still seems interesting--- basically, here's proof-of-concept of a new method that at least works as well as previous methods, along with some reasons to believe it might scale up better.
Re:What about ECC? (Score:4, Informative)
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.
Re:Interesting and a qustion (Score:5, Informative)
Re:Is this really a big deal? (Score:5, Informative)
Re:Interesting and a qustion (Score:2, Informative)
My guess is that miniaturizing a optical processor into silicon is probably going to be less powerful than normal optical processors.
The power of a quantum computer, at this early stage, is limited by the number of qbits. The point of putting it onto silicon is that silicon fabrication is the easiest way, right now, to make large numbers of interesting small structures. (in this case qbits and controlling infrastructure)
1-time pads are inherently unbreakable (Score:2, Informative)
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.
Depends on What Features You Want (Score:3, Informative)
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".
Re:Interesting and a qustion (Score:5, Informative)
This is why government agencies want secure quantum links now. As even though there is no way for someone to decrypt their plans right now there's still a chance of the plans getting out once quantum computers do come about.
I have a feeling a lot of criminals will find themselves being arrested for past crimes once quantum computers do come about as all their past recorded conversations, no matter how encrypted, suddenly become decryptable.
Re:Is factoring np-complete? (Score:5, Informative)
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).
Re:Interesting and a qustion (Score:3, Informative)
In short, yes: Wiki [wikipedia.org] see also (with more math than I can handle) Berkley article [74.125.95.132]
So, yeah. Quantum computers of reasonable size get us discrete logarithms. This means that the Diffie Hellman key exchange can be reversed after the exchange if the attacker has a powerful enough quantum computer. The computer to break DH key exchanges would be powerful enough to also break the encapsulating RSA or similar exchange (even assuming RSA encryption AND signatures was used).