[SOUND]. This week, we're going to focus on Digital signatures. We've introduced Digital signatures already, and we've said that they're a mechanism that can be used to provide integrity in the public-key setting. And in that sense their analogous to message authentication codes, however there is some key differences between message authentication codes and Digital signatures that I want to explore in this lecture. Before doing that however, I just want to describe at a high level how Digital signatures can be used. We're in the public-key setting, and so again we have one party who locally generates a pair of public and private-keys. They then need to make their public-key widely available to any other party who wishes to obtain a copy. In this picture, I've just displayed that as having this party put their public-key into some database that's widely accessible. Some other party who wishes to obtain a copy of the first party's public-key can access the database and obtain the key. And now at any point in the future, the original party who generated the public and private-keys, has the ability to authenticate a message m. By signing it using their private-key to obtain a signature that we'll denote by sigma. They can then send the pair contain including the message as well as the signature. And anybody else who has a copy of that senders public-key can then try to verify the signature on the claimed message. As in the case of message authentication codes, we'll denote output of the algorithm by a single bit, with a one indicating acceptance and zero indicating rejection. So if the verification algorithm here was, is taking as input the public-key, the message and the signature. If that output's 1, then the receiver is assured that the message they received did indeed originate at the claimed sender. That is, at the party who generated this public key in the first place. Now I want to briefly compare the situation with that of public-key encryption. Here in the context of Digital signatures, the party who generates the public and private-key pair is acting as the sender. And other parties who obtain that first party's public-key, are acting as the receiver. And they're verifying that messages that they receive did indeed originate at the claimed sender. And that's in contrast to public-key encryption. Where in that setting, the party that generates the public private-key pair is acting as the receiver. And other parties who have that party's public-key, are acting as the senders in that case. So, the roles are reversed when we compare public-key encryption to Digital signatures. Now the Security goal informally is analogous to what we've seen already for the case of message authentication codes. Namely that even after observing signatures on multiple messages, an attacker should be unable to forge a valid signature on any new message. That is, the attacker should be unable to come up with a signature a message signature pair that will verify correctly for any message that did not originate at the sender itself. And of course the key difference between the setting of digital signatures and message authentication codes is that in the context of digital signatures, we have to assume that attacker himself also has a copy of the sender's public-key. Now a Prototypical application of digital signatures is broadcasting patches for software. So imagine that we have here on the right hand side an entity that distributes software, and they'd like to occasionally issue patches whenever bugs are discovered in their software. And here on the left hand side, we have three clients who each hold the public-key of the software company who holds the matching private-key. So now for example when the company wishes to is, issue a patch. They'd like to make sure that the patch is obtained unmodified by the clients. It would be very undesirable if an attacker could simply modify the patch, and perhaps make sure that the patch does not actually update the bug in the software, or perhaps introduces a new bug of the attackers choice. So what they can do is very simple. They can simply find the patch that they're going to release, and then broadcast the patch along with the signature. Any client who obtains the patch and the signature, can then verify the new patch before installing it. And this is actually exactly what's used nowadays by software distributors like Microsoft or like Adobe when they release patches for their software. Every time you download a patch from one of these companies, that patch is first being verified to make sure that it's authentic before that patch is being installed. And, of course, the goal of all of this as we've been saying, is to prevent an attacker from modifying the patch, from giving a client a fake patch that did not originate at the claimed sender. Because the signature scheme will exactly ensure that if the client tries to verify that patch, the patch prime, that verification will fail, and the client will simply reject the patch and refuse to install it. Now, if we want to compare this to the situation with message authentication codes, we could ask for example whether message authentication codes could be used in the preceding scenario. And one way you might think to do that is simply to have the software distributors share a key k with every client who purchases a copy of their software. Maybe the key is actually hardcoded into the software itself. And therefore it wouldn't be difficult to distribute that key along with the software. And then when they want to issue a patch, the software distributor would simply authenticate the patch using a message authentication code. And send the resulting tag t along with the patch. And this could again be verified by each client. What's the problem with this approach? Well the problem is that every client, every user of the software, has a copy of the key that the software distributor is using. And what that means is that there's nothing preventing any of those clients from generating their own tag, t prime, on any patch of their choice. Right the whole point of message authentication codes is that they are symmetric, both the sender and the receiver have the same key k. And so anything that the sender can do namely authenticating patches in this case, so can any of the receivers do as well. So if any of the clients if any of the purchasers of the software decide to behave maliciously, they can issue their own patch patch prime along with a valid tag t prime. And then maybe send it to another client or may obviously they'd have to pretend that it is coming from the trusted source. But they could very easily fool another client into installing a, an incorrect patch. We could try to fix that by perhaps having the software distributor, the software company, share a different key with every client. So in this case when the company wishes to issue a patch, they would need to compute three different message authentication codes using keys k1, k2 and k3. And then perhaps I'd have to worry about sending the patch with the right tag to the right customer. Or maybe they would just send all of them, and then customers would have to choose which of tags they verify. Now this approach will not have the problem on the previous slide. All right, so the top most user in this case does not have k2, and therefore will not be able to generate a valid tag on a patch that did not originate from the company. But the problem with this approach is simply that it's unmanageable. You have here a company sharing a different key with each one the users of its software. And in the picture, I only have three clients. But if you think about modern software, you might have hundreds of thousands, millions or tens of millions of clients, and managing all of those keys is simply prohibitive. Not only do you have to manage and store all these keys, but you need to generate message authentication codes, you need to generate tags with respect to all of those keys. And that takes time and is much more complicated and cumbersome, then just generating a single signature on your patch. You also have to worry, as I mentioned before, about getting the right tag to the right user, so that they can actually verify it as well. Furthermore, in this case you have the additional problem of distributing the keys in the first place. I mentioned on the previous slide that you could imagine hard coding a key k into the software and getting that to each client, each user of the software. But here somehow the company would have to put in a different key into every version of the software, and then keep track of which user has those keys, and which keys have been issued so far. And this just adds to the complexity of the problem. So what you can see is that for the case of software distribution or patch distribution, signatures really are the mechanism of choice for doing that. Now there are a number of other dimensions along which I wanted to compare message authentication codes and digital signatures. First of all as might be clear but it worth, it's worth repeating anyway, that, in contrast to message authentication codes, digital signatures have this property of public Verifiability. Namely, anyone, or anyone who can get a copy of the sender's public key, at least, can verify a purported signature from that sender. And this is in contrast to the case of message authentication codes, where only a party who holds the matching key can verify the tag. And this actually has a number of very important consequences. First of all it implies that signatures are Transferable. And what I mean by that simply is that if I obtain a signature from a sender on some message, then I can forward that message signature pair to somebody else, and then they would be able to verify it too. So if you think back to the example of the patch distribution, you could imagine that the company only sends the patch along with the signature to the first client, say the topmost client. And then that client could, in turn, forward it to the second client, along with the signature. And that second client would then be able to verify the signature and then install the patch themselves, and then perhaps forward that on to a third client as well. Now with message authentication codes, you could imagine doing a similar thing. But the problem is that if we think about the case where each client has a unique key, then the first client, maybe he gets the message along with two tags, t1 and t2, and he can verify the first. He can't verify the second but he can forward it along. But then he has no idea whether that's going to be a valid tag, and whether or not the second client will verify that correctly or not. And this can cause trouble, if for example, he forwards a tag to the second client. And that second client cannot verify, and blames the first client for a problem. When really the problem was perhaps the tag that was sent to it by the company in the first place. So the, the real issue is that with Transferability is that you can transfer a signature. And I know that since I was able to verify it, you'll be able to verify it too. And you don't have that assurance with message authentication codes, unless we happen to be using the same key. And then you run into the security problems that we had on the, on the first proposed solution for patch distribution using message authentication codes. Finally, the Public verifiability property of signatures, provides the very important property of non-repudiation that I want to talk about on the next slide. Non-repudiation basically means that a signer, the sender, cannot easily deny issuing a signature. So that is, that if a sender who generated their public and private-key and then made their public-key widely available. If they find some message and release the message and, the message and signature to somebody else, then anybody else who's able to get a copy of that message signature pair will be convinced that the original signer did indeed sign that message and issue that message. And this is crucial for legal applications. So imagine you have two parties negotiating a contract, and one of those parties say, issues a signature on the contract. Now if they later violate the contract, well the second party can go to a judge, can go to a court, and show them a copy of the contract along with the signature. And that signature on the contract is proof that the first party did indeed sign that contract at some point in time. And the judge can go ahead and verify that signature using the public copy, the publicly available copy, of the public-key of that signer. And MACs simply cannot provide this functionality. And it's worth thinking about why. First of all, without access to the key, there will be no way for the judge or the court to verify the tag. Now even if the second party, the receiver, gives the key to the judge and says, here, here's the key, verify the, the tag on this contact. How does the judge know that the key is correct? Right, the key could have been something that the receiver made up. And this is in contrast to the case where the judge gets a copy of the public-key of the signer, where the public-key then is in some public database, it's been in there for maybe a year. And so it's clear that this really is the public-key belonging to the signer. Moreover, even if the key is correct and even if there was some way to verify using some attestation mechanism that the key that the receiver provides the judge is indeed the key that, that receiver shared with the sender. It doesn't prove anything. And the reason again is the fact that MACs are symmetric. And so any tag that the sender could have generated, say a tag on this contract, could have just as easily been generated by the receiver itself. And so the tag on the contract only proves in that case, that one of the two parties, either the sender or the receiver, generated the tag on that contract. It doesn't prove which one. And again, that's in contrast to digital signatures where only the person who generated the public key, and who therefore has the matching private key, could have possibly generated that signature. In the next lecture, we'll talk about Formal definitions of security for signatures. And we'll also cover the very important hash-and-sign paradigm that's used for signing long messages.
