[SOUND] So, far in this class we've talked exclusively about private key cryptography and as we've seen private key cryptography allows two users who share a secret key. To use that key to establish a secure channel between them, that is a way to communicate with both secrecy and integrity. And the problem is that the need to share this secret key incurs several drawbacks. The first of these is what we might call the key distribution problem. And it comes down fundamentally to the following natural question. How do these users who want to share a key go about doing so in the first place? If two users want to set up a secured channel between them, using private key cryptography. They need to share a key, but that key itself needs to be shared using a secure channel. So we have kind of a chicken and an egg problem where the users want this secure channel, but the only way they can get it is by first sharing a key over a secure channel. Why do we need a secure channel for the sharing of the key? Well we need the key to remain secret from any external attacker. And, of course, we'd also like the key to be shared correctly, so that we have integrity of the key that they've shared. Now, of course, in some settings, this problem can be solved. And, in some settings, and in particular, when we talked about private-key cryptography way back in the first week of the course. We said that one thing the users could do for example is to share the key when they're in physical proximity with each other. So perhaps when they're in the same room they can securely share a key and therefore they have some guarantee that there's no attacker eavesdropping on the two users when they're doing that. And then they can go off their separate ways and use the key to set up the secure channel between them. Another thing they could do, if they're never in the same location, is perhaps to use a trusted courier service to transmit a key between them. And then they would, of course, have to assume that the courier, himself, is not an attacker, and, also, that the courier can't be compromised along the way. Now, one thing I want to stress is that the fact that they need this secure channel to share the key initially, and then afterward, they can use that key to bootstrap a secure channel between them, does not make private key cryptography useless. So sometimes people think, well, if they have a secure channel, why don't they just communicate over that secure channel? Why do they need a key at all? But in fact, that's really not true, and if you think about it, you'll see why. For one for the first example, the users might be in physical proximity on one day, but then be far apart on a second day. So that is they have access to a secure channel on day one but then they don't have access to any physical secured channel at any time after that. Instead they'll have to use their key that they shared on day one to communicate to securely for all the other days. In the second example, with a trusted courier. So it's true that the, that the two parties might have access to a trusted courier that they could use for a secure channel between them. However, a trusted courier is inconvenient. It's slow, it's expensive, and there might be some risk that the courier might be compromised. So by relying on that trusted courier only once. And only to share a very short key between them. They can again then leverage that key to communicate securely for all times after that. So this doesn't make private-key cryptography useless. But still, the point is that in some settings there may not be any secure channel at all that the users can rely on. Or at least no secure channel that they can rely on that's relatively cheap. And we'll see later on that really unless you have two users who have some prior relationship it's not going to be feasible for them to set up a physical secure channel of any sort between themselves. The next issue with private key cryptography is what we might call the key management problem. So let's imagine that we have an organization, some company for example. With N employees where each pair of employees might need to communicate securely. And when I say that they might need to communicate securely, I mean that they should be able to communicate securely, even against other employees. So employees a and b might need to communicate without allowing another employee, employee c, to read what they're saying. We can solve this problem using private-key cryptography, all we need to do is make sure that every pair of employees shares a key. That is every employee will share a key with every other employee. Now if you do that, you'll see that each user in the system is now storing and managing N-1 secret keys. Because, again, every user is sharing a distinct key with every other user in the system. So each person is now responsible for storing, maintaining, managing these N-1 secret keys. And if you think of N being on the order of hundreds of thousands. You can see why, why this might be problematic. More over, there are order of N squared keys overall in the system. Right, because the number of pairs of users is order of n squared. Now, this may or may not be a problem, it depends on whether or not we want to assume some central repository some central manager, keeping track of all the keys shared between all the users. And if you did want that, then that entity would have to keep track of order of N squared keys. The third issue with private key cryptography is that it simply does not support what I'll call open systems. And what I mean by that is let's say we have two users who have no prior relationship. But yet they want to communicate securely. Why would these other users have ever had a opportunity to share the key in the past? If they have no prior relationship before the time at which they speech than there would of been no prior opportunity for them to have shared a key. Now when you first see this. You'd think it's very strange that people who have no prior relationship would want to communicate securely. But if you think about it a little more, you realize that it's not at all farfetched, and it's something that happens every day. So for one example, consider a customer sending their credit card information to some internet merchant. So there you have two entities, the customer and the merchant, who may have had no prior relationship. Maybe this is the first time the customer is buying something from this merchant, or maybe the merchant is a new company that just started, and doesn't have any prior relationship with anybody. Nevertheless, a customer may want to send information securely to that merchant. For another example, consider sending an email to a colleague with whom you've never interacted before. So imagine that you wanted to send me an email, for example, to ask me a question about something in the class. Well, you can go and find my web page, find my email address, and send me an email. Even though we really have no prior relationship, per se, and certainly we would not have had any opportunity prior to this to share a key. But again if you wanted to do this, if you wanted to communicate securely in either of these settings private key cryptography simply doesn't offer a way to do that. The main upshot is that classical cryptography by which I mean all of cryptography throughout history up until about the 1970s. Simply does not offer any solution to the three problems I've just mentioned. What we need is a new approach. Now on to the scene jumped a paper by Diffie-Hellman in 1976 that promised as the title indicates. A new direction in cryptography. One that could eliminate all the drawbacks that I just talked about. And in their paper, they introduced many ideas but the key idea I think boils down to the fact that some problems exhibit an asymmetry. In the sense that they're easy to compute, but hard to invert. We've already discussed this previously in the context of factoring, where multiplying two numbers is easy, but taking a product and breaking it up again into its constituent factors is assumed to be hard. And their key idea, the key idea in the Diffie-Hellman paper, is that it's possible to use this asymmetry to enable two parties to agree on a shared secret key, using public discussion. That is, they can agree on a shared key without having access to a secure channel, to a secret channel before that point in time, they can communicate publicly, and thereby agree on a key. And this is called, or protocols that do that, are called key exchange protocols. Now it's really important here to, think about how amazing this idea really is, right? What this means is that you can have two people standing on opposite sides of the room. Shouting back and forth right, using public discussion, shouting back and forth in a way that everyone else in the room can hear. And never the less, at the end of their interaction, at the end of their conversation, they can agree on a secret value that nobody else in the room will be able to figure out. So in pictures this is what it would look like. We have these two users who want to share a key. The first user will communicate, the second user will communicate. They'll exchange messages. And at the end of this process they'll be able to both write down locally a value K. That will be shared with the other party. They'll each have a key that the other party knows. And what they can do then of course is to use that key, coupled with private-key cryptography to set up a secure channel between them. So in this example here, I've indicated that after sharing the key, they could then encrypt some message using the key that they have just shared. So again this gives a way to get the shared key in the first place without relying on any prior secure channel, and then of course leverage that key to set up a secure channel using private key cryptography. A little bit more formally, we imagine the users interacting back and forth in a sequence of rounds. That is exchanging messages in a sequence of rounds. And at the end of this process the two parties should each be able to locally generate a bit string of length N that we'll refer to as a key. And the basic correctness property is that at the end of this interaction the two users will always agree on their shared key. We'll denote the sequence of messages that the parties have exchanged by a transcript. And the security property that we're going to seek is that from an attacker's point of view even if or even after that attacker has observed the entire transcript of the communication between those two users. The shared key, k, that these two users now have, should be indistinguishable from the point of view of the attacker, from a completely uniform key. So again, from the point of view of either of the parties, given their local computation, and the transcript, they can compute the key that the other party will compute also. But from the point of view of the attacker, who only sees the transcript and does not see the local computation of either party, the key that those parties generate should be indistinguishable from a random value. So formerly, let's fix a key-exchange protocol Pi. This was just a sequence sorry. A, a set of protocols that allow the parties to exchange messages and compute a key at the end. And fix some attacker, a, who will be a passive eavesdropper on the protocol. That is, if attacker a will simply be eavesdropping on all of the messages that the parties exchange in the course of running the key exchange protocol, pi. We can now define an experiment called KE for key exchange, where what happens is as follows, the honest parties run the protocol using the indicated security parameter n. Resulting in a transcript, that I'll denote here by trans and some shared key k, which will have length n. The experiment then chooses a uniform bit b. If b is equal to zero, we're going to set some variable K prime, equal to the key that these parties have shared. If b, is equal to one then we choose k prime to be a uniform string. We then give the transcript and k prime to the attacker a, who outputs a bit b prime, which us suppose to indicate as usual a guess. As to whether it was given the actual key shared by the parties or a uniform key independent of the transcript. And the experiment evaluates to one, i.e., a succeeds. If the attacker's guess is correct, i.e., if b prime is equal to b. So again, this is meant to model the attacker a eavesdropping on the communication between the parties. Seeing the transcript trans and even then being unable to distinguish between the actual key k and a completely uniform key of length, n. The key-exchange protocol, pi, is secure against passive eavesdropping, if for all probabilistic polynomial time attackers, a. It holds that the probability with which the attacker can succeed in that experiment is at most one-half plus negligible. And it follows a pattern of all the many of the previous experiments we've seen already in this course. The point being that the attacker can always guess correctly with probability half, but it shouldn't be able to do any better than that. Now I want to make a point here which is that being unable to compute the key given the transcript is a very weak guarantee. That is if we were only to require that an attacker give the transcript could not compute the key shared by the parties that's not really a very strong guarantee and it's not going to be sufficient. For applications of key exchange in cryptography. What we do need, what we need instead, is indistinguishability of the shared key from uniform. This is a much stronger guarantee. It means, for example, that the attacker can't even predict the first bit of the shared key. But this strong guarantee is exactly what's needed if the parties are then going to use the shared key that they've derived. In a part in a private key encryption scheme or in a message authentication code to secure their future communication. And this reason for that is very simple is because whenever we analyze private key cryptography whenever we constructed private key cryptosystems. Where we did so under the assumption that what the parties start with is a uniform key completely unknown to the attacker. And so here, too, what we want to ensure is that after communicating, and after running the key exchange protocols. Even if an attacker has seen the transcript, the key that the parties share should be uniform and completely unknown from the point of view of this computation [INAUDIBLE] attacker. Now one other thing I wanted to mention, is that we've from another point of view, from the point of view of what the attacker is assumed able to do, our definition is rather weak. And in particular we've only defined a notion of security against a passive eavesdropper who just sits back and looks at the protocol messages going back and forth. In practice, that level of security is not sufficient. And in practice, what we want instead is a notion called authenticated key exchange where not only are parties able to generate a shared key, but also that the parties should both know each other's identities. And they should know in particular who they've shared the key with. And if they want to share a key with one particular other party they should be assure that they've done so and that they haven't inadvertently shared the key with somebody else. In particular having shared the key with the adversary. Modern key exchange protocols do provide this stronger notion of security. They provide authenticated key exchange assuming some prior set up. That I don't want to talk about now, but we will come back to after the next week of the course. In the next lecture, we'll see an example of the canonical key exchange protocol. The Diffie-Hellman key-exchange protocol, the one introduced in their famous 1976 paper.
