Summer School on Tools :: Mykonos, Greece :: 28.5 – 1.6.

Slightly redacted announcement for the 2012 Summer School on Tools below.

Following the success of the ECRYPT Workshop on Tools for Cryptanalysis 2010,the ECRYPT II Symmetric Techniques Virtual Lab (SymLab) is pleased to announce the 2012 Summer School on Tools. Covering selected topics in both symmetric and asymmetric cryptography, this summer school will provide a thorough overview of some of the most important cryptographic tools that emerged in recent years. While the summer school is aimed primarily at postgraduate students, attendance is open to all. Continue reading “Summer School on Tools :: Mykonos, Greece :: 28.5 – 1.6.”

Sage/FLINT Days aka Sage Days 35

I am writing this while waiting for my taxi to leave Sage Days 35. Although, I didn’t get much actual coding done, it was great fun and very useful. I met a lot of old friend, new faces and managed to put faces to e-mail addresses.

In terms of coding projects, first, I tried to speed up linear algebra mod p where p is a 32 or 64 bit prime. But it turns out that any trick I could think of could not improve on Frederik’s code. So that didn’t lead anywhere but I allowed me to read some code of FLINT2 (very readable) and admire how carefully it is written.

My other two projects both involved evaluate–pointwise-multiply–interpolate algorithms for fast matrix-matrix products over finite extension fields or for matrices with polynomial coefficients (over prime fields).  After my talk on M4RI(E) David Harvey worked out how to improve multiplication over \mathbb{F}_{2^6} from 17 multiplications over \mathbb{F}_2 to 15, which then lead to a general approach for \mathbb{F}_{2^m} with composite m. Much of it remains to be implemented (efficiently), but the \mathbb{F}_{2^6} example indeed shows a 10% speed-up as expected. The code is not clean yet, uses way too much memory and doesn’t deal with the more advanced finite field stuff appropriately. It should end up in M4RIE eventually though.

I also contributed a bit to #12177 which is about a “prime slice” implementation of matrices over \mathbb{F}_{p^k}. The idea is essentially to represent  these matrices as polynomials with matrix coefficients and to use fast polynomial multiplication algorithms for these polynomials. It turns out, this works very well even for small finite fields. Burcin Eröcal did all the coding, I only helped with some discussions. We need to polish the code a lot to be usable, so if you like matrices over \mathbb{F}_{p^k} head over to #12177 and help out.

Slides: Introduction to Algebraic Techniques in Block Cipher Cryptanalysis

This morning I delivered my talk titled “Algebraic Techniques in Cryptanlysis (of block ciphers with a bias towards Gröbner bases)” at the ECrypt PhD Summerschool here in Albena, Bulgaria. I covered:

  1. Why bother
  2. Setting up equation systems
  3. Solving (GBs, SAT solvers, MIP, Cube Testers)
  4. “Advanced” Techniques

Well, here are the slides, which perhaps spend too much time explaining F4.

PS: This is as good as any opportunity to point to the paper “Algebraic Techniques in Differential Cryptanalysis Revisited” by Meiqin Wang, Yue Sun, Nicky Mouha and Bart Preneel accepted at ACISP 2011. I don’t agree with every statement in the paper – which revisits techniques Carlos and I proposed in 2009 – but our FSE 2009 paper does deserve a good whipping, i.e., we were way too optimistic about our attack.

Stats Porn

I just scanned the website of Lars Knudsen (who is visiting Royal Holloway right now) and came across this gem.

Year Crypto Eurocrypt Asiacrypt FSE PKC CHES TCC
2009 213 39 0.18 148 33 0.22 300 ?? ?.?? 76 24 0.31 112 28 0.25 109 33 0.30
2008 184 32 0.17 163 31 0.19 196 33 0.17 72 30 0.42 71 21 0.30 107 27 0.25 81 33 0.41
2007 186 33 0.18 173 33 0.19 223 33 0.15 104 28 0.27 118 29 0.25 99 31 0.31 118 31 0.26

The triples in the table indicate for the particular conference, the number of submissions, the number of accepted papers (or papers printed in the proceedings) and the ratio between the two first numbers. Bold face numbers are the record high number of submissions, The original table goes back further. Also, http://www.iacr.org/cryptodb/ has more stats about crypto publications.