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

417 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

In this lecture we're going to explore the asymptotic relaxation, of perfect secrecy.

Â We'll begin just by reviewing the notion of perfect indistinguishability.

Â Let pi be an encryption scheme, and A an adversary, i.e an eavesdropper.

Â Remember that we define the following randomized experiment,

Â that depends on both A and pi.

Â First, the attacker outputs two messages m0 and m1, in the message space.

Â Then, a key is generated using the key generation algorithm.

Â A uniform bit B is chosen, and

Â then we encrypt the message m sub b, using the key k, that we just generated.

Â This gives us a ciphertext c.

Â We give that ciphertext to the attacker.

Â Right, modeling the attacker's ability to eavesdrop and

Â view the ciphertext being sent between the parties.

Â And the attacker then outputs a bit,

Â b prime, which represents its guess, as to which of the two messages was encrypted.

Â We say that A succeeds, if its guess is correct, i.e.

Â If b prime is equal to b.

Â And the experiment evaluates to 1 if and only if, A succeeds.

Â We then say that the encryption scheme pi, is perfectly indistinguishable, if for

Â all attackers A, it holds that the probability that the experiment evaluates

Â to 1 that is the probability which with A succeeds, is exactly one-half.

Â Now, remember that we wanted to relax the notion of perfect indistinguishability,

Â in two different dimensions.

Â First all, we're going to allow security to fail, with some small probability.

Â Secondly, we're going to restrict our attention to efficient attackers only.

Â And as we mentioned last time there are two approaches for

Â doing this, the concrete approach, and the asymptotic approach.

Â Remember that in the concrete approach,

Â we define the notion of t epsilon indistinguishability.

Â Here we allow security to fail, with probability at most epsilon.

Â And we restrict our attention to attackers, running in time, at most t.

Â We can then set these parameters, t and epsilon any way we like, and

Â get the corresponding notion of t epsilon indistinguishability.

Â For the asymptotic relaxation,

Â we're going to do something a little bit more complicated.

Â What we're going to do,

Â is we're going to introduce the notion, of a security parameter n.

Â The security parameter, is a positive integer, and we can view this as allowing

Â the parties to choose the level of security, that they want for the scheme.

Â And for now, you can view n, as denoting the key length.

Â That is the length of the key that the parties share.

Â The security parameter, or the key length, is going to

Â be fixed by the honest parties, at the time, the system is initialized.

Â That is at the time they choose and share their key.

Â We're going to assume further, that the attacker, knows n.

Â The attacker knows the security parameter.

Â The attacker knows, the length of the key that the parties are sharing.

Â Now the important point, or the use of the security parameter,

Â is that we're now going to view the running times of all parties.

Â That is, the honest parties as well as the attacker,

Â as well as the success probability of the adversary, as functions of n.

Â So we're going to look at how the running time of the parties changes, as n varies.

Â And also look at the how the success probability of the attacker varies,

Â as n is increased.

Â So for computation indistinguishability,

Â we're now going to relax the notion of perfect indistinguishability as follows.

Â We're now going to allow security to fail, with probability negligible in n.

Â And we're going to restrict our attention to attackers,

Â running in time polynomial in n.

Â And I'll define both of these terms on the next slide.

Â Let's look at the case of polynomial first,

Â since this concept is probably already familiar to you.

Â We're interested in looking,

Â at the attacker's running time, as a function of the security parameter n.

Â So this means that for different values of the security parameter n,

Â we have a different amount of time that, for which the adversary runs.

Â That's going to be defined by some function, that maps,

Â the security parameter, which is a positive integer,

Â onto the running time of the attacker which is another positive integer.

Â Given some function f like that, we'll say that f is polynomial.

Â If there exists a finite number of constants ci, such that f of n is at most,

Â the summation of ci into the i, for all n.

Â Technically we should actually refer to this as being polynomialy bounded, right,

Â f not need be a polynomial itself.

Â All we care about is that it's upper bounded by a polynomial.

Â But hopefully, you'll be okay with this slight abus, abusive notation.

Â For the attacker's success probability, we're interested in looking at the success

Â probability of the attacker as a function again, of the security parameter n.

Â This means that for each value of n, which is again a positive integer, we get some

Â values some probability, which has a positive real number or possibly 0.

Â In fact it's in the range of 0 to 1,

Â but we can allow all real numbers just for generality.

