Schneier on Security
A blog covering security and security technology.
« DNA Surveillance in the UK |
| Face Recognition Comes to Bars »
February 28, 2006
Quantum Computing Just Got More Bizarre
You don't even have to turn it on:
With the right set-up, the theory suggested, the computer would sometimes get an answer out of the computer even though the program did not run. And now researchers from the University of Illinois at Urbana-Champaign have improved on the original design and built a non-running quantum computer that really works.
So now, even turning the machine off won't necessarily prevent hackers from stealing passwords.
And as long as we're on the topic of quantum computing, here's a piece of quantum snake oil:
A University of Toronto professor says he can now use a photon of light to smash through the most sophisticated computer theft schemes that hackers can devise.
EDITED TO ADD (3/1): More information about the University of Illinois result is here.
Posted on February 28, 2006 at 1:14 PM
• 27 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
So the basic concept behind quantum encryption is that intercepted bits are 'tamper evident'. Intercepting a photon to read its state prevents that state from being handed on to the recipient unaltered.
However, there are ways to intercept such photons with a better than 80% chance of not altering the state of the photon. Add to that the fact that over long distances any type of communication may have bit errors, and the certitude behind quantum encryption disappears. See the link for more info.
"Until recently, it was thought that such information couldn't be transferred more than 8 kilometres. But Lo's laser modulation technique increased that to 60 to 100 kilometres."
Oh - so he didn't invent this, he just extended the range? Funny how this relevant detail is at the bottom of the story.
I guess nobody told him about recents experimental successes in breaking quantum key exchange using quantum telecloning:
So if you don't have to turn it on to get the answer, do you have to ask or even know the question?
Why even have a piece of hardware .. just imagine it's all there.
I'll believe this stuff when I see it -- on "Startgate SG-1".
I've always maintained that there is profound meaning in not doing anything. I have modeled my life after that principle (called the 'Zero Effect'). I am delighted that my stand is vindicated by the sometimes-not-running-quantum computer.
Ironically, the researchers have published and publicized their work using conventional means. They should have eaten their own dogfood - simply spam the whole world from the non-running-state quantum computer to gain ultimate publicity.
Maybe a quantum computer could give answers before it's even built! That would be really cool!!
The trick here is the definition of "computer". The "quantum" "computer" described in the article is capable of performing a single calculation. Calling it a quantum "NAND Gate" would be an exageration.
Let's try an analogy: If I have a "computer" that takes an 8bit integer and adds one to it, then it is possible for me to know the answer of the calculation based solely on the input and the design of the "computer" without ever turning the "computer" on.
That is the sort of snake oil that this quantum "computer" story is about. Your password is safe from quantum computers as we're many orders of magnitude away from building a quantum computer sophisiticated enough to be a 1980's-style pocket calculator.
This is a good book:
A Shortcut Through Time: The Path to the Quantum Computer by George Johnson.
Provides a cogent explanation of what a QC could be. Somewhat hard to fathom for Si trained brains.
In regards to the snake-oil story...
If looking at the photons changes them so you can't decrypt them, how is the other end supposed to decrypt them?
"I've created a liquid that will melt through any substance on earth... and I have it right here in this glass beaker."
The "snake oil" link appears to be merely a poor (or deliberately lazy) attempt by some reporter to describe quantum cryptography.
> However, there are ways to intercept
> such photons with a better than 80% > chance of not altering the state of the > photon...
I don't think that really matters. You could just encode your bits into strings of bits, where the data is the XOR of all the bits. Now an eavesdropper has to read all of them (possibly modifying each) to get at one bit of information.
If, Alice knows the polarization when she encrypts, as the article suggests, then it's too late.
By observation Alice has collapsed affected the phonton, and frozen its state. It now remains in an "observed state" all the way to Bob.
If I'm wrong please let me know; I'll have to go back and re-read my Brian Greene. :-)
Gabriel said "Maybe a quantum computer could give answers before it's even built! That would be really cool!!"
I seem to recall a great story somewhat along these lines in Arthur C. Clarke's "Of Time and Stars"...
Not sure which one, it may even have been a different book, or perhaps a memory of a different past/future...
i don't think the article deserved to be called "snake oil". the underlying physics is sound, the commentator's hyperventilation "one of nature's smallest and strangest particles, which can weirdly morph into a wave..." is regrettable.
i remember a piece (scientific american i think) describing how an object could be imaged using quantum technology without any photons actually interacting with it. it's but a short step to turned-off computers giving us useful answers, and i will be grateful to be spared the boot time. i do some of my best processing when i'm turned off.
may be quantum computers around the universe are trying to get in touch with us.
>I don't think that really matters. You could just encode your bits into strings of bits, where the data is the XOR of all the bits. Now an eavesdropper has to read all of them (possibly modifying each) to get at one bit of information.
You could, and that would solve the 80% problem, but quantum encryption is hyped as if it were THE solution, so, given the human factor of overconfidence in one technolgical solution, they would not even think of that. Also bit errors in long distance communication would have a much greater impact with your XOR suggestion.
Basically, quantum encryption is not really encryption and it does not solve most of the problems of encrypted communication. Quantum encryption is the OTP of theoretical physics.
Dismissing a research field as "snake oil" based on a popular news article is irresponsible. Most of the Toronto Star article is a poor rehash of "the magic" of quantum key distribution that has been known for quite some time; the only new thing being reported is a possible extension in range by Hoi-Kwong Lo's team.
For those discussing bit-errors and the possibility that an eavesdropper could obtain up to 80% of the bits in the transmitted data, this is all taken into account in the later classical postprocessing protocol.
Basically, quantum key distribution protocols (which is what they are, not "quantum encryption" protocols) are composed of two stages. The first stage is the quantum stage, where, effectively, entangled states are established between Alice and Bob, and then measured to obtain correlated classical bitstrings. The second stage is the classical postprocessing stage, where a secure key is distilled from the correlated bitstrings. Because of the Bell inequalities about entangled states, Alice and Bob can compute a bound on the amount of information Eve could have obtained in transit, and then "compress" their correlated data sufficiently to leave Eve with negligible information about the final key.
Note that the classical stage of the protocol requires an authenticated classical channel: Alice and Bob need to be able to identify each other and verify messages signed by the other party. This is no different than any other communication protocol: you cannot create security out of nothing. In SSL, for example, a client has something already in order to authenticate the server: the CA's certificate.
The essence of the experiment is the same as the quantum "bomb detector" ( http://tinyurl.com/ccwrt ). The computation will give a result, a string of bits. For simplicity, I'll consider a single bit. On one path, the computation runs, and absorbs the photon if the result of running the program is 1 or lets it go through if the answer is 0; on the other, nothing happens. You add mirrors to make the two paths intersect at another semisilvered mirror and put detectors on the other side. If a certain detector clicks, then clearly the photon wasn't absorbed by the computation--but that detector couldn't have clicked if the result of the computation wasn't 1.
P.S. This won't make things go any faster: the photon has to have had the chance to run the computation, so you can't hope to solve a potentially infinite computation like searching for a counterexample to Riemann's Hypothesis this way.
Amazing what people are prepared to believe.
What's so amazing? A broken watch still gives the correct time twice a day.
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.