Now that we understand what is deterministic encryption, let's see some constructions that provide security against deterministic chosen plaintext attacks. So, first let me remind you that the deterministic encryption is needed, for example, when encrypting a data base index and later we wanna look up records using the encrypted index. Because the encryption is deterministic we're guaranteed that when we do the lookup the encrypted index is gonna be identical to the encrypted index that was sent to the database when the record was written to the database. And so, this deterministic encryption allows us a very simple or fast way to do lookups based on encrypted indices. The problem was that we said the deterministic encryption can't possibility be secure against a general chosen plaintext attack because if the attacker sees two cipher texts that are equal it learns that the underlying encrypted messages are the same. So, then we defined this concept of deterministic chosen plain text security which means that we have security as long as the encryptor never encrypts the same message more than once using a given key. In particular, this key, message pair is only used once, for every encryption, either the key changes, or the message changes. And then as I said, formally we define this CPA, deterministic CPA security game, and our goal in this segment is to actually give constructions that are deterministic CPA secure. So the first construction we're gonna look at is what's called SIV, synthetic IV's. And the way this construction works is as follows. Imagine we have a general CPA secure encryption system. So here's the key and here's the message and we are gonna denote by R the randomness that's used by the encryption algorithm. Remember that a CPA secure system that doesn't use nonsense has to be randomized and so we're explicitly gonna write down this variable R to denote the random string that's used by the encryption algorithm as it's doing the encryption. For example if we're using randomized counter mode, r would be the random IV that's used by randomized counter mode. And of course C is the resulting ciphertext. Now, in addition, we're also going to need a pseudo random function, f, that what it does, is it takes our arbitrary messages in the message space and outputs a strings, R, that can be used as randomness for the CPA secure encryption scheme. So, the little, r, over here is actually a member of the big R set. Okay. And we're going to assume this is a, f is a pseudo random function that maps messages to random strings. Now the way SIV works is as follows. It's going to use two keys K1 and K2 to encrypt the message M. And what it does, is the first thing is going to apply the pseudo random function f to the message M to derive randomness for the CPA secure encryption scheme E. And then it's going to encrypt the message M using the randomness that it just derived. This is going to give us a cipher text C and then it's going to output this cipher text C Okay. So that's how this SIV mode works. Basically it first derives the randomness from the message being encrypted, and then it uses this derived randomness to actually encrypt the message to obtain the cipher text. Now I'd like to point out for example, if the encryption scheme E happened to be randomized counter mode. Then the randomness R would just be the random IV which would actually be output along with the cipher text. So this means that the cipher text is a little bit longer than the plain text. But the point here isn't to generate a short cipher text. Rather the point here is to make sure that the encryption scheme is deterministic, so if we encrypt the same message multiple times, every time we should obtain the same cipher text. And indeed every time, we'll obtain the same randomness, R, and as a result, every time we'll obtain the same cipher text C. So it's fairly easy to show that this encryption scheme really is semantically secure under the deterministic chosen plaintext attack. The reason that's so is because we apply the pseudo random function F to distinct messages. Well if we apply F to distinct messages then the random string that F generates is going to look like just truly random strings. A different random string for every message. And as a result the CPA secure encryption scheme E is always applied using truly random strings. And that's exactly the situation where it is CPA secure. So because these R's are just random indistinguishable from brand new strings, the resulting system is in fact gonna be CPA secure. So this is just the intuition for why this works and it's actually fairly straightforward to actually formalize this into a complete proof. Now, I should emphasize that this is actually well suited for messages that are more than one AES block. In fact, for short messages, we're gonna see a slightly different encryption scheme that's actually better suited for these short messages. Okay, now the really cool thing about SIV is that, actually, we get cipher text integrity for free. In fact we don't have to use a special Mac if we want to add integrity. In a sense SIV already has a built in integrity mechanism. And let me explain what I mean by that. First of all, our goal was to build what's called deterministic authenticated encryption. Dae. Deterministic Authenticated Encryption. Which basically means that deterministic CPA security and cipher text integrity. Remember cipher text integrity means that the attacker gets to ask for the encryptions of messages of his choice and then he shouldn't be able to produce another cipher text that decrypts to a valid message. Okay, so I want to claim that in fact SIV automatically gives a cipher text integrity without the need for an embedded MAC or anything else. So let's see why. In particular, let's look at a special case of SIV when the underlying encryption scheme is randomized counter mode. Okay, so we'll call this SIV-CTR again to denote SIV where we're using randomized counter mode. Alright. So let me remind you again how SIV works in this case. Well, so we take our message, here, we take our message, and then we apply a PRF to it. And that derives an IV. And then that IV is going to be used to encrypt the message using randomized counter mode. Okay. So in particular, we're gonna use this PRF FTCRr for F counter, for randomized counter mode and essentially evaluate this FCTR at Iv, IV plus one up to IV plus L. And, then, we had sorta that with the message. And that gives us the final ciphertext. Okay. So, this is SIV with a randomized counter mode. Now, let's see how decryption is gonna work. And during decryption we're gonna add one more check, and that's going to provide ciphertext integrity. So let's see how decryption is going to work. So here we have our input cipher text that contains the IV and the cipher text. Well, the first thing we're going to do is we're going to decrypt the cipher text using the given IV, and that will give us candidate plain text. Now we're gonna reapply the PRF F from the definition of SIV to this message. Now if a message is valid, we should be getting the same IV that the [adversary??] supplied as part of the cipher text. If we get a different IV, then we know that this message is not a valid message and we simply reject the cipher text. So this is really cute. It's a very simple kinda built in check to make sure that the cipher text is valid, right. We simply check that after decryption if we re-derive the IV we would actually get the correct IV. And if not we reject the message. And I claim that this simple check during decryption is enough to [actually??] provide ciphertext integrity. And therefore, deterministic authenticated encryption. So I'll state this in a simple theorem. Basically to say, that if F is a secure PRF, and in counter mode that's derived from FCTR is CPA secure, then the result is in fact a deterministic authenticated encryption system. Now the proof for this is not too difficult. In two sentences, let me just show you the rough intuition for why this is true. So, all we have to argue is just cipher text integrity. So we already argued before that the system has deterministic CPA security, all we have to argue is just cipher text integrity. So to argue that the system has cipher text integrity, let's think again how the cipher text integrity game works. Adversary asks for the encryption of a bunch of messages of his choice. And he gets the resulting cipher text. Then, his goal is to produce a new valid cipher text. Well, if that valid cipher text upon decryption, decrypts to some completely new message. Then when we plug this new message into the PRF F, we're just going to get some random IV and it's very unlikely to hit the IV that the adversary supplied in the cipher text that he output. So therefore that says that when the advisory outputs his forged cipher text, the message in that forged cipher text basically should be equal to one of the messages in his chosen message queries. Otherwise, again the IV that you get is simply not gonna be equal to the IV in the forged safe index with very high probability. But if the message is equal to one of the messages that the adversary queried us on, well then, the cipher text that we're gonna get is also gonna be equal to one of the cipher texts that we supplied to the adversary. But then his forgery is simply one of the cipher texts that we gave to him. And therefore, this is not a valid forgery. He has to give us a new cipher text to win the cipher text integrity game. But he gave us one of our old cipher texts. So, this is the rough intuition. I hope, I kinda went through it quickly. I hope it kinda makes sense. If it doesn't then it's not the end of the world. I'm gonna reference the paper that describes SIV at the end of the module. And if you wanna see this in more detail you can read and take a look inside of that paper. But, regardless, this is a very cute idea that I wanted to show you where kinda the fact that we derive the randomness for deterministic counter mode using a PRF. Also, gives us an integrity check when we actually do the decryption. Okay. So this SIV is a good mode for doing deterministic encryption when you need to, particularly if the messages are long. If the messages are very short, say they're less than sixteen bytes, in fact there's a better way to do it, and that's the method that I wanna show you now. So the second construction is actually trivial. All we're gonna do is we're gonna use a PRP directly. So here's what we do. So suppose (E, D) is a secure PRP. So E will encrypt, and D will decrypt. And I claim that if we use E directly, that already gives us deterministic CPA security. So let me show you very quickly why. So suppose F is a truly random invertible function from X to X. Okay. So remember a PRP is indistinguishable from a truly random invertible function, so let's pretend that we actually do have a truly random invertible function. Now in experiment zero what the attacker is gonna see while he submits a bunch of messages, you know the messages on the left. And what he's gonna see is basically the evaluation of f on the messages on the left that he supplied. Well, in the deterministic CPA game, all these messages are distinct, and so all he's gonna get back are just q distinct random values in X. That's all he sees. Yes, there's Q distinct random values in X. Now let's think about experiment one. In experiment one, he gets to see the encryptions of messages on the right, okay, the M11 to MQ1. Well, again, all these messages are all distinct so all he gets to see are just Q random distinct values in X. Well these two distributions, in experiment zero and experiment one, therefore are identical. Basically, in both cases what he gets to see are just Q distinct random values in X. And as a result, he can't distinguish experiment zero from experiment one. And since he can't do this for a truly random function, he also can't do this for the PRP. Ok, so that explains why directly encrypting with a PRP already gives us a CPA secure system very, very, very simple to use. That says that if all we wanna do is encrypt short messages, say, less than sixteen bytes, then all we need to do is to directly encrypt them using AES and the result will, in fact, be deterministic CPA secure. So, if your indices are less than sixteen bytes directly using AES is a fine thing to do. Notice however, that's not gonna provide any integrity. And we're gonna see how to add integrity in just a minute. But the question for you is, what do we do if we have longer than sixteen byte messages? Well, one option is to use SIV. But what if we actually wanted to use this construction too. It's actually an interesting question. Can we construct PRP's that have message spaces that are bigger than just sixteen bytes? If you remember in the past we constructed PRFs on that had large message spaces from PRFs that had small message spaces. Here, we're going to construct PRPs with large message spaces from PRFs that have small message spaces. So, here's how we do it. So suppose E D is a secure PRP that operates on N bit blocks. There's a standard mode called EME that actually will construct a PRP that operates on capital N bit blocks, where capital N is much, much bigger than little n. So this would allow us to do deterministic encryption on much larger messages than just sixteen bytes. In fact it could be as long as we want. So let's see how EME works. It's a bit daunting at first but it's not a difficult construction. So, let's see how it works. So, EME uses two keys, K and L, and in fact in the real EME L is derived from K. But for our purposes, let's just pretend that K and L are two distinct keys. The first thing we do, is we take our message X and we break it up into blocks. And then we XOR each block with a certain padding function, okay? So we use the secret key L to derive a pad using this, you know function P that I'm not gonna explain here. We derive a different pad for each one of the blocks and we XOR that pad. Into the block. The next thing we do is we apply the PRP E using the Key K, to each of these blocks, and we're gonna call these outputs PP0, PP1, and PP2. The next thing we do is we XOR all these ppp's together and we call the result MP. Actually this XOR doesn't need to be there. We call the result of the XOR MP. The next thing we do we XOR all these ppp's together and we call the result MP. We encrypt this MP using E and the key K. We call the outputs of this encryption MC. Okay. So then we use the XOR MP and MC and this gives us another PM, which we use to derive one more pad, and then we XOR this output of this pad with all the PPP's to get these CCC's, [laugh], and then we XOR all these C C C's together that gives us a value of C C C zero, which we then encrypt one more time with all these E's, we do one more padding with all these P's and that actually finally gives us the output of EME. Okay, so like I said, this may look a little daunting, but in fact there's a theorem that shows that if the underlying block cipher E is a secure PRP, then in fact. This construction, EME, is a secure PRP on this larger block, you know, zero, one to the capital N. The nice thing about this construction is you notice that it's very parallel and actually that's why it's a little complicated. Counted every block. It's encrypted in parallel, so if you have a multi-core processor, you can use all your cores to encrypt all the blocks at the same time and then there would be one kind of sequential step to compute this, check sum of, all the outputs and then one more parallel around to encrypt one more time and then finally you get the outputs. These function Ps, by the way, that generate the pads, are very, very simple functions. They take constant time so we're just going to ignore them in terms of performance. So the bottom line is performance here. You notice it requires two applications of E per input block. And it turns out this can actually be slower than SIV, if SIV is implemented properly with a very fast PRF to derive the randomness. Then in fact SIV can be twice as fast, as this particular mode of operation. For this reason I say that the PRP construction is very good for short messages, whereas SIV is good if you h, if you want to encrypt longer messages in a deterministic fashion. But now what if we wanted to add integrity to this PRP-based mechanism? So, can we achieve deterministic authenticated encryption using the PRP mechanism where we directly encrypt the message using a PRP? And it turns out the answer is yes and it's actually again, a very simple encryption scheme that you should know about. Basically what we're going to do is we're going to take our message and we're going to append a bunch of zeros to this message and then we're going to apply the PRP and that's it. And that's going to give us the cipher text. Now, very, very simple. Just append zeros and encrypt using a PRP. When we decrypt, we're going to look at these least significant bits of the resulting plain text and if they're not equal to zero, we're just going to reject the cipher text. And if they are equal to zero, we're going to output the message as valid. Okay, so that's it, that's the whole system, very, very simple. Simply append zeroes during encryption, and then check that the zeroes are there when you decrypt. And I claim that this very simple mechanism actually provides deterministic authenticated encryption, assuming, of course, that you've appended enough zeroes. And in particular, if you append N zeroes, you need one over two to the N to be negligible. And if so, then, in fact, this direct PRP based encryption, in fact, provides deterministic authenticated encryption. So let me see why. Well, we already argued that the system is CPA secure, so all we have to argue is that it provides cipher text integrity. And again, that's easy to see. Let's look at the cipher text game. So the adversary is gonna choose let's say a truly random permutation. So a truly random, invertible function, on the input space. In this case the input space is the message space and the N zero bits. Now what does the adversary get to do? Well he gets to submit q messages, and then he receives the encryption of those Q messages. Mainly he receives the PRP at his chosen points concatenated with N zeros. Okay, that's what it basically it means to query the CPA challenger. So in case of a random permutation, he simply gets to see, the value of this permutation at Q points of his choice, but only concatenated with N zeroes. And now, what's his goal in the cipher text integrity game? Well, his goal is to produce some new cipher text that's different from the cipher text that he was given, that's gonna decrypt properly. Well, what does it mean that it decrypts properly? It means that if, when we apply, Pi inverse To the cipher text C, it had better be the case that the N least significant bytes of C are all zeros. And the question is how likely is that to happen? Well, so let's think about this. So basically we have a truly random permutation and the adversary got to see the value of this permutation as Q points. How likely is he to produce a new point that, when inverted, happens to have N zeroes as the least significant bits? What we're doing here is basically we're evaluating the permutation Pi inverse at the point c. And since Pi inverse is a random permutation, how likely is it to have its n least significant bits be equal to zero? So it isn't hard to see that the answer is, is, at most, the probability's at most, one over two to the N. Because, again, basically, the permutation is gonna output a random element inside of, X times 0 1 to the N. And that element is gonna end with N zeroes, but basically with the probability one over two to the N. And as a result, the adversary wins the game with negligible probability, Because, this value is negligible. So that's the end of this segment. I wanted you to see these two very cute deterministic authenticated encryption schemes. The first one we called SIV, where I said you would use randomized counter mode and you just arrived at randomness for randomized counter mode from a PRF applied to the message. And the very cute idea here is that during decryption you can simply recompute the IV from the, from the decrypted message and verify that that IV is what's given to you in the cipher text. And that simple check is actually enough to guarantee authenticated encryption or rather deterministic authenticated encryption. So this mode is, is the way you would encrypt an index in a database if the index was large. If the index happens to be short, maybe say, its eight bytes if it's an 8-byte user ID, then you can directly use a PRP and the way you would do is, is you would append zeros to those eight bytes. And then those zeros will be used as an integrity check when you decrypt and again if you append, are able to append enough zeros, then in fact this also provides deterministic authenticated encryption. As an aside, I showed you that there's a way to build the wide block PRP from a narrow PRP and that particular mode of operation is called EME. So we're gonna refer EME actually in the next segment.
