[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:02.00,Default,,0000,0000,0000,,The next thing I'm going to talk about is an idea that Ralph Merkle
Dialogue: 0,0:00:02.00,0:00:05.00,Default,,0000,0000,0000,,came up with in 1974.
Dialogue: 0,0:00:05.00,0:00:08.00,Default,,0000,0000,0000,,It's not a practical idea at all, but it's a really clever idea,
Dialogue: 0,0:00:08.00,0:00:11.00,Default,,0000,0000,0000,,and I think it's a fun thing to talk about before we get into
Dialogue: 0,0:00:11.00,0:00:14.00,Default,,0000,0000,0000,,the more realistic solutions that are used today.
Dialogue: 0,0:00:14.00,0:00:17.00,Default,,0000,0000,0000,,The idea behind Merkle's puzzles is that you have the 2 parties
Dialogue: 0,0:00:17.00,0:00:21.00,Default,,0000,0000,0000,,that want to share a key, and we'll call them Alice and Bob, as usual.
Dialogue: 0,0:00:21.00,0:00:24.00,Default,,0000,0000,0000,,First they have to agree on some parameters.
Dialogue: 0,0:00:24.00,0:00:26.00,Default,,0000,0000,0000,,They agree on an encryption function.
Dialogue: 0,0:00:26.00,0:00:31.00,Default,,0000,0000,0000,,They agree on security parameters s, n, N.
Dialogue: 0,0:00:31.00,0:00:35.00,Default,,0000,0000,0000,,The basic idea is Alice is going to create many puzzles,
Dialogue: 0,0:00:35.00,0:00:39.00,Default,,0000,0000,0000,,and then Bob will randomly pick one of the puzzles to solve,
Dialogue: 0,0:00:39.00,0:00:44.00,Default,,0000,0000,0000,,and part of solving that puzzle will give Bob the number of the puzzle and a secret.
Dialogue: 0,0:00:44.00,0:00:47.00,Default,,0000,0000,0000,,And what he'll send back to Alice is the number of the puzzle,
Dialogue: 0,0:00:47.00,0:00:49.00,Default,,0000,0000,0000,,and Alice will know the corresponding secret,
Dialogue: 0,0:00:49.00,0:00:51.00,Default,,0000,0000,0000,,and they'll use that as the key.
Dialogue: 0,0:00:51.00,0:00:54.00,Default,,0000,0000,0000,,Let me go through this in a little more detail,
Dialogue: 0,0:00:54.00,0:00:57.00,Default,,0000,0000,0000,,but that's the high level idea, and the reason that this gives you
Dialogue: 0,0:00:57.00,0:01:01.00,Default,,0000,0000,0000,,a way to establish a key is because Bob is randomly picking one puzzle to solve,
Dialogue: 0,0:01:01.00,0:01:05.00,Default,,0000,0000,0000,,whereas an attacker would have to solve many puzzles
Dialogue: 0,0:01:05.00,0:01:08.00,Default,,0000,0000,0000,,before they could get the one that Bob actually solved.
Dialogue: 0,0:01:08.00,0:01:10.00,Default,,0000,0000,0000,,Here's how the steps work in a little more detail.
Dialogue: 0,0:01:10.00,0:01:15.00,Default,,0000,0000,0000,,In order to create puzzles--so Alice creates a list of N secrets.
Dialogue: 0,0:01:15.00,0:01:18.00,Default,,0000,0000,0000,,Each one of these is a random number s bytes long.
Dialogue: 0,0:01:18.00,0:01:21.00,Default,,0000,0000,0000,,Then she creates a set of messages, also N messages,
Dialogue: 0,0:01:21.00,0:01:27.00,Default,,0000,0000,0000,,and each message will be encrypted using the encryption function that they agreed on
Dialogue: 0,0:01:27.00,0:01:30.00,Default,,0000,0000,0000,,using a key that's the corresponding secret concatenated
Dialogue: 0,0:01:30.00,0:01:34.00,Default,,0000,0000,0000,,with enough zeros to make the appropriate key length.
Dialogue: 0,0:01:34.00,0:01:40.00,Default,,0000,0000,0000,,If this was a 128-byte AES key, the secret size might be, say, 40 bytes,
Dialogue: 0,0:01:40.00,0:01:43.00,Default,,0000,0000,0000,,and then we would add zeros to fill out the rest of the key.
Dialogue: 0,0:01:43.00,0:01:46.00,Default,,0000,0000,0000,,And then what we'll encrypt using that key
Dialogue: 0,0:01:46.00,0:01:50.00,Default,,0000,0000,0000,,is a message that gives the identity of the puzzle,
Dialogue: 0,0:01:50.00,0:01:55.00,Default,,0000,0000,0000,,which will be that index, and the message will give the identity of the puzzle,
Dialogue: 0,0:01:55.00,0:01:59.00,Default,,0000,0000,0000,,and we'll include a string before it so it's clear that that's the right message.
Dialogue: 0,0:01:59.00,0:02:02.00,Default,,0000,0000,0000,,If we just included a number, if there were enough numbers
Dialogue: 0,0:02:02.00,0:02:05.00,Default,,0000,0000,0000,,we might accidentally decrypt one to that.
Dialogue: 0,0:02:05.00,0:02:08.00,Default,,0000,0000,0000,,That's what we encode for each message here.
Dialogue: 0,0:02:08.00,0:02:11.00,Default,,0000,0000,0000,,After this, Alice shuffles the messages,
Dialogue: 0,0:02:11.00,0:02:15.00,Default,,0000,0000,0000,,and then she sends all N messages to Bob.
Dialogue: 0,0:02:15.00,0:02:19.00,Default,,0000,0000,0000,,Bob randomly picks one of those, then does a brute-force key search
Dialogue: 0,0:02:19.00,0:02:22.00,Default,,0000,0000,0000,,where Bob is trying to decrypt using a guess key
Dialogue: 0,0:02:22.00,0:02:25.00,Default,,0000,0000,0000,,concatenated with N - s zeros,
Dialogue: 0,0:02:25.00,0:02:29.00,Default,,0000,0000,0000,,the message that Bob randomly selected from those puzzles.
Dialogue: 0,0:02:29.00,0:02:32.00,Default,,0000,0000,0000,,Eventually he's going to find one of these decrypts
Dialogue: 0,0:02:32.00,0:02:34.00,Default,,0000,0000,0000,,to puzzle followed by a number.
Dialogue: 0,0:02:34.00,0:02:37.00,Default,,0000,0000,0000,,At this point, Bob knows the guess, so he knows the secret
Dialogue: 0,0:02:37.00,0:02:40.00,Default,,0000,0000,0000,,that was used for that, and he knows the puzzle number.
Dialogue: 0,0:02:40.00,0:02:42.00,Default,,0000,0000,0000,,If we wanted a larger key, which we probably do,
Dialogue: 0,0:02:42.00,0:02:46.00,Default,,0000,0000,0000,,what we should include in the puzzle instead of just the i
Dialogue: 0,0:02:46.00,0:02:50.00,Default,,0000,0000,0000,,we should include a key, and this means the key can be of any length.
Dialogue: 0,0:02:50.00,0:02:54.00,Default,,0000,0000,0000,,This would be some new random key associated with that puzzle.
Dialogue: 0,0:02:54.00,0:02:58.00,Default,,0000,0000,0000,,Alice would keep track of those keys, and so for each puzzle,
Dialogue: 0,0:02:58.00,0:03:02.00,Default,,0000,0000,0000,,when Bob decrypts it, he acquires both the puzzle number and the key number,
Dialogue: 0,0:03:02.00,0:03:04.00,Default,,0000,0000,0000,,sends the number of the puzzle back to Alice.
Dialogue: 0,0:03:04.00,0:03:08.00,Default,,0000,0000,0000,,Alice can look up in her keys and figure out which key
Dialogue: 0,0:03:08.00,0:03:10.00,Default,,0000,0000,0000,,was the one in the puzzle Bob decrypted.
Dialogue: 0,0:03:10.00,0:03:14.00,Default,,0000,0000,0000,,Assuming encryption and the random number generation work perfectly,
Dialogue: 0,0:03:14.00,0:03:19.00,Default,,0000,0000,0000,,the question is how much more work does an eavesdropper have to do than Bob has to do?
Dialogue: 0,0:03:19.00,0:03:22.00,Default,,0000,0000,0000,,And an eavesdropper hears all the messages between Alice and Bob,
Dialogue: 0,0:03:22.00,0:03:25.00,Default,,0000,0000,0000,,wants to determine the key that they'll use to communicate.
Dialogue: 0,0:03:25.00,0:03:27.00,Default,,0000,0000,0000,,Here are the choices.
Dialogue: 0,0:03:27.00,0:03:29.00,Default,,0000,0000,0000,,It's impossible for the attacker to find the key.
Dialogue: 0,0:03:29.00,0:03:34.00,Default,,0000,0000,0000,,The attacker would need to use N times as much work as Bob to determine the key.
Dialogue: 0,0:03:34.00,0:03:38.00,Default,,0000,0000,0000,,The attacker would expect to need N/2 times as much work as Bob,
Dialogue: 0,0:03:38.00,0:03:43.00,Default,,0000,0000,0000,,or the attacker would be expected to need twice as much work as Bob.
Dialogue: 0,0:03:43.00,0:03:49.00,Default,,0000,0000,0000,,And the value of N is the number of puzzles that Alice creates and sends to Bob.