Estonian Winter School in Computer Science

Our traditional school will be during the first week of March again. It traditionally covers cryptography and programming languages (don’t ask me), plus a few other topics. Previously we have had such luminaries like Moni Naor, Moti Yung and Phil Rogaway from cryptography, Johan Hastad from complexity theory and Matiyasevich and Chatin from pure math.

This time the school has two younger but already very well known cryptographers, Jens Groth and Aggelos Kiayias. Jens will talk about pairing-based non-interactive zero-knowledge proofs (in my opinion, he and his coauthors caused a little revolution there a few years ago), and Aggelos will talk about cryptographic methods for digital content distribution (he’s a new book upcoming on this topic just a bit after the winter school). Other presenters include say Alan Mycroft from Cambridge.

The school is week-long, in an old manor among the forests, and yes, we usually have snow there. Please see the linked homepage of the school and please refer it to your familiar (non)graduate students! We usually have quite strong students, including a very strong bunch coming from neighbourly St Petersburg.

Postdocs positions in Estonia

We have money for several postdoc positions in Estonia. The salaries are competitive to those in continental Western Europe, while living costs are much lower. Our group consists of around 5-7 young (30–42) cryptographers (myself, Peeter Laud, Ahto Buldas, Sven Laur and others) with publications in all important conferences.

See here for further details.

Can we have a conference on UC, please?

While I am against the abundance of cryptographic conferences, I think that we still miss one conference, let’s call it a Sympiosum on Universal Composability (SUC). Who of us has not seen submissions (and accepted papers) on UC-security, that use the smallest font and margins possible, manage to still go over the alloted space, and in addition mention that both details of the security definitions and the security proofs (!) are omitted due to the lack of space.

A SUC CFP should include a nice 15-35 page introduction that would explain what exactly is UC, give notation and definitions. It should also provide the descriptions of most fundamental functionalities in the UC model (say commitments, encryption, signature schemes, etc). This introduction should be then printed as the introductory part of the SUC proceedings. All submitted (and later accepted papers) would be free of the burden of redefining the UC-security, introducing notation, and common functionalities. Instead, they could just focus on the new stuff. Obviously, the reviewers of SUC should also first familiarize themselves with the introduction.

In addition, reviewers of other conferences could breath much more easily since they would not have to review papers on UC-security anymore.

Cryptographic background makes you rich

I just bought myself Mathematicians: An Outer View of the Inner World, a wonderful hardcover book that contains pictures and autobiographies of many prominent contemporary mathematicians. At least one of them (Avi Wigderson) doesn’t need any introduction in cryptographic community. At least one more (Joan S. Birman) has done some work in cryptography. There are many other famous names, but they haven’t done any public work on our field.

Reading their autobios however is interesting. For example, the first bio I accidentally started to read is by one James Harris Simons (“differential geometry”). And then I found the next part (which is by the way not mentioned in Wikipedia): “I went on to Princeton and worked as a code-cracker at the time of the Vietnam war. I worked for the Institute for Defense Analysis. It was National Security Agency work and highly classified.” Then he continued to work on pure mathematics, and finally, moved into investment business. And became rich. Simons is the CEO of what is now one of the world’s most successful hedge funds.

I found the next quote to be quite intriguing: “Interestingly, the work I did as a code-cracker during the Vietnam War turned out to be extremely useful. As a code-cracker, you see a lot of data from your adversary. You get ideas. You test them. Most of them are wrong. If you’re lucky, you get a few hits and you begin to see. It’s similar with predicting financial data: you have an idea that when one thing happens, you might expect to see a certain pattern. You can test it out. Maybe you’re right. Maybe you’re wrong.”

Somehow the connection between code-cracking and predicting financial markets has been around in the popular culture for quite a while (“The Pi”, The Cryptographer – though not exactly, and probably some others), but this is the first time I’ve seen somebody really announcing that he’s become (that) rich because of his cryptographic background.

So – we have now one more reason to tell people why it’s good to be a cryptographer.

Another question: how much is known about the Vietnam war-era ciphers? I guess they didn’t use Enigmas anymore. Or Navajo windspeakers.

(NB: this is the only autobio I’ve read yet.)

Gordon Brown reads this blog…

Apparently. Recall that just a week ago I had a posting about the petition that asked an apology for Alan Turing? Now Gordon Brown actually issued a statement that ends with “So on behalf of the British government, and all those who live freely thanks to Alan’s work I am very proud to say: we’re sorry, you deserved so much better. Gordon Brown”. More seriously, it is worth to read this paragraph of his statement:

But even more than that, Alan deserves recognition for his contribution to humankind. For those of us born after 1945, into a Europe which is united, democratic and at peace, it is hard to imagine that our continent was once the theatre of mankind’s darkest hour. It is difficult to believe that in living memory, people could become so consumed by hate – by anti-Semitism, by homophobia, by xenophobia and other murderous prejudices – that the gas chambers and crematoria became a piece of the European landscape as surely as the galleries and universities and concert halls which had marked out the European civilisation for hundreds of years. It is thanks to men and women who were totally committed to fighting fascism, people like Alan Turing, that the horrors of the Holocaust and of total war are part of Europe’s history and not Europe’s present.

How to factor 15 by using quantum machinery

It has been over the news lately: namely, that the first “quantum chip” has been built that implements Shor’s factoring algorithm. Now, when you look at the abstract of the original paper then they have used it to factor 15. I am not sure if factoring 15 (on a quantum computer) was an open problem anymore – it surely was ten years ago.

Obviously, you can just use answers.com to get the same answer. Interestingly enough, answers.com gave a wrong answer for 18 just a few days ago, but after I pointed it out in Facebook, somebody has gone over those pages.

Schneier acknowledges in his blog that his “Applied Cryptography” is crap

Here. He also says his new book is upcoming which will be much better. He’s also inviting you to let him know if you know anything about the cult of Schneier.

Petition Seeks Apology for Alan Turing

Alan Turing was one of the greatest (if not the greatest) early computer scientists, who first defined the notion of a universal computer (“Turing machine”). He was also a leading codebreaker at the Bletchey park, whose work was instrumental (obviously, he also had ingenious colleagues) in breaking German ciphers — which has been said to be accelerate the end result of WW2 by a few years. However, he was also a gay, which was seen as a disease at this time. After receiving estrogen injections for a while, he committed suicide at the age of 41. (Another conspiracy theory was that he knew too much.)

Now there is an online petition that seeks apology for Turing. Finally. Unfortunately, you have to be a British citizen or at least resident to sign the petition, but still. Show your support.

Interestingly enough, the google search ‘online petition turing’ turns up almost 2 million pages.

Asiacrypt 2009 Accepted Papers

The list is here. I found quite a few intriguing titles for myself. Even more than in Crypto, to be honest. On the other hand, it would be nice to see abstracts, too.

I am NOT at Crypto 2009

Almost everybody seems to attend Crypto 2009. Not me – though I miss the Cactus Cooler and chicken in chocolate. And of course, the fabulous dormitory. And the cheerleaders – if they haven’t graduated, yet.

I hope Jon Katz will blog about Crypto extensively. I was reading the abstracts of accepted papers (which are fortunately online) and saw many interesting papers. Some are interesting because the result sounds good. Some are interesting because I am interested in the area. However, it is difficult to judge before actually reading the paper. Jon???

Also, the rump session is later today, broadcasted live, though I doubt I will be awake at that moment.

Deterministic way of finding primes

Terence Tao, Tim Gowers and others have a wonderful new polymath project that aims at efficient finding of large primes. The best known deterministic algorithm to find a -bit prime at this moment takes time and is based on the result that every interval contains at least one prime. Assuming Riemann hypothesis, one can deterministically find a -bit prime in time . Since the problem seems to be difficult, they also consider a number of relaxations, like allowing a unit-cost factoring oracle, or ask how to find just two large squarefree numbers and .

Now, what is a polymath project? The idea is to use the joint energy of millions of bored people, who’d otherwise just sit on Facebook, to actually do something useful. Somebody poses an interesting question and then everybody is free to take a stab on it. Hopefully, those millions of people can finally jointly solve the problem.

The current discussion thread for this project is here. Michael Nielsen has a wiki page that summarizes the known results and current ideas. Finally, Terry Tao has a number of posts about this project on his blog too.

From familiar people, I’ve spotted Avi Wigderson on those pages. I’ve also commented, though only anonymously, since I am just an egg.

My Review Sucks

For those who do not know it yet, there exists a little nice website http://myreviewsucks.com/ where you can anonymously post all those sucking reviews you’ve ever gotten, to at least bite back somewhat. If you participated in Eurocrypt, then you probably saw a rump session talk by Aggelos about it. However, the site has not been used much yet unfortunately.

