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

409 ratings

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

[SOUND].

Let's summarize where things stand.

We saw several lectures ago, that there are some inherent limitations,

if we want an encryption scheme that achieves perfect secrecy.

And in particular one of those limitations, was that the key in any

perfectly secret encryption scheme, had to be as long as the message being encrypted.

We defined computational secrecy, a relaxed notion of security,

that still provides meaningful guarantees in practice.

And we did this exactly in order to try to circumvent the limitations we saw,

that were inherent for perfect secrecy.

So the natural question now is, given our notion of computational secrecy,

can we construct schemes, that meet that notion of security, and

that overcome, the previous limitations?

Well remember the one-time pad encryption scheme.

In the one-time pad encryption scheme, we have a key,

that's a p bit long string, where the key is chosen uniformly at random.

And we use that key to encrypt a p bit message,

by simply XORing the key and the message, to obtain the ciphertext.

Again, the point here is that the key is chosen uniformly, and

it's as long as the message being encrypted.

So if the message being encrypted is very long,

think of p being megabytes, then the key has to be very long as well.

But in the last lecture we explore the notion of pseudorandom generators.

And we said that a pseudorandom generator, is exactly an algorithm,

that expands a short uniform seed into a longer, pseudorandom output.

It seems like we can use pseudorandom generators directly,

to improve the efficiency, of the one time pad encryption scheme.

At least in terms of the length of the key.

And in fact, that's exactly what we can do.

So what I've done here, is just augment the picture from the previous slide, and

add a pseudorandom generator to it.

The scheme now ,will have the two parties sharing an n bit key that they'll

then feed into the pseudorandom number generator, to obtain a p bit output.

They'll use that p bit output, as a pseudo key.

It'll be used essentially to implement the one-time pad encryption scheme, but

that pseudo key, is different from the key on the previous slide, because now,

the pseudo key is not uniform.

The pseudo key is pseudorandom, rather than random.

Nevertheless, we can use this p bit string that we've obtained,

to encrypt just like in the one-time pad.

We take the p bit pseudo key, we XOR it with our message, and

we obtain a p bit ciphertext.

Now it may look like we haven't achieved very much in

comparison with the one-time pad encryption scheme, but that's not true.

In this scheme, the key is n bits long, rather than p bits long.

The parties are sharing an n bit key, and using that key,

to encrypt a p bit message.

As indicated in the diagram, and can be much smaller than p, so the parties

can share a key now that's much shorter, than the methods we're encrypting.

Formally, we can define the pseudo one-time pad encryption scheme,

in the following way.

Let G be some deterministic polynomial time function that's expanding, where

the length of the output of G of k, is some polynomial p of, of the length of k.

Key generation in a pseudo one-time pad encryption scheme, does as follows.

On security parameter n, it outputs a uniform n bit key k.

And on security parameter n,

the scheme will allow the parties to encrypt, a message of length p of n.

So the message space now is going to be a function of the security parameter, and

the message space on security parameter n will consist of all strings,

of length p of n.

To encrypt a p bit or a p of n bit message m using the n bit k key,

we apply the pseudorandom generator G to k.

Obtain a p bit string and XOR that with the message m.

And that's our ciphertext.

To decrypt the ciphertext c using the key k, we again apply G to k and

XOR the result to c, to obtain the original message.

And correctness here is obvious.

It's the same kind of argument, as in the one-time pad encryption scheme.

Now, what we can say about the security,

of the pseudo one-time pad encryption scheme?

Remember that our goal here,

is not to come up with a heuristic candidate encryption scheme, but

to come up with an encryption scheme that we can actually prove something about.

And we'd like to be able to prove, that the pseudo one-time pad encryption scheme,

meets our notion of computational secrecy.

Now we're not going to be able to prove this unconditionally,

because on the previous slide,

G was an arbitrary algorithm, mapping inputs to longer outputs.

What we can do, however, or what we can hope to do,

at least, is to prove that the pseudo one-time pad encryption scheme, is secure,

if the function G that's used, is a pseudorandom generator.

That is, if we start with the assumption, that G is a pseudorandom generator.

Then we can hope to prove that the resulting construction of

the pseudo one-time pad, based on that G, is an encryption scheme,

meeting our notion of computational secrecy.

And this is exactly what we'll show, in the next lecture.

We'll talk in the next lecture about the general idea, of proofs by reduction,

which is a general paradigm, in which cryptographic proofs are done.

And then we'll show how to use that technique, to prove security of the pseudo

one-time pad, under the definition we've been discussing until now,

the definition of computational secrecy or computational indistinguishability.

And under the assumption that G is a pseudorandom generator.

This brings together the three principles of modern cryptography,

that we talked about several lectures ago.

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