Â So define a function f of this form, to be negligible, if for

Â every polynomial p, there are some bound to capital N

Â such that f of n is smaller than 1 over p of n, for all n larger than that bound.

Â What this means is that the function f is negligible,

Â if it's asymptotically smaller, than any inverse polynomial function.

Â Now, a typical example of a negligible function,

Â is something of the form polynomial in n, times an inverse exponential in n.

Â So something like poly n times 2 to the minus cn, for some constant c.

Â That's a very common example in cryptography, but

Â that's not the only possibility, for a negligible function.

Â Why do we make these choices for defining the terms of a small probability of

Â success, and the notion of an efficient attacker.

Â Well to some extent the choices are arbitrary, and

Â you can come up with an equally valid theory, by making other choices for

Â how to define, small and efficient.

Â On the other hand, there are some good reasons for making these choices.

Â The notion of equating efficient attackers,

Â with probabilistic polynomial-time algorithms, which I'll abbreviate by PPT,

Â is something that's borrowed from complexity theory.

Â Where traditionally, we define the notion of problems that can be

Â solved efficiently, as problems that can be solved in polynomial time.

Â More than that, the choices of polynomial and

Â negligible, have some very convenient and nice to use closure properties.

Â One of those, is that if you have two polynomial functions and

Â multiply them, the result is also a polynomial function.

Â And what this means is that if you have polynomially many calls,

Â to some polynomial-time subroutine the net result is a polynomial-time algorithm.

Â So if you have an algorithm and

Â the description of that algorithm you verified is polynomial-time, and

Â then that algorithm makes some calls to a subroutine that also is implemented in

Â polynomial-time, the net result is an algorithm running in polynomial-time.

Â Another such closure property, is that any polynomial function,

Â multiplied by any negligible function, is again negligible.

Â And what this means is that if you have an algorithm,

Â that makes polynomially many calls to some subroutine.

Â Where that subroutine might fail with negligible probability every time it's

Â called, then, the probability that the algorithm overall ever fails,

Â is still negligible.

Â So let's redefine secure encryption, using this notion of the security parameter.

Â It's larger the, largely the same as before.

Â I just want to highlight some technical points.

Â So a private-key encryption scheme,

Â as before, is defined by three algorithms, the key generation algorithm,

Â the encryption algorithm and the decryption algorithm.

Â But we're now going to additionally require that those algorithms,

Â run in probabilistic polynomial time.

Â Recall we said a few slides ago, that we want all parties to run efficiently.

Â And that includes the honest parties who are going to be running this algorithm.

Â The key generation algorithm takes as input, the security parameter in unary.

Â So, it takes as input formally the string, 1 to the n, i.e.

Â The string of n consecutive ones.

Â This is really just a formalism, that allows the key generation algorithm to

Â run in time polynomial in n, because traditionally we allow algorithms to

Â run in time polynomial, in the length of their input.

Â So we just provide it with an input of length n, to allow it to run for

Â time polynomial in n.

Â The key generation algorithm then outputs the key k as before, and

Â we'll assume that the key length, is at least equal to n.

Â The encryption algorithm, takes as input a key and a message m,

Â and outputs a ciphertext c as before.

Â One thing I just want to highlight here, is that I've made the choice to by

Â default, assume that encryption can take messages of arbitrary length.

Â That is, we're now going to assume that the message space,

Â consists of all binary strings of any length, rather than requiring the message

Â space to be explicitly defined, as part of the encryption scheme.

Â Sometimes, actually, we'll restrict that and only consider encryption schemes that

Â encrypt messages of some particular length.

Â The decryption algorithm, as before,

Â takes as input a key k and a ciphertext c, and outputs a message m, or an error.

Â And I've omitted the standard correctence condition that an encryption scheme

Â should satisfy.

Â We can now look at the asymptotic version, of computational indistinguishability.

Â Fix some encryption scheme pi and some algorithm a,

Â and define a randomized experiment, very similar to what we had before.

Â We have a, an experiment that depends on a and

Â pi, and in addition it's parameterized, by the security parameter n.

Â And we'll see how for different values of n, the experiment depends on n.

Â The experiment has some dependence on this value n.

Â So the experiment runs as follows.

Â We run our algorithm A, on input 1 to the n.

Â This is just our mechanism for

Â informing the attacker A, about what value of a security parameter we're using.

Â This also allows the attacker, to run in time, that's a function of n.

