Today is Friday, and I have no mood to work. As you might expected, from the morning, I have produced no new code in my symbolic algebra system, which is boring as hell to program. So, I chose to slack off by reading cryptography instead. My supervisor is out of town so I think it's okay. (err...)

Since the beginning of summer, I have been reading various MIT lecture notes. The most relevant to my work is the ones for Madhu Sudan's class "Algebra and Computation," which is in my opinion a very great class. I also reviewed cryptography, a course I took about a year ago and almost forgot all of its content. I got the lecture notes from Anna Lysyanskaya's version taught in Fall 2001.

Today I read from Lecture 7 to Lecture 10. The first two is devoted to proving that semantic security is equivalent to GM-security. I kinda remember learning this, but didn't recall the definition of semantic security given in Lecture 7. Lecture 9 does not have much material in it besides some definitions of cryptographic building blocks, which will be repeated in subsequent lectures anyway. Lecture 10, I think, is the focus of today's reading. It concerns the Goldreich-Levin Theorem, which states that any one-way permutation has a hardcore bit. The lecture was scribed by Paisa Seeluansawat, aka พี่กื้อ, who is now probably an instructor at University of North Texas. I hate to say it, but I was quite confused by the note, so I went googling and found a wonderful exposition of the theorem by Mihir Bellare.

The Goldreich-Levin Theorem is one of the coolest theorems I have read in a while. (Well, compared to theorems in symbolic algebra books, which are so tedious to state and doesn't say even as much...) It guarantess that most cryptosystems will work if one-way function exists. At first, I thought that the proof would be more impressive as P' Kuea pointed out that you only need to "guess" the correct bits, which is exactly the part that made me confused. However, in Bellare's article, he just tries every possible bits. Nevertheless, the technique used in the proof is new to me: it demonstrates a way to generate an exponential number of pairwisely independent random variables.

Hmm... what should I do tomorrow? It is too late to book a hotel in Nikko or a mountain hut on Fuji-san. So I think I'm stuck in Kanagawa-Tokyo area for this weekend. There's an anime-related event at Tokyo Big Site this Sunday. However, I think it's very specific and so not really worth going. FMA the Movie hits the cinema tomorrow, but I don't feel like going there to fight the crowd either. Doushiyoukana...