This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

Loading...

From the course by University of Maryland, College Park

Cryptography

324 ratings

University of Maryland, College Park

324 ratings

Course 3 of 5 in the Specialization Cybersecurity

This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

From the lesson

Week 1

Introduction to Classical Cryptography

- Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center

Maryland Cybersecurity Center

[SOUND] In the last lecture we began talking about the possibility of proofs of security and the need for formal definitions of security. In this lecture I just want to discuss these issues in a more general content. As two of the three core principles of modern cryptography.

As we have pointed out before, historically speaking, cryptography was really an art. Schemes like the shift cipher and visionaire cipher were developed and analysed in a relatively ad hoc and heuristic manner.

While there was some guiding principles in place, there was no agreement on when or if any particular scheme could be classified as secure.

In the late 1970s and early 1980s and continuing today, cryptography began to develop into much more of a science.

And I think you can isolate three fundamental principles of modern cryptography that have really helped move the field forward.

The three core principles that distinguish modern cryptography from classical cryptography are definitions, assumptions, and proofs of security.

Definitions as, as we've discussed briefly already provide a precise mathematical model in which to analyze schemes, as well as a formal definition of what security means.

Proofs, which we've also discussed before, give us confidence in the security of particular schemes and more importantly, allow us to move away from the design-break-patch cycle that was used historically.

That is, rather than propose a scheme and wait for someone to come along and break it, we can instead hope to propose a scheme along with a proof of security that ensures that no one can break it.

I'll discuss these more in a few slides, but just be aware that they won't really come into play for another few lectures.

Let's try to understand the importance of these principles in a little more detail. I've already said this in the last lecture, but I really want to emphasize this point. Definitions are crucial for building secure schemes.

Put simply, if you don't understand what it is you're trying to achieve then how can you possibly know when you've achieved it?

This is true in cryptography, as well as in computer security more broadly. [SOUND] Definitions are important for other reasons as well. Very often, going through the exercise of writing down a formal or even a semi-formal definition forces a designer to think about what they really want. Both what's essential to the problem at hand and often just as important, what's irrelevant.

And very often coming up with a reasonable definition is not just a trivial exercise, but one that reveals subtleties of the problem that may not have been immediately obvious.

Having a definition in place that some scheme is supposed to satisfy allows others to analyze the scheme with respect to that definition.

Also, as we'll see in this class, there can be multiple meaningful definitions of security that all coexist.

Having such definitions allows for a meaningful comparison of schemes. For example, you can say that one scheme is more efficient than another scheme, but satisfies a weaker definition of security.

In applications where the weaker definition is sufficient, you can then use the more efficient alternative.

More generally, having a clear definition of what security of a particular scheme satisfies. Means that others can use that scheme, as a component of some larger system they're building, and understand precisely, what security guarantees that scheme will provide.

We now come to the issue of assumptions. We haven't talked about assumptions yet, and as I said we won't need them for a few more lectures, so this discussion may make more sense then.

But in the meanwhile, believe me when I say that, with very few exceptions, non trivial cryptography currently requires some sort of computational assumptions or assumptions about the impossibility of solving certain problems efficiently.

For those of you familiar with these concepts, I'll just mention that one such assumption is that p is not equal to np. Something that's widely believed but which we don't know currently how to prove.

And by the way if you are not familiar with P and NP, then don't worry since this is the only time in, in this class when we'll encounter them.

One core principle of modern cryptography is that any assumptions used to prove security of a scheme should be made explicit.

It also allows, again, for meaningful comparison between schemes based on different assumptions. For example, you might have two schemes, one that's more efficient, but is based on a stronger, or a less well-understood assumption. And a second that is less efficient but that relies on a weaker or more widely believed assumption.

Relying on clearly stated assumptions is also important in case weaknesses are found in those assumptions. Again this will make more sense later on in the course. But for now imagine we have a system whose security is based on the assumed hardness of some mathematical problem.

If some efficient algorithm for that problem is found later on, we need to know whether the existence of that algorithm is enough to invalidate our assumption.

This is something we can only really determine if we formally state our assumption about the hardness of the problem in the first place.

Moreover, say the algorithm does violate our assumption for that specific problem. We might then be able to identify a different problem believed to satisfy the same assumption.

In that case, we can swap out the old problem and swap in the new problem and know that security now rests on the hardness of this new problem.

Finally it almost goes without saying, that we need precise assumptions if we're going to hope to write down rigorous proofs of security. And this brings us to the last core principle which may be the most important. This principle states that any new cryptographic construction should ideally be proven secure with respect to some specific definition. And based on some particular set of clearly stated assumptions. I've already motivated the importance of proofs earlier in this lecture and the previous one. So I won't harp on the issue any further. Except to say that although proofs are important in other areas of computer science as well, they're especially important in cryptography. Where there's a malicious attacker specifically trying to break your scheme, and whose actions you can't predict in advance.

Now I don't want to leave you with the wrong impression that cryptography is only a dry science, and that all the art and mystery are gone. That's not the case. For one thing, even within the paradigm of formal definitions and rigorous proofs. There's lots of room for creativity in coming up with novel definitions for new applications, designing new schemes and coming up with proof of security.

Beyond this, work on validating the underline assumptions, or in designing new primitives conjectory to satisfy those assumptions. It's still largely an art and remains an active area of research.

The field of modern cryptography has also received some criticism recently for over-emphasizing the security guarantees that proofs provide. So I want to be clear here that while proofs do give an ironclad guarantee of security, this guarantee is always relative to some particular definition. Instead of assumptions.

The first possibility is that the definition of security, with respect to which the proof was given, was not the right definition. In that it did not fully correspond to the real world setting in which the scheme was deployed.

The second possibility is that the assumption with respect to which the proof was given turns out to be invalid.

Thinking as an attacker and trying to poke holes in a definition, or invalidate an assumption, is actually another good example of the art of cryptography.

It's sort of interesting to know that proofs of security can sometimes lead to attacks by making explicit to an attacker exactly what definition the scheme guarantees and so conversely what it does not guarantee. And what assumptions needs to be violated in order to violate security of the scheme.

Nevertheless I want to emphasize that none of what I have just said should be taken to indicate that definitions and proofs are not important.

Definitions for example are very important and they can be used to allow both designers and users of cryptography to make sure that the real world environment. In which some scheme will be deployed matches the definition in place. And if this is not the case then the scheme shouldn't be used in the first place and a different scheme satisfying a more appropriate definition should be used instead.

Similarly, what I said a moment ago should not be taken to minimize the importance of proofs of security.

It’s true that provably secure schemes can be broken in the real world, but not if care is taken to make sure that the definition being used is appropriate and that well understood assumptions are used.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.