This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.
Principles of Modern Cryptography
Loading...
Do curso por University of Maryland, College Park
Cryptography
424 ratings
Na lição
Week 1
Introduction to Classical Cryptography
Conheça os instrutores
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.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
