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.
Cryptography quite a history which dates back as far as when man first to make marks to represent aspects of their lives and as technologies (albeit as primitive as they may seem in comparison to the technologies of today) forged ahead and we developed the written word, cryptology could be as simple as just writing down a message. This may sound over simplified but remember that reading and writing were skills that were taught to the minority.
So initially, cryptology was just about writing a message and passing it on to someone. But as education became available to more people that meant that any written message could be read by anyone who had the skill to decipher the squiggles. But not every message needs to be read by anyone other than the designated recipient. Remember also that even back when we lived in caves, the pictures/messages on the walls were not necessarily meant for everyone as different groups had different enemies.
When you take into consideration social history, as soon as people started to form tribes there was a need for secrecy concerning land, food sources and general politics. As civilisations progressed the use of cryptography became more devious. Egyptians already had hieroglyphs, they simply made subtle changes to the characters and only people who knew the code were able to read the ‘true’ message. The Greeks also became really innovative about ‘codes’, one of the most popular ways to send a coded message was to wrap a tape around a stick, the message would be written on the stick. In order to understand the message when it was delivered to you, you needed to have a sick of the same diameter as the original stick otherwise you could not read the message.
But there is never a greater need for cryptology than during periods of conflict. Over history the secret codes have become more complex and some could be considered to be unbreakable. In Britain during the Second World War there was a group of code breakers based at Bletchley, whose sole role was to break codes used by the enemy. Over time these codes have become more and more complex. Given time and perseverance. Most codes can be broken do many agencies change the codes they use on a regular basis, and for some this could be daily.
One of the most innovative and unbroken ‘codes’ used during the Second World War was used by the Navajo’s who based a code on their native language, in today’s world, the more hi-tech option is for the use of public and private keys that support a form of asymmetric encryption.