I asked Jon to allow me to write a guest blog about an issue that I have been thinking a lot about lately. The question is whether there is a place for “algorithmic cryptography research” within the crypto community. Of course, I need to explain what I mean. Algorithmic research is all about finding increasingly more efficient solutions to problems. If the best algorithm known for a problem is n^5 and you find an algorithm that takes less time, then this is progress even if the solution takes n^4 and this is still quite expensive. Eventually, experience shows that this methodology yields solutions that are more and more efficient, until they are “optimal” or at least much better.
In crypto, things seem more complicated. It is relatively easy for me (and I guess for others) to judge a pure theory paper. I understand the contribution, whether it is conceptual or technical, and so on (of course, there are papers that are easier and harder to judge, but overall it’s not too problematic). However, it seems much more difficult to judge a paper that constructs a “more efficient protocol”. Once again, I don’t mean a protocol that is the first to achieve a constant number of rounds, because this is again a theoretical achievement. I mean a protocol that is more efficient in terms of round complexity, number of exponentiations, and so on than other previously-known protocols. Working in this area seems to be very dangerous. Sometimes such papers are very well received, and sometimes they are not. The question is what distinguishes the well-received and less well-received papers? Well, I have some ideas. First, a protocol with a clear asymptotic improvement often has a better chance. Second, introducing significantly new techniques seems to be almost crucial to getting such a paper accepted. The problem with judging new protocols in this way is twofold. First, there are some asymptotically efficient protocols out there that perform really badly on concrete parameters. Second, if I take a problem and come up with a more efficient solution than anything known (and of course provide a rigorous proof), then should I throw it out because the technique isn’t new?! I’ll even go as far as to venture that it’s better to have a less efficient protocol with new techniques than a more efficient protocol that uses old techniques in a better way. What about using the old techniques but coming up with a much better analysis that shows that a smaller security parameter can be used? All of these “achievements” are hard to judge, and generally hard to sell, unless we explicitly state that we want to have algorithmic cryptography.
In my opinion, if we don’t encourage algorithmic improvements (that don’t have radically new techniques, but are still often very hard to achieve), then we won’t ever reach the goal of having really efficient secure protocols. At the moment, I’m hesitant to work on such problems, because I’m not sure that I’ll have an audience. (I stress that it’s being in the middle that’s a problem. If I come up with a protocol that’s really efficient and can be used in practice, then I can sell it to the ACM CCS community. However, I also think crypto should be interested in it, and this is also really my community. Furthermore, it will take many years to get practical protocols and we need to respect small improvements in that direction, or we’ll never get there.)