I just finished reading Lee Smolin’s The Trouble with Physics. No, I’m not going to review it. What do you think I want the Quantum Pontiff to turn into a gigantic ball of flaming flamable flame wars? (The publisher actually was supposed to send me a copy and may still, but with my moving it may have missed me. But not to worry I went out and bought a copy myself because I couldn’t resist.)
Actually okay here is a two second review. The book is a fast, interesting read and I recommend it to anyone who is curious as to what all the fuss on certain websites is about without having to wade through a vast collection of comment tirades. Contrary to what you might expect, loop quantum gravity is not trumpted up as an alternative to string theory in the book, instead Smolin focuses on what he sees are the challenges string theory faces and then also about how he thinks the sociology of academia causes problems at a time when revolutionary new ideas are needed (which is what Smolin argues is required to get beyond our current status in the search for a quantum theory of gravity.) This later part of the book is interesting irrespective of your views or understanding of string theory and Smolin makes the case that the academic system has a lot of weaknesses when it comes time for truely new physics.
But okay, enought about the contents of the book that I’m not qualified to comment on. Lee Smolin actually mentions quantum computing multiple times in the book. Now first I have to take him to task because I am a nitpicking little son-of-a, and I just can’t help myself. Smolin writes
In 1994, Peter Shor of MIT, who was then a computer scientist at Bell Laboratories, found a remarkable result, which is that a large enough quantum computer would be able to break any code in existence.
Whoops. No, Shor’s algorithm can break the main public key cryptosystems those based on the difficulty of factoring and the discrete logriathm, but there are still public key cryptosystems which are so far resistent to both quantum and classical attacks (like those based on certain shortest vector in a lattice problems.) So quantum computers can’t break any code in existence. But, all is well, because in the next few sentences Smolin pays quantum computer some amazing props:
..Since then money has flooded into the field of quantum computation, as governments do not want to be the last to have their codes borken. This money has supported a new generation of young, very smart scientsits- physicists, computer scientists, and mathematicians. They have created a new field, a blending of physics and computer science, a significant part of which involves a reexcamination of the foundations of quantum mechanics. All of a sudden, quantum computer is hot, with lots of new ideas and results. Some of these results address the concerns about the foundations and many could have been discovered anytime since the 1930s. Here is a clear example of how the suppresion of a field by academic politics can hold up progress for decades
See he called quantum computer people “young” and “very smart!” That’s like being called “cool” in physics language! Now if only quantum computing could follow string theory’s example and populate physics departments across the country. Perhaps those in control of U.S. physics deparments who have hired a number of quantum computing theorists countable on fingers over the last few years have secretely been doing us all a big favor by keeping us from becoming overhyped and overpopulated. Or at least overpopulated.
My impression about Shor’s algorithm was the same as Smolin’s. Do you have a link for “certain shortest vector in a lattice problems”? I’d be curious to learn more.
Hey Walt, a reference is Oded Regev’s review which is at http://www.cs.tau.ac.il/~odedr/papers/crypto2006.pdf
In addition to the lattice based systems, there are also some based on the hardness of distinguishing error correcting codes, see here http://en.wikipedia.org/wiki/McEliece_cryptosystem
Regarding quantum computing versus cryptographic systems based on lattice problems, see also the explanation of NTRU at http://www.ntru.com/cryptolab/faqs.htm#twentyoneA
I think that in order to populate physics departments the way you want, you will need to reproduce. Preferably with another quantum computer scientist. Possibly many many times. 😛
Thanks! I think I see how I formed the impression that I did. I had the vague impression that cryptosystems were all based on problems thought to be of intermediate difficulty between P and NP, and that all of the known such (other than graph isomorphism) were number-theoretic, and thus amenable to Shor-type algorithms.
Smolin’s statement is correct for _practical_ asymmetric (public key) encryption systems whose security is widely agreed upon by the cryptographic community. (It is too strong because quantum algorithms haven’t touched the security of symmetric key encryption systems.)
McEliece is not practical; according to The Handbook of Applied Cryptography, for the recommended security parameters the public key size is 2^19 bits, which will be unwieldy for most applications for the foreseeable future (also the data expansion factor is about 1.6). Also because of its impracticality its security has received less scrutiny.
NTRU: According to Koblitz and Menezes’s A Survey of Public Key Cryptosystems (http://citeseer.ist.psu.edu/695523.html), “a history of successful attacks on various versions of NTRU makes many people hesitant to endorse its use.â€
My impression is that the Ajtai-Dwork lattice based system, and its successors, also have impractically large public keys, even after the improvement by Regev. Can anyone confirm this? (Also Regev has shown that these systems would be broken by any quantum algorithm for the dihedral HSP involving coset sampling. So these systems depend on a problem closely related to those Shor’s algorithm solved, though that problem has proven difficult.) Does anyone know the relation between these lattice based systems and NTRU?
Koblitz and Menezes’s A Survey of Public Key Cryptosystems also discuss PKE cryptosystems based on braid groups which are widely believed to be insecure. They also mention systems based on hidden monomials. Anyone know the status of those? Many versions of knapsack based PKE cryptosystems were broken so that people are pessimistic about using this problem as the basis for a PKE system. Many other types of PKE cryptosystems have been developed and then broken.
Given the historic difficulty of creating practical PKE cryptosystems based on problems other than factoring or discrete log, here’s a question I believe is open to debate: which will come first, the building of quantum computer capable of breaking existing factoring and discrete log PKE cryptosystems or the development of a practical PKE cryptosystem which is widely believed to be secure against quantum and classical attacks?
Hey Eleanor, thanks for the run down! I agree that when you restrict to “practical” Shor seems to be a killer! (I feel bad for making much of a fuss about this statement in Smolin’s book as the rest of the book has very few of the types of errors that occur when you write a popular science book and have to simplify things. I mean it is SO SO SO much better than a certain famous physicist who thought that the power of quantum computers came because they could efficiently multiply two numbers.)
My impression was that Regev’s improvement moves the lattice based systems not to the level of RSA et al, but much closer to practical.
At least some of the braid group PKE cryptosystems have been broken. See http://crypt.kaist.ac.kr/pre_papers/LeePark.pdf
I also seem to recall that there was one version of the knapsack PKE which wasn’t broken? Sorry I can’t find the paper in any of my files.
I like your question. Many have speculated that quantum computers would break ALL PKE cryptosystems (evidence towards this being, as you mention, the close relation of the lattice cryptosystems to hidden subgroup problems. McCliese can also be solved by a certain hidden subgroup problem.) My conjecture is that the “practicality” (size of key, data blow up) is related to the complexity of the quantum algorithm which will break that PKE crytopsystem.
Dave,
Were you thinking of the Chor-Rivest knapsack scheme? It was proposed in 1988 and had a good run, but was broken ten years later by Vaudenay. If there’s another knapsack scheme still standing, I’d definitely like to know about it.
Yes, various braid group based schemes have been broken in serious enough ways that people are pessimistic about being able to build a braid group based PKE system.
I’m not sure of the status of hidden monomial based systems.
Thanks for your thoughts on these questions.
On a slight tangent, have any of you seen the Bruce Schneier Facts webpage?
Be warned, it’s painful. Oh, and it’s a crypto parody of the Chuck Norris facts, in case you haven’t seen it already.