Special Interest Group on CRAP

Neal Koblitz recently wrote an article in the Notices of the American Mathematical Sociey titled The Uneasy Relationship Between Mathematics and Cryptography. This article is actually the third by Koblitz, following two previous articles with Alfred Menezes:

1. Another Look at “Provable Security”
2. Another Look at “Provable Security”, II

There’s something weird about the division in these communities, because it appears to be the mathematicians rather than the computer scientists who are concerned about the mismatch between reality and models of security. I have personally found the work on security in the theoretical computer science community to be both interesting and compelling, but I am often dismayed by the tendency to exaggerate its importance for practical systems.

In particular the terminology of “probably secure” is both misleading and coercive. [see note below] Such cleverly chosen phrases sound appealing at first, but they invite improper conclusions and sound grander than they are. The problem is that it sounds like security is being proved, which may lead non-theoreticians to conclude that they can put more faith in practical systems based on the theoretical protocols than they should. The real nature of “provably secure” systems is that they prove asymptotic reductions between idealized but largely impractical models of cryptographic systems and computational problems that we hypothesize to be difficult. In reality we have almost no evidence for supposing that any computational problems being hard other than our own ignorance or relgious conviction. Even if we could prove that P!=NP, an asymptotic statement of complexity would require considerable work in order to make any inference for practical systems.

A more appropriate term than “provably secure” would be “hypothetically secure” or “theoretically secure”. The term “hypothetically secure” would more accurately reflect the fact that it is only secure if an unproved hypothesis is true (and then only asymptotically or for some unpspecified parameters against a hypothetical adversary). The term “theoretically secure” would emphasize that the term “secure” can only be interpreted in a theoretical model, and it is both dangerous (and often impractical) to make any inference from the theoretical statement of security to any practical statement of security. The concept of “proof” is one that exists only within theoretical models, and we should be cautious about exaggerating the inferences that can be made from theoretical models. Theoretical models are useful, and practioners can wisely make inferences from the theoretical results, but these inferences are something that takes place in the real world, not within a theoretical model.

The articles by Koblitz and Menezes have inspired responses from several members of the complexity community. Recently two have appeared by Jonathan Katz and Michael Mitzenmacher. I also call attention to the response by Oded Goldreich and his most recent response to the Koblitz article. I was pleased to see that Oded voiced a very similar point of view to mine regarding the terminology “provably secure”. The field would be better off if this terminology was stricken from the vocabulary.

I found the first article by Koblitz and Menezes to be quite compelling and interesting, but the followon article was less interesting and the most recent discussion by Koblitz and Goldreich seems to reflect an escalating resentment between groups who have different points of view. I think we would all be wise to return to the pursuit of knowledge and forego the personal attacks.

There are multiple forces that have contributed to the breakdown of respect between groups. Part of the problem is the exaggerated language that pervades the field, and part of the reason is the mismatch in culture between computer science and mathematics. Mathematicians have always regarded conference publications as little more than ephemeral conversation rather than archival publication, whereas computer scientists regard conference proceedings as their primary means of publishing. The influence of money on the field is also a problem, both for the potential of people to make vast sums on commercial products, and the need to compete for meager resources for fundamental research.

Much of science is incremental and sometimes tedious. The need of scientists to continue to publish at regular intervals in order to show progress results in a lot of uninteresting publications. Like most people, I recognized very early that the concept of zero knowledge was fundamental to the understanding of cryptography. Unfortunately, this basic idea was carried to a number of extremes, increasingly straining my patience by the study of minor nuances on the basic concept. After a few years the connection to cryptography was completely lost, but people continued to mumble things containing the term “zero knowledge” while claiming to do cryptography. At some point I remember being on a program committee in which half of the papers contained the acronym ZKIP, but I coined the term ZCIP to describe their contribution to cryptography. ZCIP = Zero Content Indistinguishable Papers.

Unfortunately I think the discourse regarding the role of complexity in cryptography has degenerated to a point where it may take some time to recover. I’m am as guilty as anyone else in this with my quip about ZCIP, but I was motivated by what I saw as exaggeration of importance. The contributions to our understanding that have resulted from the complexity-theoretic point of view are unquestioned. At the same time, we should be careful to understand and respect the relationship between the pursuit of basic science and the development of practical and useful information security systems. Practitioners of both activities need to step back and gain some appreciation for people who are on the other side of this divide.

Update: An an anonymous writer has pointed out that this was a peculiar typo. I meant to type “provable” but instead it came out as “probable”. It goes to show you that the choice of language used to describe a concept is important.