Â A function of its input length.

Â The attacker outputs m0 and m1 as before.

Â Although now we're going to add the condition, that m0 and m1,

Â have to be equal length.

Â This didn't come up before, because in general we were assuming that

Â we had a message space containing only messages of some fixed length,

Â whereas now that's not the case.

Â Here we're going to restrict the attacker to only output messages of equal length.

Â And we'll have more to say about this later.

Â The second part of the experiment is exactly as before.

Â We choose a key k, by running the key generation algorithm, on input 1 to the n.

Â We choose a uniform bit b, and then we encrypt message m sub b

Â using the key k that we just generated, to obtain a ciphertext c.

Â We give the ciphertext to A,

Â who outputs a bit b prime, and we'll say that a succeeds if b is equal to b prime.

Â And we'll define the experiment to output 1 or to evaluate to 1 in this case.

Â I want to highlight here that we're viewing A as a stateful algorithm

Â that is given 1 to then and outputs the messages and

Â then keeps on running, and is later given c and outputs b prime.

Â So, you can think of this formally as an algorithm that's maintaining state,

Â throughout this entire randomized experiment.

Â We'll then say that a scheme pi, is indistinguishable, if for

Â all probabilistic polynomial-time attackers A,

Â there's a negligible function epsilon, such that the probability with which

Â A succeeds in the previous experiment, is at most one-half plus epsilon of n.

Â So I want to highlight a couple of things here.

Â The first thing I want to highlight,

Â is that the expression on the left hand side here,

Â the probability with which the attacker succeeds, is indeed a function of n.

Â If we affix some scheme pi and some attacker A, then the, we can, then for

Â any particular value of n, we can evaluate or calculate, the probability with which

Â A succeeds when attacking that encryption scheme pi, in the preceding experiment.

Â And so if we imagine doing that for

Â all possible values of n, then we get something which is a function of n.

Â It's a function that maps from any particular value of

Â the security parameter, to some probability in the range of 0 to 1.

Â So the thing on the left hand side of this expression is indeed a function, and

Â we can ask about the asymptotic behaviour of that function.

Â We'll say that the scheme is secure, if for

Â any polynomial time probabilistic polynomial time attacker A,

Â the probability with which that attacker succeeds, viewed as a function of n,

Â is bounded by one-half plus a negligible function.

Â Plus a, plus some negligible quantity, i.e.

Â Plus some quantity, that decays to 0, faster than any inverse polynomial.

Â So again, we're making the choices here of restricting attention to efficient

Â attackers, i.e probabilistic polynomial-time attackers.

Â And we're allowing the possibility, that attackers can succeed,

Â with probability slight greater than one-half.

Â However, that probability must decay to 0 faster than any inverse polynomial.

Â Let's look at a very simple example just to illustrate,

Â the style of the definition.

Â So consider some scheme pi, just a made-up scheme but imagine that the best

Â attack on the scheme, is a brute-force search over the key space.

Â And that the key generation algorithm, just generates a uniform n bit key.

Â So because we're assuming that the best attack is brute-force search,

Â this means that if we have some attacker that runs in some time, t of n.

Â Right, remember,

Â the attacker is now allowed to make its running time depending on n.

Â And in this case, we're just saying that,

Â on any, value of the security parameter n, the attacker runs in some time t of n.

Â Well then, the success probability of the attacker,

Â is essentially going to be one-half plus the probability with

Â which the attacker happened to find the key in its brute-force search.

Â Since the key was chosen uniformly, and since the attacker,

Â running in time t of n, could have possibly tried at most t of n keys.

Â This means, that the probability with which the attacker succeeds,

Â is at most one-half plus t of n, over 2 to the n.

Â Right, again, t of n over 2 of the n,

Â is a probability with which the attacker found the key, and

Â if the attacker didn't find the key, it can do no better than guess randomly.

Â And so it will succeed in that case with probability one-half.

Â I claim that this means, that this particular scheme pi is secure.

Â Right, why is that?

Â Well we need to argue, that for

Â any attacker running a probabilistic polynomial time, the success

Â probability of that attacker is at most one-half plus a negligible function.

Â Well, for

Â any attacker running in time in polynomial time t of n must then be polynomial.

Â And then the function t of n divided by 2 to the n is negligible.

Â All right, we said earlier that any polynomial times

Â a negligible function remains negligible.