My own two “favorite” reviews from past: First, by a reviewer saying that our result is not interesting since we improve the best known result only by a constant factor (well, the constant happened to be 2^15), and second, by some reviewer saying that the CPIR protocol I proposed (with log^2 communication) was not interesting since we already had protocols with polylogarithmic communication. The reviewer went forward to say that we can always define a new security parameter k’ as a polynomial of k, and thus log^2 vs log^anything is a nonissue. In general I also tend to be amused by a review that says that my work is a combination of known techniques. I thought that was what was called research.

Finally, I really like yet another opinion piece by Doron Zeilberger, where he says that due to the stupid reviews he’s not going to publish anymore papers in peer-reviewed journals. Lucky guy, he’s both famous and tenured. I also like one of the reviews he has gotten: “I think the results are new and the general plan is straightforward. It won’t get the Fields medal but I don’t think that’s our criteria. I do recommend it’s acceptance.”

On the other news, Jon Katz doesn’t like FOCS and Asiacrypt.

PS Finally, as you might have noticed I started to actively blog again. I used to do it a few years ago, but then most of my posts were personal. I’ll try to make this blog purely work-related.

In UK, two convicted for refusal to decrypt data

The UK has a bizarre law that gives the authorities the right to ask for keys used to encrypt and decrypt the data. In the case of disobedience, one may be sentenced to prison for up to two years (in usual case) or up to five years (in a case that involves national security). According to a recent news, two men were convicted for five years for refusing to provide authorities with their encryption keys. More precisely, of the 15 individuals served, 11 did not comply with the notices. Of the 11, seven were charged and two convicted.

This law is not even wrong for so many reasons, starting from basic human rights, and ending with it being a technical and legal absurdity. I’d just like to point out two factors why this law is absurd. First, how can you prove that one has known they keys, or has not forgotten them, or the post-it note where they keys were was not burned by a third person? This really baffles me. Second, without actually knowing the key, it is impossible to assume that the encrypted material has anything to do with the case, and thus as far as I see it, one should have convincing evidence to imprison even without getting the key at all. This however would make this concrete law superfluous.

This reminds me the next strip from XKCD:

On the other hand, may be there is something that “crypto nerds” can do here, and I’d actually like to propose a research question. Namely, we could try to devise a cryptosystem which has many possible indistinguishable decryption keys. If you have you have a copy of the ciphertext, the plaintext, and the corresponding decryption key, then you can easily generate a new decryption key that corresponds to any possible plaintext. The authority should not be able to (a) distinguish between different decryption keys, and (b) to have a reasonable advantage to even guess what is the number of the active keys.

On the other hand, then you could get beaten up for just using such a cryptosystem.

Stable Crypto Conference Marriages

In my previous post, I argued that there are too many cryptographic conferences. One of the accompanying well-known problems is that if your paper (say) gets rejected from Eurocrypt, then you either have to wait (and risk again) 3 months for Crypto, or you can go for a slightly weaker conference. However, most of those “slightly weaker” conferences (TCC, FSE, PKC, FC, and the next year even CT-RSA) are organized a few months before the Eurocrypt. This means actually that you need to wait for another (say) nine months. Call it the Spring Bundle.

Another well-known bundle is in December, with Asiacrypt organized inbetween 6+ smaller conferences (CANS, ITICS, ICICS, ICISC, Indocrypt, Inscrypt, and may be some more imatinatively named conferences). The good thing about this Winter Bundle is that you can submit papers, rejected in Asiacrypt, directly to ICICS/ICISC/Indocrypt/Inscrypt. The bad thing here is that those conferences are not slightly but much weaker than Asiacrypt.

I have had for quite some time an idea that the conferences belonging to one bundle should have a joint PC, and joint reviewing process, such that the best papers would be accepted to the top conference in this bundle (respectively Eurocrypt and Asiacrypt), while other papers would be somehow distributed among the weaker conferences. (Taking into account that the papers would also be in scope: e.g., block cipher papers not going to TCC.) However, I have never been sure how to distribute papers among the smaller conferences, since at least the 6 Decembery small conferences are all weak, some more than others.

I think Doron Zeilberger has a quite neat idea, albeit in the context of mathematical journals. To translate it to our language, let the authors choose, when submitting a paper, an ordered list of preferred conferences. The conference PCs will agree on either total rejection of the paper, or the ordered suitability list of the paper to different conferences. After that, they just run a stable marriage algorithm on pairs (papers, conferences). If you get a paper matched to conference X, you can’t complain since you still thought X to be ok (and your more favorite conferences rejected you). Analogously, the conference PCs can’t complain: if they don’t like a paper at all (or it’s not in scope), they can refuse to be matched with it.

