Posted by: jonkatz | December 16, 2011

Is cryptographic theory practically relevant?

I’ve seen too many workshops/talks with this (or a similar) title, where it was clear that the answer (“yes, of course!”) was a foregone conclusion.

In that light, I was pleased to see from the list of speakers, titles, and (especially) abstracts that this upcoming workshop on the theme appears like it will take a more nuanced approach.

I wish I could go, actually, but the timing (right at the beginning of the semester) is terrible.



  1. I would really love to see Serge Vaudenay’s talk:
    Privacy in Deniable Anonymous Concurrent Authentication with Setup is Impossible: Do we Care?

  2. When I was working on Private Info Retrieval my wife told me

    A database is NOT an n-bit string.

    She has a point.

  3. Looking at the webpage of the the workshop, I am surprised at the goal of the workshop and the list of speakers.

    If the goal is really to understand what “theory of cryptography” brings to the table, this workshop is bound to do a terrible job since it does not have a good representation of theoretical cryptographers. It has some, but very few.

    I feel that the following is what would happen:

    1) The workshop is quite likely to conclude that they don’t really care as much about “current theoretical research,” — particularly the research of tcc-community.

    2) The theoretical cryptographers are quite like to conclude that the conclusions of this workshop are useless, since they did not have a good representation there.

    You can disagree with me. I don’t really care.

  4. I mean, there is not even a *single* person in the list of speakers who will claim that theoretical cryptography is his/her *primary* research interest, yet the first line in the description says:

    “The workshop aims to bring together researchers who work in theoretical aspects of cryptography…”

    Talk about a good start :))

  5. Why_even_try: Interesting point. But it really depends how you define “theoretical cryptography”. If it means “doing rigorous security proofs” (which I think is how the workshop organizers interpreted it), then a good percentage of the speakers do work on theory of cryptography.

  6. jonkatz:

    Just “doing rigorous security proofs” does not mean you are a theoretical cryptographer. This is quite a loose definition. Almost all research in theoretical cryptography has *some* practical motivation. It does not mean that theoretical cryptographers are actually practitioners.

    Doing reigorous security proofs is merely a good exercise to support your claims. Much like correctly calculating the running time of your algorithm.

    To clarify further:

    1) Studying the paradigms and design principals for blockciphers, trying to understand why one thing works and the other does not *is* in my opinion theoretical research.

    Of course I can list countless others like multi-party computation, but that would miss the point.

    2) Likewise, builiding a theory of encryption schemes, even if it comes practical real world motivations, such as deterministic encryption is also theoretical research.

    3) Coming up with a secure protocol for arbitrary real world tasks and then doing rigorous security proofs is not theoretical research. Here you are interested in an isolated task and there is no theory being built around it. You are merely using established tools to solve this isolated problem; doing security proofs is required of you in this case, since if you do not, then you are not even a *cryptographer*. There would be no difference between you and someone else who comes up with a random ad-hoc approach to put “encryption and signatures” together to solve the problem.

    Some examples of such isolated tasks are: constructing protocols for pay-tv, protecting keys on smart cards, key management, access control mechanisms, etc.

    These topics do not represent research in theoretical cryptography. These are topics where tools from cryptography can be applied to solve the problem successfully. They fall in the domain applied cryptography.

    Of course, as usual many topics are perhaps in the gray area where they can be called both. But often, theoretical and applied research can be separated.

    The goal of this workshop will be better descripbed as the following: “We wish to understand what are some modern world cryptography problems in the industry, and how provable security can help with them.”

    Indeed, it is a very good exercise, since it helps keep our field connected with the real world, and keep a decent portion of our field useful in practice. It is particularly relevant to you if your funding comes from industry projects. However it is not something that “bridges gap between theory and practice”.

    Finally, understand that theoretical cryptography is not superior to applied research topics. Nor do I feel that way — contrary what I sound like. Some people prefer to work on the former, some on the latter, and there are some who don’t necessarily make such a choice.

    What I do despise is the titles like this:

    “Privacy in Deniable Anonymous Concurrent Authentication with Setup is Impossible: Do we Care?”

    This is because such title represent some sort of a hatred towards a very small portion of theoretical problems, and hence bring a bad name to the entire theoretical cryptography community; in particular the tcc-community. If I really want to sit-down and start digging all the useless research that gets done in the so called “practice motivated cryptography”, I am certain to find a huge portion of papers that I would hate. But it is true in many research areas, not just theoretical crypto, or applied crypto.

  7. @Why_even_try:


    As one of the organizers of this workshop, I was pretty struck by the strength of your comments (one might describe them as vitriolic – perhaps they were not intended that way, but that’s how they came across to me). So I thought I ought to at least attempt a response.

    Knowing Serge as I do, and knowing what he’s been working on lately, I would think his title was meant to be light-hearted, and not expressive of hatred at all. In fact, I suspect it was intended to be self-deprecating. However, I must say that I am surprised that you found this title alone so despicable, and were able to read so much into it and what it might represent.

    I infer from your message that you are adopting a relatively narrow definition of what “theory” means in cryptography: perhaps loosely defined as “the kind of work that gets published at TCC”?

    That’s absolutely fine, and it’s quite understandable that you choose to define it in these terms. But it might also be helpful for you to be aware that not everyone does define the term so narrowly. Indeed, I believe that a key issue for our field (as a whole) is that some (though not all) people in industry/commerce regard pretty much everything we publish in the scientific literature as being “theory” – in other words, it all gets tarred with the same brush, and, in some quarters, is ALL regarded as being irrelevant to practice. Believe me that I’ve had this experience first hand.

    You might respond that this of absolutely no concern to you the work that you in particular do. That’s fine too! But some of us do see this as a problem for our field, and want to work towards building a better shared understanding of how theoretical cryptography – broadly scoped – can influence the real world, and vice-versa.

    But I’d like to go further and challenge the assumption that the workshop is not about theory – even with your narrow definition of that term. You give some examples of what you consider to be theory and what you consider to fall outside the scope of this term. In particular you write:

    “Likewise, builiding a theory of encryption schemes, even if it comes practical real world motivations, such as deterministic encryption is also theoretical research.”

    But this is exactly the kind of thing that falls within the scope of the workshop! For example, we will have talks that touch on extending the current theory of encryption schemes to encompass additional security properties such as length hiding, prevention of traffic analysis, resilience to randomness failures, and so on. We will also have participants who are experts on deterministic encryption, on fundamental aspects of randomness extraction, and on zero-knowledge proof systems. We will have speakers who have thought deeply for many years about randomness in cryptography.

    Now it’s true that many of the participants will draw upon real-world concerns when motivating the problems that they have chosen to talk about for this workshop. But the research they are doing falls squarely within your own definition of theory. I think it’s a particularly wonderful thing that these kinds of theoretical topics- using your definition – turn out to be so closely related to the real-world problems that practitioners are concerned about. One might even use the classic phrase “unreasonable effectiveness” in this regard.

    So I’d actually like to strongly encourage you to come along to the workshop. I think you’d find plenty of interesting theory talks being given – albeit with connections to the real world being explicitly highlighted and discussed. We still have a few places left for participants.

    But maybe you’d even like to give a talk? We could squeeze you in to the schedule. Perhaps you could expand on your chosen theme of defining theory? I truly believe that the more you do so, the more you’ll find you have plenty in common with the other participants.

    Feel free to drop me an e-mail if you are interested.


    Kenny Paterson

  8. Thanks, Kenny, for the comment.

    (PS: I found Serge’s title funny. For what it’s worth, I remember the same joke 10 years earlier, when people would complain about too many titles of the form “Concurrent, Non-Malleable XYZ”. And then of course there is the automated paper-title generator!)

  9. Dear Kenny,

    As a theoretical cryptographer (at least if we use the “not useful for practice” definition 🙂 ), I find the workshop’s program very interesting, and would have loved to attend it if my schedule would have permitted it. To me it seems clear that the aim of the workshop is not to denounce certain areas of research as “useless”, which would indeed be rather unproductive and uninteresting, but rather to strengthen ties between industry and researchers.

    Are you planning to videotape talks and/or put the slides online?

    –Boaz Barak

  10. Dear Boaz,

    A shame you can’t come.

    Yes, we’ll try to extract slides from all participants and get them online.



  11. @Kenny Paterson:

    Perhaps you failed to notice my mention of what the workshop is good for — understanding what problems are good from industry’s point of view. You also failed to mention that I see this as an excellent goal.

    Therefore, the workshop is good for developing a better understanding of what is more important in industry and how we should incorporate problems useful in practice in our research. The workshop, however, is not good for concluding the value of results like “Privacy in Deniable Anonymous Concurrent Authentication with Setup is Impossible.” It does not have the right people in it. Then why choose this forum to mock such research?

    And am I really reading too much into Serge’s title? Do you really think it was the best way he could have spent the time in his talk? How is the title self-depreciating when he does not work on such topics?

    Anyway, I do not even know why I am writing this. Especially after Kenny Paterson — who is primarily a theoretical cryptographer — has “rigourosly proven” that I have lost the argument by my *very* own definition of theoretical cryptography, and thereby losing it right there in my first comment. Alas.

    It is possible for me to defend my last comment by pretending that it’s main objective was to make the post “self-depreciating” and “humorous.” Rest assured, that is last of my intentions :).

  12. […] Katz recently blogged about an upcoming workshop: “Is Cryptographic Theory Practically […]

  13. […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s


%d bloggers like this: