On Post-Modern Cryptography

an essay by Oded Goldreich

This essay relates to a recent article of Koblitz & Menezes (Cryptology ePrint Report 2004/152) that ``criticizes several typical `provable security' results'' and argues that the ``theorem-proof paradigm of theoretical mathematics is often of limited relevance'' to cryptography. Although it should be obvious that these claims are utterly wrong, we undertake articulating this triviality. In particular, we point out some of the fundamental philosophical flaws that underly the said article and some of its misconceptions regarding theoretical research in Cryptography in the last quarter of a century.

See material avialable on-line.

Executive Summary (or some highlights)

What is really the issue? Koblitz and Menezes object to the rigorous analysis methodology of cryptography (which evolves around clear definitions and rigorous inference rules). The issue at hand is the choice of adequate methodology for cryptographic research, and our opinion is that cryptographic research must be committed to scientific methodology of rigorous analysis. In general, we believe that rigorous analysis is, by far, the best way to study reality. Moreover, in the case of cryptography, this general principle is more important than in any other discipline.

The foregoing assertion is based on the realization that cryptography is focused on adversarial behavior; that is, the protection against adversarial behavior is the discipline's founding question. Needless to say, adversarial behavior is very different from normal behavior. Furthermore, it is almost always the case that the (adversarial) behavior that harms a system is of a type that the system's designer did not expect. In contrast, most disciplines are concerned with normal behavior, or with deviations from the norm that one has already observed or can envision. Our point is that, while a rigorous analysis is of great value for questions regarding normal behavior, it is indispensable for questions regarding abnormal and unexpected behavior.

On theory vs practice. The general principle that governs the application of theoretical research to practice is that (scientific) research informs (technological) practice. This does not mean that practice reduces to a straightforward implementation of theoretical results. On the contrary, the application of theoretical results in practice requires a deep (but not necessarily detailed) understanding of theory as well as the exercising of judgment (which in turn is based on the principles that underly the theory).

In particular, in our opinion, the principles that underly the theory of cryptography are the focus on clear definitions of security and the application of rigorous inferences regarding security. Thus, we believe that practice should be based on three ingredients: (1) using clear definitions of the one's goals, (2) using clear definitions of one's assumptions, and (3) providing a rigorous justification of the claim that if the stated assumptions hold then the designed system meets the stated goals.

On assumptions. A frequently asked question says that since we are using assumptions anyhow, why don't we just assume that the designed system meets the postulated specifications. Our answer is that not all assumptions are equal. Specifically, we distinguish assumptions by their clarity and simplicity, and argue that the validity of clear and simpler assumptions is easier to evaluate. Thus, it is of great value to reduce complex assumptions (which on the face of it may even be self-contradictory) to simpler assumptions, and likewise reduce new assumptions to old assumptions that are widely believed.

On mistakes. Unfortunately, mistakes occur also in scientific disciplines, but they are far more frequent outside the domain of science. The occurrence of mistakes does not invalidate the scientific methodology but rather increases the importance of being committed to it; that is, the fact that a rigorous analysis may be flawed does not mean that one should abandon rigorous analysis but rather that one should apply it even more carefully.

Material available on-line

Back to Oded's page of essays and opinions or to Oded's homepage.