Study Group: On the Impossibility of Tight Cryptographic Reductions

Today I kicked off the study groups for 2016/17. I spoke about On the Impossibility of Tight Cryptographic Reductions, from this year's Eurocrypt. Keen readers of the blog might recall that this paper is a particular favourite of mine.

Since I've wrote about it before, I won't go into much detail about the paper. Instead I'll say why I (still) like it, and a bit about how it's shaped my own work this year.

So, why choose this paper again? First and foremost, it's just really good. It's well written and the result - that certain reductions are necessarily lossy - has big implications for the way we do things in provable security. There is an increasing drive for theoreticians to produce work that has a meaningful impact on the real world. Choosing security parameters is an important part of that picture, but this paper shows that the traditional tools of provable security can sometimes be inadequate in this regard - especially in a setting like the internet, with billions of users of cryptography.

Is it that our methods need changing? Or should practitioners ignore the theory and 'go with their gut' when choosing parameters? Do we need to actively avoid using those crytographic primitives for whom reductions are always lossy,  like rerandomisable signatures and encryption schemes where each public key has a unique secret key? These are profound questions for the community.

Another reason I chose to talk about this paper is that it's nicely self-contained. This is not an incremental result about something obscure. Almost everyone here at Bristol has encountered reductions, and after recalling the standard EUF-CMA definition for signatures it was easy to build up to the main theorem of the paper (or at least the particular case of signatures in the main theorem). If any new PhD students are looking for some theory to get their teeth into, this paper would be a great starting point.

Finally, I cheated a bit by giving my presentation about a paper that I've become very familiar with in the last few months, as I'm trying to extend it. At the moment, the result only applies to certain public-key primitives; I'd like to say something about multi-key to single-key reductions for symmetric encryption (which is of particular relevance to my PhD project, on Key Management APIs). I hope to have more to say on this in the not-too-distant future.