Crypto 2012, Day Four

Today was already the last day of Crypto'12. It was a thoroughly enjoyable conference, with plenty of interesting talks, but also socially. On the symmetric side of the cryptologic spectrum, I noticed that many of the accepted papers had previously been presented as work in progress at the Dagstuhl seminar. The result by Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir on Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems was no exception (full version available as IACR eprint 2012/217). At the time, Shamir had asked the participants not to broadcast the results (hence the obfuscated blog coverage at the time), but this time everything is public. The program committee had award this paper with the predicate ``Best''. As customary for the recipient of the Best Paper Award, the authors were granted additional speaking time, and likewise some extra attention to the wonderful talk by Itai Dinur seems in order.

It all begins with the simple and elementary observation that for a single blockcipher E with a k bit key operating on k bit blocks, full key recovery by exhaustive search takes 2^k time and virtually no memory. When the blockcipher is DES (the international standard for a long, long time) k=56 and exhaustive search is an issue. In order to increase resistance against this attack, a natural solution would be to repeat the blockcipher with two distinct keys, i.e. to compute E_L(E_K(X)). The resulting key (K,L) has length 2k so one might hope that the best generic attack would take time 2^2k. Alas, a meet-in-the-middle attack allows easy recovery much faster. First compute and store a table E_K(X) for all K and subsequently try all E^-1_L(Y) for all L in the hope of hitting a tabulated element (resulting in a complete candidate key, one expects to find around 2^k candidate keys this way). For this reason, double encryption is hardly ever seen, but instead one directly moves to triple encryption. The best known generic attack on triple encryption takes time 2^2k and memory 2^k. By these three examples, one might be tempted to conjecture that the time*memory complexity is lower bounded by the size of the keyspace. It turns out this conjecture is incorrect, as demonstrated by Dinur and his coauthors. Already for quadruple encryption, a better trade-off is possible by guessing the ``middle'' value (after double encryption). For a given input-output pair (X,Z) of quadruple encryption, and each guess Y, one can compute both a 2k bit key that connects X with Y and one that connects Y with Z using the standard meet-in-the-middle. Thus in time 2^2k and memory 2^k one finds 2^2k full 4k bit candidate keys (by trying more input-output pair a unique key can be retrieved). Note that the total time*memory complexity of this attack is only 2^^3k, constituting an improvement over prior art.

This improvement can also be used for any higher number of rounds, but every so often a further improvement can be made by splitting the problem conveniently into two parts. These splits are not always symmetric, and the magic sequence at which a further improvement takes place, turns out to be 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, ... (also known as A000124 and related to Floyd's triangle). So far, this is all beautiful theory, but their is a remarkle absence of multiple encryption beyond triple in the wild, limiting the impact of the attacks. Amazingly, many other problems can be rephrased into one that allows the techniques to be applied. Foremost is a knapsack problem, for which new attacks are developed that in many cases best existing ones by Becker, Coron, and Joux, and also by Howgrave-Graham and Joux (though the most promising attack to me still seems to be one by these earlier works).

There were of course more talks on Thursday, but I will skip straight to the very last session. The penultimate talk of the conference was on the homomorphic Evaluation of the AES Circuit. This is work by Gentry, Halevi, and Smart and the latter gave the talk in his inimitable style. At some point, he asked out loud Why AES? which prompted the answer Because it is out there, and we can in analogy of answering the question Why climb the Mountain to which the answer was simply Because it is out there. I will leave a technical exposition of the work to Nigel, but one of the interesting things to see is how low level implementation (think SIMD instructions) and high level ideas from fully homomorphic encryption (e.g. number theoretic noise-cancelling tricks) form a blend that should appeal to a very large part of the crypto community. My only criticism would be that the philosophy of mountain climbing is slightly more complicated, but it was a highly entertaining talk nonetheless. It prompted the session chair Daniele Micciancio to exclaim at the end You just experienced Nigel Smart.

Zvika Brakerski continued the FHE session with a talk on how to remove modulus switching and still get an efficient scheme. For the details I will have to refer to the paper, but I would like to take this spot to advertise the two tutorials that were mentioned at the end of the talk.

And that, dear cryptoblog readers, was the end of Crypto.