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

541 ratings

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.

What we haven't seen before are assumptions.

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.

In fact cryptography requires even stronger assumptions than this.

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.

Making assumptions explicit allows researchers to attempt to

validate these assumptions.

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.

And in particular, provably secure schemes can be broken in the real world.

When this happens, it happens for one of two reasons.

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.

In any case, a scheme with a proof guarantees something that’s well defined,

which is more that can be said, which is more than can be said for

schemes without any proof at all.

This wraps up our discussion of the three principles of modern cryptography.

Starting in the next lecture, we'll get to see these in action as we begin to

formalize exactly what we mean when we say that an encryption scheme is secure.

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