This would take care of several possible conflicts. May be you as an author cannot travel to (say) TCC at this time – then you omit TCC from your list. If you think FC and CT-RSA are too weak for you and you want to gamble, you can only put Eurocrypt and the suitable IACR workshop in your list. If you are a real gambler, you’ll only consider Eurocrypt.

Obviously, if the authors are not happy with their allocation, they can withdraw their paper, but this happens even now sometimes. Moreover, if you knew you wouldn’t like conference X, so why to list it?

Anyhow. Such a system would increase publishing rate quite a bit. However, I still think it necessary to increase the number of accepted papers in top conferences, since just both bundles are too big.

There’s another point in Doron’s opinion piece: that there shouldn’t be any journals at all, everybody should just publish in arxiv, and let the readers be the referees (e.g., just count the impact, the number of citations). Although I strongly agree in the case of journals, I am not sure if this were implementable in our conference system, where getting there (going to the conference and meeting with the people) is also fun. Still, I think counting the impact (citations) is a much more relevant way of deciding researcher’s impact than counting his or her tier 1 conference papers. (See my previous post for more.)

For another take of this issue, see also the PhD Comics. Doron’s earlier opinion piece was even better.

EDIT: Two more comments. First, in the current system your paper might be the best of the rejected papers (you don’t know it). You will then submit it to say ICICS. Assume ICICS does not have any competent reviewers in this subarea, the paper will get rejected, which may be especially depressing. With this kind of joint reviewing you may get rid of this problem, too.

Second, such a joint system will increase the average quality of the top conferences, too, even if the number of accepted papers was increased. Risk-averse authors (or authors, whose paper has already been rejected from the last big conference) might want to decrease the risk by submitting the paper to a smaller conference. However, may be it would have been accepted to the top conference this time, too – nobody knows? With the joint system, Eurocrypt could get the bestest papers of this spring (assuming that the authors prefer Eurocrypt to say FSE or TCC, of course). This would considerably decrease the gamble element: either risk a lot by submitting to a top conference (where the paper may be rejected), or submit to a non-top conference (which may accept it, but then it doesn’t look so good on CV, or which may reject it because of the lack of good reviewers).

Time for Crypto to Grow Up

This time in Fortnow’s blog – a long discussion about whether one should reform/abolish conferences as the primary publication venue in computer science. 40+ comments at this moment

His entry and comments are mostly concerned about the situation in complexity theory/TCS. I think one ought to ask the same question about crypto, especially since our field has an over abundance of conferences. The problem is also that the top conferences (Eurocrypt, Crypto,  may be Asiacrypt) only accept 30-34 papers yearly, while the number of quality papers is much larger. Moreover, the last 10 or so papers accepted are always somewhat random. Now, when your paper is still good but gets rejected, you have to wait 3 more months for the next top conference, and then 3 more.

On the other hand, you have 20 small conferences, that are almost all equally bad. (Not FSE, TCC, PKC, CT-RSA, FC, CHES, but the rest of them.) Most of them get a tiny share of good papers, since some top researchers do not want to wait for 3 months,  or just want to travel. Or for some other not-science-related reason. In general, if you are an established researcher, it does not pay off to sit in the conference room at those conferences since you do not learn anything new so you just do some sight seeing. (If you are lucky, somebody whom you know might also participate!) And being on a PC of such conferences is usually just a pain.

I think there is some room for reform, thus. My own recommendation would be to increase the number of papers, accepted to all IACR conferences and workshops by 50%. (As said, the last 10 are always random* – and the first 10 non-accepted papers are sometimes better.) This would increase the rate crypto results get published quite a lot. This would also mean that less top papers would get accepted to third tier conferences, which would also be good – hopefully the number of third tier conferences would decrease.

Moreover, to compare it with the past, Eurocrypt 1990 got 85 submissions and accepted 42 papers. Eurocrypt 2004 got 206 submissions and accepted 36 papers. With Crypto, corresponding numbers are 43 (of 93) and 33 (211). Thus, while the number of submissions has increased 2.5 times, the number of accepted papers has actually decreased(!). In addition, in 1990 the number of active research groups in cryptography was may be 10 times less than now. This means, that the competition for Crypto/Eurocrypt papers has increased dramatically.

* I’ve actually done some statistics. I might have a separate post on that, but of Crypto 1998 papers, around 10 have been cited less than 30 times. While the top paper, by Cramer and Shoup has been cited 600+ times. Other conferences followed a similar pattern, though not always the top paper has that many citations. OTOH, there are many papers in third tier conferences that have more citations than the mean Crypto/Eurocrypt paper of the same year.