This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.
Computational Secrecy
Loading...
From the course by University of Maryland, College Park
Cryptography
509 ratings
Explore Related Videos
At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you
From the lesson
Week 2
Computational Secrecy and Principles of Modern Cryptography
Meet the Instructors
Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center
Maryland Cybersecurity Center
We've been working with the notion of perfect secrecy, which requires that
an encryption scheme leak absolutely no information about the plaintext.
Even to eavesdroppers with unlimited computational power.
As we've seen in the last lecture,
the notion of perfect secrecy has some inherent drawbacks.
Which make perfectly secret encryption less used in practice than it
might otherwise be.
Furthermore, if you think about it a little bit,
the notion of perfect secrecy might seem unnecessarily strong.
In this lecture, we're going to look at a relaxation of perfect secrecy that I'll
argue still gives reasonable and useful security in practice.
The relaxation we're going to look at is called computational secrecy.
The intuitive idea is that it would be okay if we
had a scheme that leaked information.
With tiny probability to eavesdroppers with bounded computational resources.
That is, we're going to relax perfect secrecy in two different ways.
First of all, in contrast to perfect secrecy, which requires that
absolutely 0 information is ever leaked to an attacker,.
Here we're going to allow security to fail with some tiny probability.
You can think about this as leaking the entire plain text even to the attacker.
But only happening, but that only happening with very small probability.
Furthermore, we're going to relax the notion of perfect secrecy by
restricting our attention to efficient attackers.
And only being concerned with ensuring security against efficient attackers.
In contrast to perfect secrecy, we're not going to
be concerned about what attackers with unbounded computational resources can do.
So we have these two relaxations of allowing security to fail with
some tiny probability and restricting our attention to only efficient attackers.
And I want to explore both of these in a little bit more detail.
Say we have an encryption scheme.
Where security fails with some tiny probability.
Say 2 to the minus 60.
Should we be concerned about using such an encryption scheme?
Well in fact, if you do the calculation you'll find that
with probability greater than 2 to the minus 60.
The sender and receiver are using that encryption scheme will both be
struck by lightning some time over the course of the next year.
The take away from this is that if you're concerned about probabilities of
events that occur with this probability of 2 to the minus 60.
Then you have bigger problems to worry about than failure of
the encryption scheme.
Another way to look at it is that if you have an event which occurs with
probability 2 to the minus 60 in each second.
Then that event is expected to occur only once every 100 billion years.
So again, if you imagine that you have an encryption scheme that some
parties are using to encrypt one message a second.
And the and each time the encryption scheme is applied,
it leaks information to an attacker with probability 2 to the minus 60.
Then you expect that that scheme will leak information to an attacker,
only once in 100 billion years.
And again, if you're concerned about events that occur only once every 100
billion years,.
Then I would argue that you have bigger problems to worry about.
What about the restriction to looking only at bounded,
at attackers with bounded computational resources?
Well, to get a sense of the kind of attackers we're going to consider,
let's look at an attacker who performs a brute force search over the key space.
That is trying each key in the key space one by one,
decrypting some observed cyber text with each possible key.
And let's make the assumption that the attacker can test one key
per clock cycle of the underlying processor.
This is actually an overly optimistic assumption, but we'll make it for
simplicity in our calculations.
If we have such an attacker running this attack on a typical desktop computer.
Then that attacker can search through about 2 to the 57 keys per year.
That's the number of clock cycles in a typical desktop computer if
the computer is running over the course of a year.
So this would mean that the attacker is taking their computer.
Doing this brute-force key search,
testing one key per clock cycle and using that computer for nothing else.
If the attacker, instead,
uses a supercomputer, they could test about 2 to the 80 keys per year.
If that attacker was running an exhaustive search on
a supercomputer since the time of the Big Bang.
They could test about 2 to 112 keys in total.
So, restricting our retention to attackers who can
try at most 2 to 112 keys is a very reasonable assumption.
We don't need to worry about attackers who can task 2 to 256 keys.
Simply because there's no way that such an attacker can possibly exist in
our physical universe.
Just by way of comparison I wanted to let you know that in
modern encryption schemes.
The key space is at least 2 to the 128 keys or more.
So this means that if you had an attacker running on
a super computer since the time of the Big Bang.
And doing nothing else except trying to find the key that you're using in
such an encryption scheme.
They still would not have been able to do an exhaustive search over
the entire key space.
That seems like a pretty good security assurance to me.
To relax the definition of perfect secrecy, we're actually going to
start with a definition of security called perfect indistinguishability.
Let's fix an encryption scheme defined by three algorithms Gen, Enc, and
Dec, as usual.
And we'll refer to that encryption scheme by pi.
Informally the notion of
perfect indistinguishability guarantees the following.
Let's assume we have some two messages m0 and m1.
And we choose one of those messages at random, and
encrypt it using a uniform key to give us some ciphertext c.
We give that ciphertext c to an attacker.
And that attacker then tries to determine from that ciphertext which of
the two messages, m0 or m1, was the one that was actually encrypted.
We'll say that the scheme pi is secure.
In the sense of perfect indistinguishability.
If no adversary A can correctly guess whether of m0 or
m1 one was encrypted with probability any better than one-half.
More formally, let's let pi be an encryption scheme as before, and
let A be an attacker, i.e, an eavesdropper.
We're going to define a randomized experiment that we'll call PrivK for
private key and that depends on both A and pi.
It's an experiment that depends on some encryption scheme pi that we fix and
some attacker A that we've also fixed.
The experiment proceeds as follows.
First, A gets to output any two messages m0 and
m1 in the message space of its choice.
Then we generate a key using the key generation algorithm of
the encryption scheme.
We choose a uniform bit B that's going to act as a selector bit selecting one of
the two messages m0 or m1.
And the, we encrypt the message m sub b using the key k that we just generated.
This gives us a ciphertext c.
The ciphertext c here is going to be called a challenge ciphertext.
We give the ciphertext to a.
And A then outputs a bit, b prime, which is meant to
represent its guess as to which of the two messages was encrypted.
We'll say that A succeeds in a given run of the experiment.
If its guess, b prime,
is equal to the value b corresponding to the message that was actually encrypted.
And we'll define the experiment to evaluate to 1 or to output 1 if and
only if A succeeds.
Notice that it's easy for any attacker A to succeed with probability one-half.
If an attacker outputs a random guess for its bit b prime,
it will be correct with probability exactly half.
In fact, no matter what the attacker does if, if,
it would be correct with probability one-half.
It's easy to see that it's possible for
an attacker to succeed with probability one-half.
All the attacker has to do is to output a random guess b prime and
it will then succeed with probability exactly half.
Well say if the encryption scheme pi is perfectly indistinguishable.
If for all attackers A it holds that attacker succeeds with
probability exactly half.
That is to say there's no possible attacker a that can do
any better than one-half.
We claim that pi is perfectly indistinguishable if and
only if it's perfectly secret.
This means that perfect indistinguishability is just an alternate
way of defining perfect secrecy.
The claim is not very difficult to prove, but it's a bit technical and
messy and so I'm not going to prove it here.
You'll have to take me on faith.
But the point is that we've defined this notion of perfect indistinguishability via
an experiment that explicitly mentions an attacker A.
That's different from what we had for the case of perfect secrecy.
But never the less, this definition that we get by defining that experiment,
this definition of perfect indistinguishability.
Is exactly equivalent to our prior definition of perfect secrecy.
We're now going to define our notion of computational secrecy.
By starting with our notion of perfect indistinguishability that we
just defined and relaxing that.
There are two approaches to relaxing that definition.
One of which is called the concrete approach, or
the concrete security approach.
And the other of which is the asymptotic approach, or
the asymptotic security approach.
Recall that to define perfect indistinguishability.
We defined an experiment and
said that an encryption scheme pi was perfectly indistinguishable.
If for all attackers A, the probability that the attacker could succeed in
the experiment was exactly one-half.
In the concrete version of computational indistinguishability,
we're going to relax that in the following way.
Now we'll say that a scheme pi is t epsilon indistinguishable.
If for all the attackers A running at time at most t.
It holds that the probability that the attacker succeeds in
the same experiment as before is at most one-half plus epsilon.
Notice that we take into account both of the relaxations we've
talked about previously.
Right, we restrict our retention here,
only to attackers A, running in time at most t.
Rather allowing all attacker regardless of the running time is
definition of perfect indistinguishability.
And, more over, we define the to be cured as for all such A.
The probability that A can succeed in the experiment is at
most one-half plus epsilon.
So we're allowing an additional epsilon slack in the probability with
which the attacker can succeed.
There are a couple of nice advantages to this notion of concrete security.
First of all, the parameters t and epsilon correspond very closely with what
we ultimately care about in the real world.
In the real world,
we have some assumed time bound with which our adversaries can run.
Right? So, going back to
the example from earlier, we may be concerned with attackers who can run for
time, at most, 100 million years.
And we have this parameter Epsilon, which,
which tells us, essentially, the probability with which security can fail.
So the attacker can succeed with probability one-half, just like in
the case of perfect indistinguishability, plus this extra parameter epsilon.
Which determines the little bit of slack with which we're allowing our
attacker to succeed beyond what it can do.
What it could do if our scheme were perfectly secret.
So concrete security is very nice in that respect because it
maps very cleanly on to things we ultimately care about in practice.
Nevertheless there are some drawbacks to the concrete security approach.
For one thing,
the concrete security approach doesn't really lead to a clean theory.
It's a little hard to go into the details of why that's the case.
You may have a better sense of why this is the case after the,
after you take the rest of this course.
But one thing we can immediately observe is that the parameter t is
very sensitive to the exact computational model.
Right, if we measure t in terms of years, then we have to be
concerned with what kind of computer the attacker is running on.
Whether the attacker is running, computers in parallel.
Whether the attacker is using, a particular operating system.
Whether they're using a particular type of machine,
a particular programming language.
And all these details will impact ultimately the values of t
that we care about.
Now this is actually a problem that we must deal with in the real world.
In the real world we have to worry about some particular attacker.
And we may actually want to know what machine they're running on,
what programming language they're using.
And whether they're running sequentially or
whether they're running a bunch of mis, machines in parallel.
Nevertheless, from a theoretical point of view, it makes things rather messy.
Furthermore, we'd like to have schemes where users are not bound to
some particular choice of t and epsilon.
But where they can instead adjust the levels of security.
That is adjust the parameters t and epsilon that the scheme can provide.
To some levels that are comfortable for them.
And we'll see that in the asymptotic notion of security we can
actually achieve that.
So next time, we'll revisit the notion of computational indistinguishability using
the asymptotic relaxation of perfect indistinguishability.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
