Essay:The Edifice of Cryptography
From CRYPTUTOR
The Edifice of Cryptography: An Artist's Impression
Manoj Prabhakaran
Modern cryptography systematically addresses several questions that all arise at once when one deals with information and security. The artist's impression we present is an attempt to bring out the various aspects of the field. Like all such perspectives, this by no means is the only way to comprehend the field; nevertheless, we hope such a perspective is useful in conveying the spirit of the field to students and non-specialists.
Contents |
The Edifice
We look up on the edifice of modern cryptography as built on top of two pillars. The first of these pillars is the various cryptographic tasks one conceives (like encryption, signatures, etc.). As soon as one tries to formalize these intuitive goals, one comes across the challenge of modeling the world we live in, and formally defining our goals within such a model. All this constitutes the first pillar.
The second pillar on which the field rests is of computational complexity. Computationally hard problems (with several other properties) are critical ingredients in building most cryptographic schemes. These ingredients are relatively simple and easy to formalize concepts compared to the security goals mentioned above.
Resting on these two pillars, and indeed bridging them in a technical sense, are the various implementations of cryptographic schemes. These schemes achieve (as can be verified using accompanying proofs) the security definitions provided the complexity primitives they use have the requisite hardness properties.
In the following we detail several aspects of these three components.
The First Pillar: Constructs, Models and Definitions
By cryptographic constructs we mean intuitive concepts like encryption, signature schemes or multi-party computation. These constructs are typically motivated by real-life applications. They can often be explained by giving an example scenario. There are also less intuitive (or more technical) constructs that arise as common tools in several cryptographic schemes. Constructs like pseudorandomness generator or zero-knowledge proofs are examples.
Once the constructs are conceived the game is on. We want to realize these ideas. Several obstacles become obvious as one considers candidate constructions. The popular (non-theoretical) approach has been to come up with constructions which address these challenges. At some level, this corresponds to coming up with a scheme so that several undesirable attacks or channels of information flow are ruled out. In contrast modern cryptography tries to come up with a scheme so that only specified channels of information flow are allowed. This is done by explicitly specifying these channels as part of the security definition, and later proving that a construction meets these definitions.
Security definitions are easiest to understand when they are simple, abstract and general. (Unfortunately these also tend to be the ones most difficult -- if not impossible -- to attain.) Simplicity and abstraction (a) make it easy to see whether the security guarantees are satisfactory, (b) robust to unanticipated threats, and (c) applicable to a wide range of scenarios and changing technologies. The definitions are specific to each construct (encryption, signature etc.). But often they fit into broad definitional paradigms or patterns, which makes it easier to interpret them.
An important component in formulating a definition is coming up with a mathematical model of the real world. This involves modeling such things as computers, communication channels, time and probability. Sometimes toy models are used to simplify detailed investigation of certain issues, but typically only models close to being realistic are relevant to practice. Typically the models do have several idealizations (e.g., computations which do not bugs, computational hardware which do not leak side-information, sources of perfect randomness, etc.) which are considered (not always reasonably) not to affect the conclusions. Alternately, the idealizations can be seen as demands on a real life system which need to be met, before the results from the theory can be employed.
The security guarantees are only as good as the model used. Yet, even when the model leaves out several details, we hope that the security guarantees translate to useful assurances in real life. There are several criticisms one could raise (and indeed are often raised) against the "standard models" used in cryptography. On the other hand, there are several possible justifications for even weaker "non-standard" models. The models and definitional frameworks used are continually evolving to address various considerations. This is a topic that merits a detailed discussion of its own (which we shall not attempt in this essay). The standard models tend to be the more pessimistic models developed in the field.
To sum up, this pillar gives a mathematical form to the intuitive notions of security. There are two leaps of faith that this pillar embodies: (a) the modeling attempts to capture the real world in a mathematical model (e.g. modeling computation, probability, time) and often also relies on simplifications or idealizations, and (b) the security guarantees in the mathematical model need to be interpreted as satisfactory in real life (e.g. is one in a billion probability of being defrauded OK? Is a computational complexity assumption valid?). However, avoiding the modeling and definitions because of these leaps of faith is comparable to say, avoiding computer simulations while building an aircraft. Indeed, one needs to constantly reexamine and improve the models and definitions, as is being done.
The Second Pillar: Complexity, the Source of Security
Various security constructions derive their security guarantees from the complexity of the components in them. There are two kinds of complexities at play: informational complexity and computational complexity.
Informational complexity just means entropy (unpredictability, or lack of information) that is introduced to a system to achieve security goals. More precisely, most of the security schemes use a source of random bits. For instance, various cryptographic keys are generated randomly, so that an outsider cannot guess the key, except with an extremely small probability. Such an informational complexity is inevitable for achieving most constructs.
The second kind of complexity, which is much more subtle and less understood, is computational complexity. The role of computational complexity is intuitive: often "breaking the security of a scheme" may be possible in principle, but computationally hard. Cryptography borrows the conventions of complexity theory (asymptotic treatment, polynomial time computation etc.) while talking about computational hardness. However, on several details the kind of computational hardness studied and used in cryptography is different from the kinds usually considered in complexity theory. For instance, while complexity theory mostly considers the complexity of succesfully solving all instances of a problem (worst-case hardness), cryptography is concerned about the complexity of breaking even a few instances of a cryptographic scheme.
Computationally hard problems required in cryptography would typically also need some easiness properties. (For instance, an encryption must be "hard to break" without a key, but easy to decrypt with an appropriate key.) Unfortunately, with our understanding of computational complexity today, we do not know how to ensure that a problem has such a combination of properties. Indeed, we do not know if any such problem exists. Proving the existence of such a problem will go well beyond resolving some of the most challenging open problems in computer science and mathematics (like proving P not equal to NP). As such, we resort to making assumptions about the complexities of various problems. Several problems drawn from various branches of mathematics (algebra, number theory etc.) serve as worthy victims for such assumptions. But in addition, we often abstract out commonly used combination of hardness and easiness features into so-called "general assumptions" (e.g., one-way functions, trapdoor permutations etc.).
The Bridge: Implementations and Proofs
Built on top of these two pillars are several useful implementations. The implementations come with proofs of security, so that we know that they indeed satisfy appropriate security definitions. The implementations and proofs reduce the complex security requirements of the cryptographic constructs to the simple complexity primitives. Relevance of the theory to practice depends on our ability to build this bridge.
There are several recurring trends in the various constructions and in the proofs of security. Proof techniques like "hybrid argument" and "black-box simulation" are good examples. Also, several "impossibility results" reside in this part of the edifice, showing that certain reductions are not possible at all. This informs us on our choice of definitions and our choice of complexity primitives.
