MIT公开课：现代加密核心概念

[SQUEAKING] [RUSTLING] [CLICKING] ROBERT TOWNSEND: This is lecture 9 on encryption. Be prepared. There's a bit of math in this, but the main goal is the conceptualization of the problem. So we've got encryption is a tool in and of itself, and it can, therefore, be separated from the ledgers and so on. I have a slide on that. And then we'll come to three interrelated concepts, encoded message systems, hashes, and cryptographic puzzles.

And then I'll circle back to modern encryption, which uses public and private keys, giving you example of cyclic rings. And then we'll go into fully homomorphic encryption, multiparty computation, and zero-knowledge proofs in terms of what they are and some notation. I have been threatening to go back periodically to Bitcoin, which keeps popping up in various of the lectures. In this case, we'll now hopefully have enough of the tools to understand the data storage system in so-called Merkle trees, or hashed trees associated with Bitcoin and the use of proof-of-work algorithm to randomize who is the validator.

And finally, I'll summarize how these FHE, Fully Homomorphic Encryption, multiparty computation, and zero-knowledge proofs fit together in terms of when they are needed or not. So the point of this slide is something I mentioned last time, that programmed contracts are distinct from distributed ledgers. We can use encryption for both, and it's the third leg, in the sense, that we've covered already, distributed ledgers and smart contracts.

Encryption can be used as part of the validation protocol. Validation of the ledgers allows the financial counts to be altered with transfers of money and assets, but done in a secure way because it will be encrypted, hence, no trust is necessary, and this will create immutable and readily indexed records. So that's the ledger part of it. As part of the programming of contracts, we can deal with all kinds of obstacles to trade-- private information, limited communication, limited commitment, confidential data.

So the data need to be secure, and it can be costly to store and retrieve data potentially. So encryption is a way to implement optimized solutions for two or more multilateral agents who want to use or solve a mechanism design problem, but they want to keep the messages they're sending back and forth secret. They want, again, the data to be secure and immutable. They want to be able to commit to the arrangements and commit to the way they're implemented without any inconsistencies even if one-- or if you can wrap your mind around it, if there were two, even if both potentially want to renege.

So that's the big picture. Now let's go to the communication problem and basically think about encrypting messages. So there will be-- and I'm going to do this as kind of an overview and go through the other concepts, and then we'll circle back to some helpful notation. So a public key is an object in the context of a exactly specified mathematical space, and the public key is used to encrypt messages so that what one sees are ciphertext.

Gobbledygook. The ciphertexts are public. There's no attempt to conceal them. The private key is used only for decryption of the messages. And the algorithms make it virtually impossible to decipher an encrypted message without the private key that was used as part of generating it. There's an analogy here associated with prime numbers, and I'll keep coming back to this. And actually, it will be part of the mathematics in the end, that if you have two prime numbers, and the number-- those primes are large enough, it is very difficult to decompose into the underlying primes from the product.

And if you're thinking of 3 plus 5, that doesn't seem terribly hard, but as the numbers get larger and larger, it gets more and more challenging. So anyway, the analogy here is the private key is like one of the two factors that were used for the product, and it's pretty straightforward, computationally much easier to verify that you have a solution once one of the factors. So there's a word in here, algorithms on designated spaces make it virtually impossible.

That's a scary word because actually, you could get lucky and decipher things. It's just the odds are low. And also, as you'll see, it does-- it is a computational issue. So some of these better-known ways of encrypting are vulnerable to quantum computing, and we'll touch on that as we-- so that it's so not so hard after all. OK, so that's messages. What are hash function? A cryptographic hash function is an algorithm that takes an arbitrary amount of an input in size and context and produces a fixed-size output called a hash.

Some properties. A given input always generates the same hash value. The enciphered text is the same if the input is the same. And likewise, a hash cannot be deciphered except by random guessing. So a good hash would be one that makes it very hard to reconstruct the original input from the output. This is called one-way function or non-reversibility. With just one change in one bit of the original input, the output-- the hashed output changes significantly and unpredictably.

So any tinkering is detected because you can compare one hash to a claimed identical copy, and if it used a different input, it will be different, and I'll come back to that. This anti-tinkering is called the diffusion or avalanche effect. And that's going from the hash backwards. Likewise from the inputs, if you had two different inputs to the hash, then it should be hard to find two different inputs that gave the same hash.

Now that reminds me to say that the power of this thing is that the hash is of extraordinarily low dimension relative to the inputs that are being used. And as you'll see, this is how Bitcoin, for example, is able to keep track of all these transactions since the genesis state. So it almost seems impossible, but it's based on algorithms that are very hard to disentangle. And non-predictability means the input isn't going to tell you anything about the output.

So Sam generated these examples in the last few days to try to be concrete. Here's the text. This is an example document that's going to be hashed. The quick brown fox jumped over the lazy dog. You put it in this standardized hash function and you get this ciphertext. But suppose you slipped and there's a little typo in this word over, and you get-- you can scan this for a while and try to see some similarity in the ciphertext, but there is none, that's the point.

AUDIENCE: But the reason it's not invertible is because we don't know what this function is exactly doing as people as us, outsiders? Or why is it not invertible, right? Well, it's actually not invertible in the sense that there's many things that map to the same output. ROBERT TOWNSEND: I mean, you'll see some math momentarily. It's like basically private and public keys, and you can know a lot as the public keys, but the private key is randomly drawn, so unless you're lucky at guessing and you don't know the random key, then it's computationally almost impossible.

Here's an example of hashing an accounting statement as representative database, two people. They're always Bob and Alice, it seems, with their balances and their ID numbers, and that generates this-- and these are all of the same length. I mean, hashes can be longer than this, but this is illustrative. OK. So hashes are like a signature system, too, for messages and for documents, data sets. If you have the original data set stored away on a server, then you hash it up and state exactly how it was hashed, and it's public.

The hash version is public, but doesn't reveal the data. Now, a new person comes along who does have permission to look at the data, wants to make sure that the candidate file they're about to use with real data is actually the data file-- the original data file and it hasn't been corrupted or altered. So if the original data are assigned by this unique hash, then the candidate file can be hashe

原文超出正文长度上限，此处截断——上游还有内容，完整版见上方「原文 ↗」。