New BBC documentary focused on breaking of “Tunny”

October 31, 2011

BBC has published a new documentary “Code-Breakers: Bletchley Park’s Lost Heroes that focuses on how Tunny (or Lorenz, the cipher machine used by Nazi high command) was broken in Bletchley Park during the World War II, and concentrating on feats of William Tutte and Tommy Flowers. Highly recommended. If you are not living in the UK, there are other means to get access to the documentary.

Eurocrypt 2001 citations

May 5, 2011

Eurocrypt 2001 papers citation chart

Since (but not only) I am a general chair of Eurocrypt 2011 in Tallinn, I became somewhat curious about the past Eurocrypts. The chart above is what I found about the citation statistics of papers published in Eurocrypt 2001, that is, exactly 10 years ago. The citations are counted according to Google Scholar (and may obviously be somewhat incorrect). Moreover, I only counted citations for the top match (and not say for mistyped names, journal versions, etc).

The 9 papers that have received more than 100 citations are (unordered):

  • Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords
  • Priced Oblivious Transfer: How to Sell Digital Goods
  • Practical Threshold RSA Signatures without a Trusted Dealer
  • Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels
  • Evidence that XTR Is More Secure than Supersingular Elliptic Curve Cryptosystems
  • Multiparty Computation from Threshold Homomorphic Encryption
  • The Rectangle Attack – Rectangling the Serpent
  • An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation
  • Encryption Modes with Almost Free Message Integrity

Anyone can guess which paper is actually the most cited one — at least I was not able to do it before Googling the Scholar.

I think even more interesting is the tail of this chart, with 39, 38, 38, 37, 32, 26, 26, 20, 19, 17 and 13 citations.

I have obvious questions: is it normal that papers accepted in a top venue have less than 20 citations after 10 years? What about less than 50? Is getting citations (having impact) important at all during selection of the papers? I know that in the case of STOC and FOCS there is severe criticism that papers get accepted based on their technical difficulty, and not on their possible impact. (I fail at finding a good link right now, but see for example here or here.) Impact *is* shown by the number of citations, so do Crypto and Eurocrypt have a similar problem? As an example, the *least* cited paper (with 13 citations) is called “Efficient Amplification of the Security of Weak Pseudo-random Function Generators” – and it’s definitely a technically complex paper.

Also, it would be interesting to know the most cited rejected papers (even without concrete names).

So many questions. :-)


April 30, 2011

Not only has the new Canadian TV show “Endgame” an ex-world champion in chess as the main hero, in the newest episode 7 they also introduce a female cryptographer (“she’s a brilliant cryptologist for the world’s biggest firewall developer”) who does research on homomorphic encryption.

“Algebraic cryptosystems?” – “Yeah, lattice-based”

EDIT: going to add a few more funny quotes.

“Her master thesis at MIT was about the […] transposition cipher used by Spartan military. How cool is that?”

Paper-voted (and why I did so)

March 5, 2011

(This entry is written mostly for my non-cryptographer friends who wonder why I am always criticizing Estonian e-voting scheme, but it may also be interesting for cryptographers all around the globe. All opinions are my own.)

Many people probably already know that Estonia has had Internet voting since 2005. Over the years, the number of voters has increased. In the parliamentary elections this week, more than 10% of the whole population (which means even larger percentage of the population who can vote – and probably quite a large percentage of the people who actually go to vote) used Internet voting.

I paper voted.

Why? First of all, as a cryptographer, it is my job not to support insecure systems. Given the current situation in Estonia, paper-voting is the only thing that I can do, but I hope things will improve rapidly.

Here’s a short description of Estonian Internet voting protocol:

One vote attempt:
You as a voter either use an ActiveX control (or a downloadable application if you use a wrong browser/…) to log in to a secure webpage. To authenticate yourself you use an ID card (those have been obligatory in Estonia for quite a few years). After logging in, you use the GUI to select the candidate. After that, the voter computer encrypts your vote by using RSA and the key of a tallier. The result is also signed by using your private key (which is again stored in your ID card). Your computer now sends the signed & encrypted vote to the vote collector server.

You can always revote by using exactly the same procedure. The VCS only stores the latest vote by every voter. (This step was introduced to combat vote coercion/family voting — note that if everything else fails, you can go to the voting station and revoke your electronic vote by paper-voting.)

Vote counting:
After the election period ends, the VCS will take the latest encrypted votes of all voters and send them to the second server that is behind a firewall. The second server removes all the signatures. It then ‘burns’ all the unsigned encrypted votes to a CD. Now, a number of trusted people (including observers) take this CD and bring it to a separate room, which is well guarded. That room contains the third server, the tallier who is *not* connected to Internet at all. The CD is input to the tallier. The tallier reads all encrypted votes. Since it knows the decryption keys, it can decrypt all votes. After that it outputs the number of votes given for every candidate.

This whole process also contains a number of organizational steps (like transfer of the CD to the tallier, or general auditing), but cryptographically that’s it.

