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

320 ratings

University of Maryland, College Park

320 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 2

Computational Secrecy and Principles of Modern Cryptography

- 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 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.

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.

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.

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.

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.

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