After the Monday and the Tuesday, the Dagstuhl seminar surprisingly continued on Wednesday, but for the sake of symmetry, I'll concentrate on what I considered the highlights of the last two days of the seminar (being the Thursday and the Friday) in the blog entry. My apologies to those who spoke but are not covered here.
Tetsu Iwata presented his recent attack on EAX-prime. Tetsu gave a wonderful talk and kindly excused himself for the simplicity of the attack. It is always instructive to see how a relatively small change (from EAX to EAX-prime) can cause such a huge difference (from provably secure to rather broken).
Orr Dunkelmann continued his Crypto'11 rump session, describing the effectiveness of Meet-in-the-middle attacks on IDEA. For the initial attack, already an improvement on prior art, all that seemed to matter was IDEA's key scheduling. Since in the first few rounds, the key can be split up in a part that is used only in the first round and another part that is used only later on, a meet-in-the-middle attack becomes possible. Orr and his coauthors then went further by combining this new idea with known techniques, such as the Biryukov-Demirci relation and splice-and-cut.
In the late afternoon session, Antoine Joux presented new results on bit splitting for knapsack and codes. The idea arises from his Eurocrypt'10 work with Howgrave-Graham on finding knapsack solutions by representing every solutions in many different ways and applying Wagner's generalized birthday algorithm to find one of the by now many solutions. Last year the method for knapsacks was improved and independently applied to the problem of decoding random linear codes. By combining these latter two ideas, a further improvement is possible, giving rise to the asymptotically fastest decoding algorithm to date.
Elena Andreeva gave two short talks welded together. The first part was an update on provable results of the remaining five SHA-3 candidates. The second part was more tentative, as she gave a new definition to measure the security of blockcipher security. The hope is that this definition will be useful to make more concrete what it means for a cipher to be secure against (or succumb to) a related-key or known-key attack. It was still very much work in progress, but I really liked the approach and it was obvious that I was not the only one!
The final talk on Thursday was given by Phil Rogaway. He presented a completely new approach to designing a blockcipher. Here a single round of the blockcipher defines a keyed involution with a particular structure. Due to this structure, Phil and his coauthors were able to prove how many rounds were sufficient to achieve provable security against IND-CCA type attacks. The work was information-theoretic in nature (so the round keys for the involutions were horrendously large), but one can argue that such a design still provides a heuristic once one makes the design more efficient (and giving the proof in a private random oracle model).
Thursday evening there were no talks, but apparently there was an opportunity to watch Enigma, the movie with Kate Winslet. I'd already seen it once, so instead I played some pool with the other attendees. It's always fun and while some were better than others, and the matches were all reasonably even. On my way to the wine, I also noticed Ewan Fleischmann was playing chess against Christian Forler. Ewan did fairly well while I was watching, but seemed to have screwed up a bit in between bottles.
The last day only had a morning program, before people would disband after lunch. John Steinberger presented a continuation of his talk of Monday, but in a relatively standalone fashion. John's ability to condense problems from probability theory to their core keeps amazing me.
All in all, I enjoyed the seminar a lot and after my first semester of teaching, it was good and inspiring to see the forefront of research again. So I'd like to take this opportunity to thank the organizers, Frederik Armknecht, Stefan Lucks, Bart Preneel, and Phil Rogaway, for the wonderful job they did, which included finding last-minute replacements for last-minute cancellations. Special thanks also to Kenny Paterson for travelling to Dagstuhl together! In about a week's time there will be the workshop on the practical relevance of cryptographic theory. Since a large part of our group will go there, expect regular updates on this blog!