So what’s wrong with it? For a cryptographer it’s a rhetoric question but let me reiterate some points. Basically, an e-voting system can be attacked by attacking voter computers, Internet connection or voting servers. Signing/encryption mostly takes care of fraudulent Internet (they do not obviously protect you against DDOS attacks and the like).

Voter computers are an obvious problem: most of the people are computer illiterate, and are not able to check if their computers are not infected. Even if they have the newest antivirus (which we can’t be sure of), that antivirus itself might not be able to detect a piece of new malware that has been written specifically for *that* election and is unleashed just before it. (Note: in Estonia e-voting lasts for 3 days.) That malware could do a lot of damage, like hijack the connection between you and the ID card (basically letting the ID card to sign wrong votes), between the GUI and what actually happens inside the computer, etc. I would *not* be surprised if such a piece of software was written by a high-school kid.

Vote servers are another problem: they can attacked by a hostile (but yet invisible) takeover, or by an insider (software provider, hardware provider, they guy with a gun meant to protect the servers, cleaning lady…). To be completely certain nothing like that happens, one should use either 100% trusted providers etc, etc (which is somewhat unlikely if an interested foreign powers invests a few million euros to bribe everybody), or one should use cryptography. But first, why does it matter? Can’t we trust the election office? Rhetorically I could ask: do we trust politicians in general? Do we? Less rhetorically, there are so many potential threats here.

Given all this, when Internet voting process started in Norway, the government officials clearly stated they want strong cryptography, and probable security in general. In particular, they do not want to only avoid attacks. They want to be able to prove that no attacks happened. Moreover, they want to be able to prove that the e-voting system is so secure that no attacks are possible at all. (Or at least, the number of possible attacks is strongly limited.) If the e-voting system satisfies that property, they can in particular prove that they did *not* cheat. That means, at least some kittens in Norway will have a good night sleep. And people’s trust in the governance will increase.

We can imagine all kind of attacks (and motivations behind those attacks) against Internet voting. A party would like to gain a few more votes. A script kiddie is angry at a politician whose daughter doesn’t like him. A foreign power wants their favorite party to gain a few more votes. A foreign power attacks e-voting process just so that it will be clear that somebody attacked and thus the results can’t be trusted. Etc. Etc. Script kiddie might spend a few days to write a virus that works on user computers. A foreign power might spend $10M to develop Stuxnet+.

How can we protect Internet voting then? Fortunately, there *are* very well-known (at least in the cryptographic community) protocols for that. It is known how to get security in the case when a minority of voting servers is malicious. Under some conditions, it just suffices to have one uncorrupted voting server. Developing such protocols means that there is a need for additional computing power (and time, to implement the cryptographic protocols). Deploying such protocols is invisible to the voters.

Protecting against corrupted voter computers is more difficult. There are quite many ways to do it, but most of the ways requires the voters to perform some additional operations. As an example, Norway will use a scheme where every voter receives (by post) a codesheet that has the names of all candidates and corresponding check codes. (The codes are unique for every voter.) Voting proceeds as usual, by using computer and your favorite GUI, but afterwards you will receive by SMS a single code. The voter can now just verify if this is the same code that was written on the codesheet under his or her favorite candidate. If it is not, he can revote electronically (or go and paper-vote).

There are a number of good things about the Norwegian system. First of all, receiving the codesheet and checking your codes is not obligatory — you just have to do it when you are paranoid or just security-conscious (or just geeky). Thus, Internet voting still rules in the sense of convenience. On the other hand, interested voters can verify that their votes were counted for by following a relatively small number of steps.

Another thing that I like about the Norwegian solution is that by using their own words, the underlying math is simple enough to be understood by high school students — and they plan to start teaching the protocol at high schools. (See the slides here.) Which is nice, since cryptography is not everything — for complete trust there have to be enough people to understand the system. And it’s always nice to teach people new math. :-)

The Norwegian system is not ideal, but it can be improved upon. There are also many other, somewhat similar (or completely different) techniques to protect Internet voting schemes against corrupted user computers. Unfortunately, dwelling into them would take quite a lot of time and this margin here is too short.

Rebuttal system in conferences

February 19, 2010

David Eppstein has mostly good experiences with rebuttal experiment in SoCG (top conference in computational geometry). Briefly, after the initial review period, authors are given 1 week time to answer to reviewer’s questions. After that, in a few weeks, a final decision is made which papers are to be accepted.

I personally expect that if handled correctly, such rebuttals would help tremendously in the reviewing process. I’ve just too many times received reviews that could be rebutted with a single paragraph, and may be I’ve written some reviews like that myself. I am a strong supporter of rebuttals, and I hope they will be implemented in at least top conferences in cryptography too.

Estonian Winter School in Computer Science

December 1, 2009

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

October 19, 2009

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?

September 30, 2009

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

September 29, 2009

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…

September 11, 2009

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

September 5, 2009

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 to get the same answer. Interestingly enough, 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

September 4, 2009

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

September 2, 2009

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

August 19, 2009

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

August 18, 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.


Get every new post delivered to your Inbox.