Re: Anyone seen the 'quantum cryptanalysis' thread?
At 12:11 PM 9/28/94 -0700, Timothy C. May wrote:
Alice switches to 15,000-bit moduli....the how much longer does it take the Shor machine to do its thing? (Even if polynomial, what factor?)
I won't speculate further. The numbers are indeterminate, even to Shor, I suspect.
In any case, nothing for Cypherpunks to worry about in our lifetimes (certainly not in my lifetime, and probably not in the lifetime of our youngest members).
It's easier to make an omlette out of eggs than to make eggs out of an omlette so encryption should remain well ahead of decryption. This differs from the popular view that decryption would eventually win the "war" with the encryption and devise a way of defeating *any* possible code/cipher. This "fact" was expressed in Edgar Rice Burroughs' Mars stories where he said that the Martians didn't use codes much because they were vulnerable. See also Sneakers in which we have a "black box" decyption device that can break any code. Also the guy who confronted me at the London conference last year and said "they broke the satellite movie coding system so why can't they break PGP?" I wonder where this idea comes from. DCF "Who was shocked, shocked by the end title sequence in Sneakers which features a newsreader describing how good commie liberals like the Robert Redford and Dan Ackroyd characters are using their decoding device to steal money from the Republican National Committee and transfer it to Greenpeace and all the usual suspects. Looks like those guys don't believe in democracy. That sort of thing is worse than the Watergate break in."
Duncan Frissel writes
This differs from the popular view that decryption would eventually win the "war" with the encryption and devise a way of defeating *any* possible code/cipher. This "fact" was expressed in Edgar Rice Burroughs' Mars stories where he said that the Martians didn't use codes much because they were vulnerable. See also Sneakers in which we have a "black box" decyption device that can break any code. Also the guy who confronted me at the London conference last year and said "they broke the satellite movie coding system so why can't they break PGP?"
I wonder where this idea comes from.
Casually looking at the history of the past 100 years or so of cryptanalysis, particularly what has been recently revealed recently about US/British triumphs in World War II, shows a number of startling successes against what were thought (and even now seem to ordinary minds) to be intractable ciphers. It is not very hard to see why popular mythology, which usually lags the cutting edge of science by at least several years and even sometimes several decades emphasizes decryption. After all, decryption seems to have been winning the last time we were allowed to have a look. It is also true that a quirk of human nature that probably has a lot to do with the origin of religion tends to mythologize to vast, even epic status those who can do something that ordinary people can't. And this hero/god dieification often involves the myth of unlimited power, which in the case of crypto means the ability to break any cipher. It will take a while before appreciation of the fundemental revolution represented by number theory based ciphers sinks in. Even the simple understanding that there exist unbreakable ciphers right now that anyone with a floppy disk drive can implement is too advanced to sink in very far. But probably the worst myth is the notion that most practical crypto systems were actually intended by their creators to be unbreakable. And of course nobody out there understands that satellite TV pirates have yet to break any cipher at all (at least as far as I know as someone who follows this technology). All the current triumphs have been based on exploiting holes (mostly involving cloning) in the key distribution and management in an environment where your enemy both necessarily has the complete cipher device and several copies of known to work keys. Dave Emery
Duncan Frissell and Dave Emery have commented on the popular notion that all codes and ciphers will "eventually" be broken. Dave Emery wrote:
Casually looking at the history of the past 100 years or so of cryptanalysis, particularly what has been recently revealed recently about US/British triumphs in World War II, shows a number of startling successes against what were thought (and even now seem to ordinary minds) to be intractable ciphers. It is not very hard to see why popular mythology, which usually lags the cutting edge of science by at least several years and even sometimes several decades emphasizes decryption. After all, decryption seems to have been winning the last time we were allowed to have a look.
On the other hand, Bamford pointed out in 1982 (in "The Puzzle Palace") that no significant Soviet cipher had been broken _directly_ for at least a decade, as near as he and other experts could tell (there are clearly uncertainties in what the NSA was able to do, but this wa Bamford's best estimate). Ditto for the Soviets not having broken U.S. ciphers in at least as long a time. What code and cipher breaking had occurred had generally happened through HUMINT sources, as with the Walker spy ring (which sold old code books, allowing earlier traffic to be reconstructed). Black bag jobs, bugging of buildings, etc. And I have no idea what crypto material Aldrich Ames transferred.
It will take a while before appreciation of the fundemental revolution represented by number theory based ciphers sinks in. Even the simple understanding that there exist unbreakable ciphers right now that anyone with a floppy disk drive can implement is too advanced to sink in very far.
I agree. Even Tom Clancy mythologizes crypto and usually gets it wrong. ...
as someone who follows this technology). All the current triumphs have been based on exploiting holes (mostly involving cloning) in the key distribution and management in an environment where your enemy both necessarily has the complete cipher device and several copies of known to work keys.
Exactly. In fact, at the last physical Cypherpunks meeting I arrived a few minutes late, in the midst of a debate about whether noise sources from audio inputs were "random enough" to defy cryptanalysis by the NSA. After listening for a while I had to speak up: In the history of modern cryptanalysis is there _any_ evidence that a single message has been broken because of something like this? I speculated that any slight reductions of entropy, thus allowing slight increases in the ability to predict the bits, are dwarfed by many orders of magnitude by more practical concerns. For example, the proliferation of keystroke capture utilities which capture and store all keystrokes entered for later retrieval. (I acknowledge the importance of high entropy noise sources, I just question the nit-picking about it when such much more tractable attacks exist.) --Tim May -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. Cypherpunks list: majordomo@toad.com with body message of only: subscribe cypherpunks. FAQ available at ftp.netcom.com in pub/tcmay
[sorry if this is way out of it, I haven't had time to keep up with my c-punks mail lattely] Duncan writes
It's easier to make an omlette out of eggs than to make eggs out of an omlette so encryption should remain well ahead of decryption.
As I'm sure somebody else has pointed out somewhere along this thread, the ability to simultaneously analyze a superposition of an arbitrarilly large subset of all possible imputs (as our theoretical quantum cryptanalytic device might) implies to ability to solve, in polynomial time, any exponential time problem. [Its easy to consider a device which, given a superposition of a subset of all numbers less than 2^n, delivers as output a confirmation or denial that one of the numbers in the subset is a factor of the input modulus. Such a device can factor in order n time complexity simply by playing higher lower games and guessing one bit at a time] I want to take issue Duncan's analogy here however. It starts off well:
"It's easier to make an omlette out of eggs than to make eggs out of an omlette"
This is like saying entropy always wins, which it does. It will always be easier to take apart and destroy than to create. Then he continues:
So encryption should remain well ahead of decryption
Which process is increasing order and which process is increasing entropy? I think an encrypted message is a highly ordered construct. In its natural state, information can be read by everyone. Upon this state encryption imposes order. It allows a specific subset of all entities to read the information. In the total cyberspatial system, none of the original information has been lost, yet new information has been added. I look at encryption as the tool that will allow us to build up an orderly society within the natural anarchy of cyberspace. Encryption is an artifact of order. And as such I would expect science to eventually uncover a mechanism that makes it easier to breakdown this order than to create it in the first place. I suppose it is plausible that there exists a class of Quantum-Hard problems, but it is difficult for me to conceptualize such a class of problems. It seems like quantum computation is capable of decreasing the time complexity of any problem to its logarithm an arbitrarilly large number of times. [Not that I believe for one moment that it is likely that quantum cryptanalytic machines will be developed that are sufficiently fault tolerant (if the term can even be applied to a system like this) to overcome the coupling between the quantum computer and the surrounding environment in the next couple of decades.] Cheers, Jason W. Solinsky
As I'm sure somebody else has pointed out somewhere along this thread, the ability to simultaneously analyze a superposition of an arbitrarilly large subset of all possible imputs (as our theoretical quantum cryptanalytic device might) implies to ability to solve, in polynomial time, any exponential time problem.
I just wanted to point out that I'm not sure this is true. I might be wrong; I'm a total newbie here. However, my impression was that it is *not* known that "anything in NP is solvable in quantum polytime (BQP)". I think it's been shown that, relative to a random oracle, it's not true that NP is contained in BQP. Then again, I'm told that oracle results are often misleading and usually not worth a bean. <shrug> I don't know much about this stuff. :-( [This oracle result is mentioned in Schor's paper.] Hopefully someone more clueful than I will explain this stuff :-) ------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu
As I'm sure somebody else has pointed out somewhere along this thread, the ability to simultaneously analyze a superposition of an arbitrarilly large subset of all possible imputs (as our theoretical quantum cryptanalytic device might) implies to ability to solve, in polynomial time, any exponential time problem.
I just wanted to point out that I'm not sure this is true.
I might be wrong; I'm a total newbie here. However, my impression was that it is *not* known that "anything in NP is solvable in quantum polytime (BQP)".
Well its quite possible that I am wrong since I didn't exactly have the easiest time reading the papers on the subject. But this is my reasoning: If you can create a machine that gives you a yes or no result (yes at least one of the subset of possible inputs entered into the machine contains the properties you are looking for [i.e. does not destructively interfere], or no there aren't any) then you can construct an quantum computer that tests for the property(s) the correct answer must have (in the case of factoring, the machine will test whether or not inputs divide the modulus). You can now repeatedly enter as inputs superpositions of inputs that include precisely half of all inputs that might (given the information that has already been gathered) be correct). You will now be able to mount a brute force attack searching through 2^n possibilities in order n time. It should be possible to nest these machines (although admitedly this does nasty things to the physical complexity of the quantum computer. It doesn't seem like the complexity would grow exponentially in the case of nesting [in fact it seems like it would go quadratically with the nesting level] but I'd have to think about it some more before I could claim to be confident of that.) thus allowing us to reduce any problem of time complexity e^X(n) (where X is either a polynomial in n or of the form e^X(n) [this goes on recursively]) to a problem of polynomial time complexity. JWS
solman@MIT.EDU writes
As I'm sure somebody else has pointed out somewhere along this thread, the ability to simultaneously analyze a superposition of an arbitrarilly large subset of all possible imputs (as our theoretical quantum cryptanalytic device might) implies to ability to solve, in polynomial time, any exponential time problem.
As far as is know, quantum computers cannot solve NP complete problems in polynomial time. They can solve some problems (such as factoring) that classical computers cannot solve in polynomial time. -- --------------------------------------------------------------------- We have the right to defend ourselves and our property, because of the kind of animals that we James A. Donald are. True law derives from this right, not from the arbitrary power of the omnipotent state. jamesd@netcom.com
participants (6)
-
Dave Emery -
David A. Wagner -
frissell＠panix.com -
jamesd＠netcom.com -
solman＠MIT.EDU -
tcmay＠netcom.com