The phone they spoke over was the Russian version of the American STU-3, the technology having been stolen about three years before by a team working for Directorate T of the First Chief Directorate. The internal microchips, which had been slavishly copies, scrambled the incoming and outgoing signals with a 128-bit encryption system whose key changed every hour, and changed further with the individual users whose personal codes were part of the insertable plastic keys they used. The STU system had defined the Russians' best efforts to crack it, even with exact knowledge of the internal workings of the system hardware, and they assumed the the Americans had the same problems—after all, for centuries Russia had produced the world's best mathematicians, and the best of them hadn't even come up with a theoretical model for cracking the scrambling system.I doubt anyone could turn a souped-up ConnectionMachine into a quantum computer. But one could imagine some smart NSA scientists finding a way to simulate a variation of Shor's quantum factoring algorithm on such a device, well enough to break moderately long RSA codes. Just thinking.
But the Americans had, with the revolutionary application of quantum theory to communications security, a decryption system so complex that only a handful of the "Directorate Z" people at the National Security Agency actually understood it. But they didn't have to. They had the world's most powerful supercomputers to do the real work. They were located in the basement of the sprawling NSA headquarters building, a dungeonlike area whose roof was held up with naked steel I-beams because it had been excavated for just this purpose. The star machine there was one made by the company gone bankrupt, the Super-Connector from Thinking Machines, Inc., of Cambridge, Massachusetts. The machine, custom build for NSA, had sat largely unused for six years, because nobody had come up with a way to program it efficiently, but the advent of quantum theory had changed that, too, and the monster machine was now cranking merrily away while its operators wondered who they could find to make the next generation of this complex machine.
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Tuesday, December 14, 2004
Decryption by Clancy
Consider the following paragraphs from Tom Clancy's 1998
novel Rainbow Six.
Feynman showed that quantum mechanics can be simulated efficiently by quantum computers but not by classical computers. Specifically, quantum computers suffer at most a polynomial slowdown, while classical computers suffer an exponential slowdown. This implies that classical computers cannot efficiently simulate quantum computers, which helps explain the buzz about recent developments in quantum computation.
ReplyDeleteThus, implementing Shor's quantum algorithms on a classical computer will be inefficient, and most likely worse than a more direct attack. As it happens, it's been done, and while the author of that paper doesn't seem to have included performance numbers, it's clear from considering the data structures that they are fairly poor.
Second, a six year old system along the lines of the Connection Machine line wouldn't be state of the art today. Off the shelf processor speeds, node interconnect speeds, memory and hard drive sizes, etc., have improved sufficiently in the intervening time that the idea that the NSA would be using such a system is implausible. Far more likely that they would buy a bigger and better Blue Gene or the like.
In short, Clancy didn't do his homework on this one.
Clancy doesn't claim that they've simulated a quantum computer with the Super-Connector. He says that programming the computer was prohibitively inefficient until they found a way to apply quantum theory.
DeleteJust thinking out loud? What about Adleman's DNA computer?
ReplyDeletenot related, a suggestion for new topic...
ReplyDeleteany thoughts on this article over at crooked timber ? (it deals with social networks and academic hiring)
http://www.crookedtimber.org/archives/002953.html