Recently there has been a lot of exciting work in cryptographic hash functions. Hash functions are functions which take some large (possibly infinite) domain, and map it to a smaller (usually of fixed size) range. Cryptographic hash functions are hash functions which are one-way and also collision free. One-way means that if H is the hash function, then, given H(x) it is computationally infeasible to determine x. Collision free means that if we are given H(x), then it is computationally infeasible to find a y not equal to x such that H(x)=H(y). Actually this is called weakly collision free. Stronly collision free is if it is computationally infeasible to find any two x and y not equal to each other such that H(x)=H(y). You may notice that there exist many collisions when the domain is larger than the range, but for a strongly collision free hash function, finding even a single collision is difficult.
One common use for cryptographic hash functions is in digital signatures. Instead of digitally signing the entire document, one almost always uses a hash function on this document and then digitally signs the resulting value. So if it is possible to construction documents which have the same hash value, then this whole scheme gets into trouble.
Recently two widely used cryptographic hash functions, MD5 and SHA, have been under attack. Work by a whole host of people, including papers by Wang and Yu, and Biham, Chen, Joux, Carribault, Lemuet, and Jalby has shown that it is possible to find collisions for these hash functions in computationally feasible times. But wait, you say, finding collisions doesn’t necessarily mean that we can’t use these attacks for the digital signature schemes we described above. You would think this because the results on breaking the cryptographic hash functions provide basically random collisions. For the specific task of creating a forged document with the same hash function, you might think these attacks don’t work. But you would be wrong! In fact, you can use these attacks to create forged documents with the same hash function. Magnus Duam and Stefan Lucks have a wonderful discussion and demonstration of this here. What is very cool is that they have two postscript files which both produce the same value after applying the MD5 hash function (a25f7f0b 29ee0b39 68c86073 8533a4b9, heh.) (Previously Kaminski and Mikle have also shown such capabilities.)
So…do you really trust MD5? I don’t.
Update: As Aram points out in the comments, this page has a cool list of hash functions and those that have been broken. Not a pretty picture.
Bend It Like Feynman
Next week I begin teaching. This is really the first course that I’ve fully taught-I’ve given plenty of summer school lectures, and guest lectures, and I was a teaching assistant through most of my years at Berkeley-but this is the first class that I’ve really been in total control of the class. The class is “Quantum Computing” and is in the professional masters program here in the Computer Science and Engineering department at UW. You can check out the course webpage here. But there’s not much there but a syllabus yet. The cool thing is that I get to teach this course the way I think it should be taught. On the other hand, this means that there are “no excuses”-the quality of the class rests squarely on my shoulders
Since this is the first time that I’ve actually had to lecture for an entire course (as opposed to being a TA, in which you aren’t the first person to tell the students about the material) I’ve been spending a bit of time contemplating what makes a good lecturer. One way I did this was to go back and read the “Feynman Lectures on Gravitation.” Something I’ve noticed about a large number of the good speakers and lecturers, including Feynman, is that while their actual vocabulary might be limitted, they almost universal express themselves in ways which are very unique. Reading Feynman’s lectures, there aren’t many sections which are just ordinary drolling on. Saying the ordinary in extraordinary manner appears to be vital to keeping a lecture going. And certainly this also adds to Feynman’s humor. Perhaps by expressing his thoughts in such strange manners, he is just naturally led to funny sentences such as
There are 10^11 stars in the galaxy. That used to be a huge number. But it’s only a hundred billion. It’s less than the national deficit! We used to call them astronomical numbers. Now we should call them economical numbers.
Indeed, if you read Gordon Watts blog, he put up a list one of his students had kept during his teaching of all the crazy things he said during the term. And you can tell, just by reading this list, that Gordon would make an excellent teacher. Now I just wonder if I need to tone up or tone down my crazy speak habits…
The Web Ate My Brain
I’ve started using the Greasemonkey script Webolodeon. This cool little script pops up a little screen every five minutes when you are surfing the web and asks you to justify why you are still surfing the web. Pretty cool and useful, I must say.
Hell Froze
Roger Waters to reunite with Floyd for Live8 concert. David Gilmour:
Like most people I want to do everything I can to persuade the G8 leaders to make huge commitments to the relief of poverty and increased aid to the third world. It’s crazy that America gives such a paltry percentage of its GNP to the starving nations. Any squabbles Roger and the band have had in the past are so petty in this context, and if re-forming for this concert will help focus attention then it’s got to be worthwhile.
And in other news, pigs can fly,
Approximating Zone
A new sign for outside my office:
Popular Science Hits the Spot
Friday I picked up How the Universe Got Its Spots : Diary of a Finite Time in a Finite Space by the astrophysicist Janna Levin. I met Janna once. Fresh off the factory floor at Caltech, I arrived at Berkeley having convinced the graduate school admissions people there that I was going to do particle physics. I really had no such intentions. I had decided I wanted to do astrophysics. Luckily I didn’t have to take the first year grad courses (so I’ve only been through Jackson, once, thank you very much!) so I was able to immediately start taking astrophysics classes. Having taken only one astro course at Caltech, I really had a lot of learning to do! But already in my first year I was trying to find some research to do: research was the reason I went to grad school, not to take classes. One of the people I visited was Janna Levin, who at the time was a postdoc. She gave me these really cool papers on chaos in black hole solutions as well as on the main subject of this popular book, what if the large scale topology of the universe is nontrivial. So I’m sure she doesn’t remember me, but I remember those papers on topology and also a paper she wrote with J.D. Barrow on the twin paradox in compact universes. I would be neglegent if I didn’t quote the Simpsons episode where Stephen Hawking makes an appearance:
Hawking: Your theory of a donut-shaped universe is intriguing, Homer. I may have to steal it.
Homer: Wow, I can’t believe someone I never heard of is hanging out with a guy like me.
Moe: All right, it’s closing time. Who’s paying the tab?
Homer: [imitating Hawking’s voice box] I am.
Hawking: I didn’t say that.
Homer: [still imitating] Yes I did.
[a glove comes out of Hawking’s wheelechair, bopping Homer in the face]
Homer: [still imitating] D’oh.
Shortly after talking to Dr. Levin about her work, I met with Dr. Daniel Lidar in the Chemistry department who was working on quantum computing. I had done some “research” as an undergrad on quantum computing, and the newness of quantum theory really appealed to me. Astrophysics is grand and beautiful and there was so much new data coming in, but many of the great theory problems seemed so large and so well gone over that I was sucked away from astrophysics. I am still jealous of the astrophysicist when they get to contemplate the entire frickin universe. Whereas I get to contemplate things I shall never really see. Well both are pretty cool.
“How the Universe Got It’s Spots” is an interesting little book. It is written as a series of letters to the author’s mother and explains all sorts of science, from topology, to black holes, to quantum theory. I’ve become, over the years, a hell of picky person when it comes to popular science books. I will admit that there were a few times when I had to close my brain during “Spots”, but most of these have to do with describing quantum theory, and happily it wasn’t the uncertainty principle which got mangled. And I’m just too stubborn to listen to what anyone else has to say about quantum theory. So me saying there were only a few rough spots in “Spots” is like saying that it’s really really well done.
Interestingly, the book takes a very personal view of the science discussed in the book. Not personal like most popular science articles where the author descripes his or her story and relationship to all these bigwigs in the grand quest we call science, but personal instead in detailing the authors emotional relationship to her work (and in some broader context, her relationship to the world around her as well.) In this way it reminds me a bit of Good Benito by Alan Lightman. Those astrophysicists really how to hit a guys emotion nerves. Here is a nice passage from “Spots” describing mathematicians and their penchant for being insane:
When I tell the stories of their suicide and mental illness, people always wonder if their fragility came from the nature of the knowledge-the knowledge of nature. I think rather that they went mad from rejection. Their mathematical obsessions were all-encompassing and yet ethereal. They needed their colleagues beyond needing their approval. To be spurned by their peers meant death of their ideas. They needed to encrypt the meaning in others’ thoughts and be assured their ideas would be perpetuated.
Another reason that I’m hard on popular science books has to do with the amount of learned. Growing up, the best popular science books all had one common trait. You would be reading the book and thinking about the topic and you would think, “well, it seems to me that what they’ve talked about here implies X.” And then a few pages latter you would read that indeed scientists discovered that such and such does imply X! Great popular science to me has a lot to do with great foreshadowing. The problem I have now is that I know most of the story. I’ve caught up to modern times. So the foreshadowing doesn’t work for me.
On the other hand, popular science articles do have a very interesting effect when I read them today. They remind me of the big picture, and often they let my mind wander. While I was reading “Spots,” for instance, the following occurred to me. One of the reasons we love relativity, both special and general is that it arises from such simple postulates into a beautiful and complex theory. One sometimes hears that this is missing in quantum theory: where do all these postulates about Hilbert space and Born’s rule and such come from? Are there some nice basic posulates from which we can reason, much like Einstein did for special relativity, as to why quantum theory should be the way it is? But while I was reading “Spots” it occurred to me that may this was an illusion. Suppose that instead of discovering special and general relativity before quantum theory (O.K. there is some overlap, but the truely disturbing parts of quantum theory emerged after both relativity theories.) If you are a quantum person living in a quantum world, does all this talk about mirrors and clocks seems rather troubling. Mirrors are big classical thingees. What do quantum mirrors look like, and is it natural to talk the thought experiments that Einstein used? But in a larger sense, I also began to wonder if the principles of relativity are really so natural. Are they natural to someone who experiences the amplitudes of quantum theory in their everyday experience? Why is it that we spend time trying to think about how quantum theory might emerge (this is, after all, what interpretations are really after, isn’t it?), but don’t spend time thinking about a deeper theory from which, say, special relativity might emerge. This, I guess is one reason I’m interested in loop quantum gravity: there, one of the challenges is to really see how our four dimensional world emerges from the, for a better word for it, quantum foam. So why does special relativity look the way it does, quantum boy? And it’s silly questions like these which keep me reading popular science, and will continue to keep me reading popular science, long after I’ve grown accustomed to the history.
Some Spiffy Physics Dudes
Howard Barnum passes along this link to a home video of the 5th Solvay conference held in 1927. It was at this conference that Heisenberg and Born delivered a paper in which they said
We regard quantum mechanics as a complete theory for which the fundamental physical and mathematical hypotheses are no longer susceptible of modification.
17 of the 29 participants in this Solvay conference were current or future Nobel prize winners.
The home video gives evidence that physicists have alway been jovial joking hams for the camera.
I Want! I Want!
Wired has an article about smart interactive whiteboards. Being a theorist, whiteboards and a pen and pad of paper are two of my most useful tools. I really don’t know if one of these whiteboards would really help me, but still: they look pretty spiffy! Now if only I had a few grand stashed away
The Rest of the Story
Rumors (Uncertain Principles and Luboš Motl’s reference frame) are that the Eovtos experiment here at the University of Washington may have observed a deviation from Newton’s laws at small lengths (less than one hundred microns.) Of course this would be huge news, and their desire to take it slow is certainly understandable and, I might add, is good science.
I remember driving down the road one day and I heard the radio man Paul Harvey report that a group of physicists had discovered room temperature superconductors. I recall that I got so excited that I actually started crying. Such a discovery would presumably change the world! Alas, it turned out to not be true. Either Paul Harvey had made it up or the group’s announcement was not correct. And now you know, “the rest of the story.”
A Physicist Does Math
I always like to show the following to those who have just learned quantum theory. The commutation relation between poisition and momentum is [tex]$[x,p]=i hbar$[/tex] or [tex]$xp-px=i hbar$[/tex]. Now act on an eigenstate of the [tex]$x$[/tex] operator [tex]$|x_0rangle$[/tex] and you get [tex]$(xp-px)|x_0rangle=xp|x_0rangle- p x_0 |x_0rangle$[/tex]. Take the inner product of this state with the ket [tex]$langle x_0|$[/tex]: [tex]$langle x_0 | (xp|x_0rangle- p x_0 |x_0rangle)= langle x_0| (x_0 p – x_0 p)|x_0rangle=0$[/tex]. But if we carry out the same procedure on the right hand side of the commutation relation we get [tex]$langle x_0| i hbar |x_0rangle=ihbar$[/tex], which, last time I checked, was not zero. Snicker. It’s so mean to give this to those who’ve just learned quantum theory, but shucks, it’s also pretty fun to watch them squirm and figure out what went wrong.