Is Cryptographic Theory Practically Relevant? (Day 1)

Yesterday the workshop wondering about the practical relevance of cryptographic theory started at the reknowned Newton Institute in Cambridge. There was a staggering number of participants including people from both industry and from academia, covering a vast range of cryptographic theory and practice.

The workshop started with Serge Vaudenay's talk ominously titled "Privacy in Deniable Anonymous Concurrent Authentication with Setup is Impossible: Do we Care?". His choice of title had already received some critical comments in the comments section of Jon Katz's blog, so I was looking forward what the title referred to. Before Serge came to the main topic so to speak, he discussed another issue that fits very well with the Dagstuhl seminar from two weeks ago.

Last Eurocrypt he and his coauthors looked at statistical attacks on RC4.There they estimated certain complexities using assumptions about certain variables being independently distributed in some way. Since then, they have tried to validate these assumptions in practice by running experiments. It turned out that the variables behaved quite differently then assumed and expected, so a different model (related to modelling tornados) was needed. Turning the workshop's theme on his head, Serge concluded that practice can be relevant for theory.

He continued to talk about deniability in certain protocols. His main point was that a notion like deniability is extremely brittle. It is known how to achieve deniable authentication in the standard model, but as soon as a random oracle is added into the mix, the deniability no longer holds. Similarly, once the right kind of trusted hardware token is available, deniability can no longer hold. The point is that these extra powers are more useful to the adversary than to the protocol designer and from the literature on for instance receipt-free elections they don't come as an entire surprise, but it is still somewhat strange to see in action.

Serge's talk contained a third part on achieving different kinds of privacy in authentication protocols relevant for RFID tags, where he adapted a security definitions to bypass impossibility notions and realign with practice. The combination of the three parts of his talk was a clear reminder of the limitations and potential dangers of conducting cryptographic theory in complete isolation from practice, as one might well end up with unrealistic models or assumptions. In other words, a great start to the workshop.