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

Loading...

En provenance du cours de Université du Maryland, College Park

Cryptography

415 notes

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

À partir de la leçon

Week 7

Digital Signatures

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

Maryland Cybersecurity Center

[MUSIC]

Well this brings us to the end of the course.

I really hope you enjoyed the course, as much as I enjoyed teaching it, and

as much as I enjoyed interacting with, many of you on the discussion boards.

In fact, I hope you enjoyed the course so

much, that you're motivated to learn more, about the field of cryptography.

And what I wanted to just briefly talk about here is, where to go next?

What more is there to learn, and where can you turn to learn more about it?

So, first of all,

I want to point out that, even though I emphasize proof-able security.

Back when we talked about the principles of modern cryptography.

And even though we did see examples of proofs, and

I did talk about formal theorem statements expressing what kind of security we could

prove, I really didn't give very many proofs in the second half of the course.

And the reason simply is that the proofs become, a bit more difficult.

They become more time consuming.

They require a bit more background.

And also it's a little bit difficult to present them, on a PowerPoint slide and

I much prefer doing them on a,

on a whiteboard and being more active and interactive.

But if you're interested in the field,

it's really important to understand, how these proofs of security work.

And understand how to evaluate them, as well.

One thing in particular that I gave very short script to in this course,

is the random oracle model.

Even though I did mention a handful of times, this assumption of treating

a cryptographic hash function as if it's a random function.

I didn't go into any detail about it, and

we didn't really see any proof, based on that assumption.

This is a technique that's become more and

more widely used, in the analysis of cryptographic schemes today.

And if you're interested in the field, again,

it is important to go and see some examples of these proofs and

really understand what it is the random-oracle model entails.

As well as what it's limitations are.

Another topic that we really didn't have time to cover in this course was

design principals.

For modern stream ciphers, block ciphers, and hash functions.

We defined what a stream cipher is.

A stream cipher is supposed to act as a pseudo random generator.

We defined, what a block cipher should be.

A block cipher is supposed to be behave like a random function.

We talked about the notion of collision resistant hash functions.

I gave examples by name, of modern day cryptographic primitive,

that are assumed to realize these different functionalities.

But, we didn't go into any detail at all,

about how these modern day primitives are actually constructed.

And that's another very important area to learn about,

a very interesting one as well.

To really understand and get a sense,

of how these things can be constructed in practice and why we have any

belief that these things really do achieve the properties that we claim they do.

Another very interesting topic, is to look at developing cryptographic primitives and

cryptographic schemes.

Based on minimal assumptions.

So, in our discussion of for example private key encryption,

we took as our basic building block, pseudo random functions i.e block ciphers.

And we showed how to construct encryption schemes satisfying strong definitions of

security, based on any broad cipher.

The previous bullet talks about how block ciphers are actually

constructed and practiced.

But the practical constructions we have, are ultimately heuristic,

in the sense that we can't really prove anything about them.

The best we can do, is to analyze them.

And use the fact that there has not been any successful attack on them after

years of analysis, to therefore give us the belief, that they are indeed secure.

But, what's very interesting is that you can actually take a more

foundational approach and start with a very, very weak assumption,

namely the assumption that what's called one way functions exist.

A one way function, is roughly speaking, a function that is easy to compute, but hard

invert, such that i.e that it's difficult to compute the inverse, of that function.

That's a very basic, minimal assumption, but it turns out that that

assumption suffices, for constructing all of private key cryptography.

That is, you can build block ciphers, based on the assumption that one way

functions exist and then, as we've seen in this course, you can build, private key

encryption and message authentication codes, based on block ciphers.

I specifically did not cover this topic,

because it's really only a theoretical interest.

It doesn't have any practical significance today.

But for those of you with a more mathematical orientation or

a more theoretical orientation, I would advise you to

look into this topic because it really contains some very interesting results.

We also did not talk very much, about modern day algorithms for factoring and

computing discrete logarithms.

We introduced the problems.

We said that they're considered to be hard.

Namely, that there's no polynomial time algorithm, for

solving these problems, but that doesn't mean that the best algorithms we have for

solving them, are the trivial, brute force, exponential time ones.

And in fact it's very important to understand,

what the best algorithms are for factoring and computing discrete logarithms,

when determining the key length, of public key schemes.

For those of you who again are more mathematically oriented,

there's also a lot of very interesting mathematics, and

group theory, involved in designing and analyzing these algorithms.

Finally, we only gave very relatively little attention to public key

encryption and signature schemes.

And there's much more to learn about in that area as well.

I'm very happy to announce, that the second edition of my textbook,

Introduction to MODERN CRYPTOGRAPHY, was published and actually this happened,

I wasn't sure exactly when this was going to happen.

It happened sometime after I began recording week one but

before I'm ending the course now.

And so all of these topics,

all the topics listed on this slide are in fact covered in that book, and

I think it's a great place to turn to next if you're interested in learning more,

about cryptography beyond what we had time for in this course.

Now beyond that, you can start looking at more advanced material.

And here you begin getting into the current Cryptographic research and or

things that you might learn if you go to graduate school, to study Cryptography.

I'll just mention these very briefly.

In this course, we've talked primarily about a two party setting, where we have

say a sender and receiver communicating in the presence of an attacker.

Who's trying to eavesdrop or otherwise interfere with their communication.

But cryptography can also study the setting, where you

have a network of many parties all interacting and running some protocol and

where it's not even clear, which parties trust other parties.

Or which parties can be trusted or which might be compromised.

And this leads to a general area of the cryptographic design of protocols for

various tasks, with security even in the face of compromise of

some number of the participants in the protocol.

I mentioned in the last slide, design principles for

stream ciphers, block ciphers, and hash functions.

But of course, the counterpart to that is modern-day cryptanalysis, of

the constructions stream ciphers and block ciphers and hash functions that we have.

This is again a very active area of research today.

And one where you can really get very deep,

deeply involved in that as you try to understand these practical constructions.

There's also a lot of interesting work surrounding.

Number-theoretic algorithms.

And here I'm talking about things beyond necessarily algorithms for factoring and

computing discrete logarithms.

But algorithms for other aspects as relevant to cryptography as well.

Another very interesting area, of modern day cryptographic research,

is the investigation of what is sometimes called post-quantum cryptography.

So in this class, when it came to public key cryptography,

we looked exclusively at systems that were based on, really only two assumptions.

The assumption that factoring was hard and the assumption that

computing discrete logarithms in certain classes of groups, was also hard.

It turns out, that if quantum computers are ever built.

Both of these problems could then be solved in polynomial time on

a quantum computer.

And so for that reason, people who are thinking ten, 20,

30 years ahead are already worried about, what will replace modern day

public key cryptosystems, in case a quantum computer is ever built.

And so people are investigating various other assumptions.

On which to base public key cryptography.

And there's much, much more beyond that.

And what I would encourage you to do if you're really interested,

is to take a look at the web page for

the International Association for Cryptologic Research, IACR.org.

And take a look at both their flag ship conferences, Crypto, Eurocrypt,

and Asiacrypt.

Held annually, as well as the journal,

journal of cryptology that they are in charge of publishing.

And there you can get a sense of what kind of problems,

researchers in cryptography are working on nowadays and

see what interests you and develop your tastes that way.

With that, I only have left to wish you luck on the final exam.

And to encourage you to check out the capstone course as part of

the cyber security specialization being offered by the University of Maryland.

Again, I really do hope you've enjoyed the class, and

I look forward to meeting some of you in the future.

Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.