Â Here we have the polynomial t of n, times the negligible function 2 to the minus n.

Â And so the result is negligible.

Â So again, this means that for any pol, pol, probabilistic polynomial time

Â attacker you come up with, that runs in some time t of n.

Â But I don't know what it is, but I do know that it's bounded by a polynomial.

Â The success probability of that attacker is going to be,

Â at most, one-half plus negligible.

Â Different attackers,

Â will have correspondingly different negligible functions.

Â But for all of such attackers, they, they will have some corresponding negligible

Â function that bounds, their advantage over one-half.

Â Now one thing I wanted to point out, is this restriction in the definition where

Â we require the attacker to output two messages of equal length.

Â Now in practice, as I said when I defined encryption in the context of the,

Â the asymptotic notion of security, I said that we

Â generally want encryption schemes that can encrypt arbitrary length messages.

Â However, it's also the case that in general,

Â encryption does not hide the plaintext length.

Â So when I encrypt a short message, I get a ciphertext that is

Â typically shorter than what I get if I encrypt a longer message.

Â So the, an attacker whose eavesdropping on the communication, and observes not only

Â the ciphertext but its length, can learn something of the length of the plaintext.

Â In general, we are willing to allow the attacker to learn that information.

Â And furthermore you can show that under certain conditions, it's

Â really impossible to hide all information about the length of the plaintext.

Â So because we're willing to give that information up,

Â we need to take that into account in our definition.

Â So if we allowed the attacker to output,

Â two arbitrary messages of arbitrary lengths, then the attacker would be

Â able to succeed, with probability, much better than one-half.

Â He could succeed really with probability 1.

Â So the definition takes into account the fact that we don't try to, try to

Â hide the plaintext length, by forcing the attacker by restricting the attacker,

Â to looking at, to outputting equal length messages in 0 and then 1.

Â Now nevertheless, even though we've de, we've made up our definition in this way,

Â made our definition to correspond to what's done in practice that is, and

Â leak the length of the plaintext.

Â It's important to beware,

Â that leaking the plaintext length can often lead to problems in practice.

Â Just because we set up a definition in a particular way,

Â doesn't mean that the problem goes away.

Â It just means that our definition is limited,

Â to only those cases that we include in our definition.

Â There are some very obvious examples of where leaking the plaintext length,

Â can lead to problems.

Â A simple example that I often like to give,

Â is one where somebody's encrypting, yes and no answers to some question.

Â If an attacker can learn the exact length of the plaintext, and

Â can in particular learn whether what's encrypted is a two character message, or

Â a three character message,

Â then whatever encryption scheme you're using if that information is leaked,

Â the attacker can figure out exactly the answers you're sending.

Â There are also some less obvious examples.

Â Think about the case where your encrypting your a database search.

Â So you can just think of a simple case where I encrypt my query to the database

Â and the database evaluates the query and then sends back an encrypted result.

Â Well by looking at the size of the result that's returned,

Â the attacker can get a good sense of what I was searching for.

Â Think about just an encrypted Google search for example.

Â If I search for a if I make a search query for some popular term, I'll get

Â back many more, many more hits than I would if I search an unpopular term.

Â And so that's going to reveal information to the attacker about what it is that I'm

Â searching for.

Â Another good example is if I compress my data before I encrypt it.

Â In that case, if, even if I start with two messages of equal length,

Â they may compress to things that have different lengths,

Â depending on the inherent structure in those two messages.

Â And so if I just blindly compress my data, and

Â then encrypt the result, and the attacker can view the length of the ciphertext and

Â from that, get some information about the length of my compressed data.

Â Then the attacker can glean from that some information about my

Â original uncompressed data.

Â So these are just three examples of the kind of things that can come up

Â in practice.

Â We've defined in this lecture a notion of computational secrecy, and in fact,

Â from now on, we're going to assume the computational setting by default.

Â So we have left the world of perfectly secret cryptography and

Â perfectly secure cryptography in general, and from now on,

Â we're going to only consider the computational setting.

Â Furthermore, almost always we're going to be dealing with

Â an asymptotic notion of security.

Â And I'll only mention a concrete notion of security in passing, at some points.

Â In the next few lectures what we'll do,

Â is we'll progress toward constructing a scheme,

Â that achieves our notion of computational security that we've just defined.

Â And does better than the one-time pad, in terms of the length of the key,

Â that's required.

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