Before we start with the technical material, I wanna give you a quick overview of what cryptography is about and the different areas of cryptography. So the core of cryptography of course is secure communication that essentially consists of two parts. The first is secured key establishment and then how do we communicate securely once we have a shared key. We already said that secured key establishment essentially amounts to Alice and Bob sending messages to one another such that at the end of this protocol, there's a shared key that they both agree on, shared key K, and beyond that, beyond just a shared key, in fact Alice would know that she's talking to Bob and Bob would know that he's talking to Alice. But a poor attacker who listens in on this conversation has no idea what the shared key is. And we'll see how to do that later on in the course. Now once they have a shared key, they want exchange messages securely using this key, and we'll talk about encryption schemes that allow them to do that in such a way that an attacker can't figure out what messages are being sent back and forth. And furthermore an attacker cannot even tamper with this traffic without being detected. In other words, these encryption schemes provide both confidentiality and integrity. But cryptography does much, much, much more than just these two things. And I want to give you a few examples of that. So the first example I want to give you is what's called a digital signature. So a digital signature, basically, is the analog of the signature in the physical world. In the physical world, remember when you sign a document, essentially, you write your signature on that document and your signature is always the same. You always write the same signature on all documents that you wanna sign. In the digital world, this can't possibly work because if the attacker just obtained one signed document from me, he can cut and paste my signature unto some other document that I might not have wanted to sign. And so, it's simply not possible in a digital world that my signature is the same for all documents that I want to sign. So we're gonna talk about how to construct digital signatures in the second half of the course. It's really quite an interesting primitive and we'll see exactly how to do it. Just to give you a hint, the way digital signatures work is basically by making the digital signature via function of the content being signed. So an attacker who tries to copy my signature from one document to another is not gonna succeed because the signature. On the new document is not gonna be the proper function of the data in the new document, and as a result, the signature won't verify. And as I said, we're gonna see exactly how to construct digital signatures later on and then we'll prove that those constructions are secure. Another application of cryptography that I wanted to mention, is anonymous communication. So, here, imagine user Alice wants to talk to some chat server, Bob. And, perhaps she wants to talk about a medical condition, and so she wants to do that anonymously, so that the chat server doesn't actually know who she is. Well, there's a standard method, called a mixnet, that allows Alice to communicate over the public internet with Bob through a sequence of proxies such that at the end of the communication Bob has no idea who he just talked to. The way mixnets work is basically as Alice sends her messages to Bob through a sequence of proxies, these messages get encrypted and decrypted appropriately so that Bob has no idea who he talked to and the proxies themselves don't even know that Alice is talking to Bob, or that actually who is talking to whom more generally. One interesting thing about this anonymous communication channel is, this is bi-directional. In other words, even though Bob has no idea who he's talking to, he can still respond to Alice and Alice will get those messages. Once we have anonymous communication, we can build other privacy mechanisms. And I wanna give you one example which is called anonymous digital cash. Remember that in the physical world if I have a physical dollar, I can walk into a bookstore and buy a book and the merchant would have no idea who I am. The question is whether we can do the exact same thing in the digital world. In the digital world, basically, Alice might have a digital dollar, a digital dollar coin. And she might wanna spend that digital dollar at some online merchants, perhaps some online bookstore. Now, what we'd like to do is make it so that when Alice spends her coin at the bookstore, the bookstore would have no idea who Alice is. So we provide the same anonymity that we get from physical cash. Now the problem is that in the digital world, Alice can take the coin that she had, this one dollar coin, and before she spent it, she can actually make copies of it. And then all of a sudden instead of just having just one dollar coin now all of a sudden she has three dollar coins and they're all the same of course, and there's nothing preventing her from taking those replicas of a dollar coin and spending it at other merchants. And so the question is how do we provide anonymous digital cash? But at the same time, also prevent Alice from double spending the dollar coin at different merchants. In some sense there's a paradox here where anonymity is in conflict with security because if we have anonymous cash there's nothing to prevent Alice from double spending the coin and because the coin is anonymous we have no way of telling who committed this fraud. And so the question is how do we resolve this tension. And it turns out, it's completely doable. And we'll talk about anonymous digital cash later on. Just to give you a hint, I'll say that the way we do it is basically by making sure that if Alice spends the coin once then no one knows who she is, but if she spends the coin more than once, all of a sudden, her identity is completely exposed and then she could be subject to all sorts of legal problems. And so that's how anonymous digital cash would work at a high level and we'll see how to implement it later on in the course. Another application of cryptography has to do with more abstract protocols, but before I speak the general result, I want to give you two examples. So the first example has to do with election systems. So here's the election problem. Suppose ... we have two parties, party zero and party one. And voters vote for these parties. So for example, this voter could have voted for party zero, this voter voted for party one. And so on. So in this election, party zero got three votes and party two got two votes. So the winner of the election, of course, is party zero. But more generally, the winner of the election is the party who receives the majority of the votes. Now, the voting problem is the following. The voters would somehow like to compute the majority of the votes, but do it in such a way such that nothing else is revealed about their individual votes. Okay? So the question is how to do that? And to do so, we're gonna introduce an election center who's gonna help us compute the majority, but keep the votes otherwise secret. And what the parties will do is they will each send the funny encryption of their votes to the election center in such a way that at the end of the election, the election center is able to compute and output the winner of the election. However, other than the winner of the election, nothing else is revealed about the individual votes. The individual votes otherwise remain completely private. Of course the election center is also gonna verify that this voter for example is allowed to vote and that the voter has only voted once. But other than that information the election center and the rest of the world learned nothing else about that voter's vote other than the result of the election. So this is an example of a protocol that involves six parties. In this case, there are five voters in one election center. These parties compute amongst themselves. And at the end of the computation, the result of the election is known but nothing else is revealed about the individual inputs. Now a similar problem comes up in the context of private auctions. So in a private auction every bidder has his own bid that he wants to bid. And now suppose the auction mechanism that's being used is what's called a Vickrey auction where the definition of a Vickrey auction is that the winner is the highest bidder. But the amounts that the winner pays is actually the second highest bid. So he pays the second highest bid. Okay, so this is a standard auction mechanism called the Vickrey auction. And now what we'd like to do is basically enable the participants to compute, to figure out who the highest bidder is and how much he's supposed to pay, but other than that, all other information about the individual bids should remain secret. So for example, the actual amount that the highest bidder bid should remain secret. The only thing that should become public is the second highest bid and the identity of the highest bidder. So again now, the way we will do that is we'll introduce an auction center, and in a similar way, essentially, everybody will send their encrypted bids to the auction center. The auction center will compute the identity of the winner and in fact he will also compute the second highest bid but other than these two values, nothing else is revealed about the individual bids. Now, this is actually an example of a much more general problem called secure multi-party computation. Let me explain what secure multi-party computation is about. So here, basically abstractly, the participants have a secret inputs to themselves. So, in the case of an election, the inputs would be the votes. In the case of an auction, the inputs would be the secret bids. And then what they would like to do is compute some sort of a function of their inputs. Again, in the case of an election, the function's a majority. In the case of auction, the function happens to be the second highest, largest number among x one to x four. And the question is, how can they do that, such that the value of the function is revealed, but nothing else is revealed about the individual votes? So let me show you kind of a dumb, insecure way of doing it. What we do is introduce a trusted party. And then, this trusted authority basically collects individual inputs. And it kinda promises to keep the individual inputs secret, so that only it would know what they are. And then, it publishes the value of the function, to the world. So, the idea is now that the value of the function became public, but nothing else is revealed about the individual inputs. But, of course, you got this trusted authority that you got to trust, and if for some reason it's not trustworthy, then you have a problem. And so, there's a very central theorem in crypto and it really is quite a surprising fact. That says that any computation you'd like to do, any function F you'd like to compute, that you can compute with a trusted authority, you can also do without a trusted authority. Let me at a high level explain what this means. Basically, what we're gonna do, is we're gonna get rid of the authority. So the parties are actually not gonna send their inputs to the authority. And, in fact, there's no longer going to be an authority in the system. Instead, what the parties are gonna do, is they're gonna talk to one another using some protocol. Such that at the end of the protocol all of a sudden the value of the function becomes known to everybody. And yet nothing other than the value of the function is revealed. In other words, the individual inputs is still kept secret. But again there's no authority, there's just a way for them to talk to one another such that the final output is revealed. So this is a fairly general result, it's kind of a surprising fact that is at all doable. And in fact it is and towards the end of the class we'll actually see how to make this happen. Now, there are some applications of cryptography that I can't classify any other way other than to say that they are purely magical. Let me give you two examples of that. So the first is what's called privately outsourcing computation. So I'll give you an example of a Google search just to illustrate the point. So imagine Alice has a search query that she wants to issue. It turns out that there are very special encryption schemes such that Alice can send an encryption of her query to Google. And then because of the property of the encryption scheme Google can actually compute on the encrypted values without knowing what the plain texts are. So Google can actually run its massive search algorithm on the encrypted query and recover in encrypted results. Okay. Google will send the encrypted results back to Alice. Alice will decrypt and then she will receive the results. But the magic here is all Google saw was just encryptions of her queries and nothing else. And so, Google as a result has no idea what Alice just searched for and nevertheless Alice actually learned exactly what she wanted to learn. Okay so, these are magical kind of encryption schemes. They're fairly recent, this is only a new development from about two or three years ago, that allows us to compute on encrypted data, even though we don't really know what's inside the encryption. Now, before you rush off and think about implementing this, I should warn you that this is really at this point just theoretical, in the sense that running a Google search on encryption data probably would take a billion years. But nevertheless, just the fact that this is doable is already really surprising, and is already quite useful for relatively simple computations. So in fact, we'll see some applications of this later on. The other magical application I want to show you is what's called zero knowledge. And in particular, I'll tell you about something called the zero knowledge proof of knowledge. So here ... what happens is there's a certain number N, which Alice knows. And the way the number N was constructed is as a product of two large primes. So, imagine here we have two primes, P and Q. Each one you can think of it as like 1000 digits. And you probably know that multiplying two 1000-digit numbers is fairly easy. But if I just give you their product, figuring out their factorization into primes is actually quite difficult. And, in fact, we're gonna use the fact that factoring is difficult to build public key cryptosystems in the second half of the course. Okay, so Alice happens to have this number N, and she also knows the factorization of N. Now Bob just has the number N. He doesn't actually know the factorization. Now, the magical fact about the zero knowledge proof of knowledge, is that Alice can prove to Bob that she knows the factorization of N. Yes, you can actually give this proof to Bob, that Bob can check, and become convinced that Alice knows the factorization of N, however Bob learns nothing at all. About the factors P and Q, and this is provable. Bob absolutely learns nothing at all about the factors P and Q. And the statement actually is very, very general. This is not just about proving the factorization of N. In fact, almost any puzzle that you want to prove that you know an answer to, you can prove it is your knowledge. So if you have a crossword puzzle that you've solved. Well, maybe crosswords is not the best example. But if you have like a Sudoku puzzle, for example, that you want to prove that you've solved, you can prove it to Bob in a way that Bob would learn nothing at all about the solution, and yet Bob would be convinced that you really do have a solution to this puzzle. Okay. So those are kind of magical applications. And so the last thing I want to say is that modern cryptography is a very rigorous science. And in fact, every concept we're gonna describe is gonna follow three very rigorous steps, okay, and we're gonna see these three steps again and again and again so I wanna explain what they are. So the first thing we're gonna do when we introduce a new primitive like a digital signature is we're gonna specify precisely what the threat model is. That is, what can an attacker do to attack a digital signature and what is his goal in forging signatures? Okay, so we're gonna define exactly what does it mean for a signature for example to be unforgeable. Unforgeable. Okay and I'm giving digital signatures just as an example. For every primitive we describe we're gonna precisely define what the threat model is. Then we're gonna propose a construction and then we're gonna give a proof that any attacker that's able to attack the construction under this threat model. That attacker can also be used to solve some underlying hard problem. And as a result, if the problem really is hard, that actually proves that no attacker can break the construction under the threat model. Okay. But these three steps are actually quite important. In the case of signatures, we'll define what it means for a signature to be, forgeable, then we'll give a construction, and then for example we'll say that anyone who can break our construction can then be used to say factor integers, which is believed to be a hard problem. Okay, so we're going to follow these three steps throughout, and then you'll see how this actually comes about. Okay, so this is the end of the segment. And then in the next segment we'll talk a little bit about the history of cryptography.
