In this segment,

we're gonna look at another form of encryption called tweakable encryption.

I'm gonna modify tweakable encryption using this encryption as an application

and we'll see this encryption is yet another application for

deterministic encryption.

So the disk encryption problem is that we wanna encrypt sectors on disks.

Say each sector is four kilobytes long.

And the problem is that there's no space to expand.

In other words, if the sector size is four kilobytes,

the cipher text size also has to exactly four kilobytes because there's nowhere to

write the extra bits if the cipher text was bigger than the plain text.

And so our goal is basically to build a non-expanded encryption

where the cipher text size is identical, exactly equal to the plain text size.

So what does it mean that encryption can't expand?

Well, technically, we're saying basically the message space is equal to the cipher

text space, so the message space would be four-kilobyte messages and

the cipher text space would be also four-kilobyte messages.

In this case, clearly we have to use deterministic encryption, because if

encryption was randomized, there would be no place to store the randomness.

And similarly, we have no room for

integrity because we can't expand a ciphertext and add any integrity bits.

So the most we can achieve is deterministic CPA security and

that's gonna be our goal.

Now it turns out, there's a really simple lemma to prove that basically says,

that if you give me a deterministically CPA secure cipher,

where the message space is equal to the cipher text base, so no expansion.

Then in fact, the cipher is a PRP.

So really all we're saying here is if we want no expansion at all,

our only option for

encrypting is what we called construction number two in the previous segment.

Namely, we have to encrypt using a PRP.

So let's look at how we might encrypt using a PRP while we take our disk and

we break it into sectors.

Now if we encrypted every sector using a pure P under the same key,

we could have run into our standard problem with a truistic encryption,

namely if sector one and sector three happen to have the same plain text,

then the encrypted sector 1 would be equal to the encrypted sector 3 and

the attacker would learn that the corresponding plain texts are the same.

Now this actually is a real problem.

For example, if some of your sectors are empty, you know they're all set to zero,

then in fact, the crypted sectors would be identical, and as a result, the attacker

would know exactly which sectors on your disk are empty and which sectors are not.

So, this is actually quite problematic and the question is, can we do any better?

And so the answer is yes.

And the first idea that comes to mind is, well, why don't we use a different key for

every sector?

So you can see sector number one gets encrypted with key one,

sector number two gets encrypted with key two and so on and so forth.

So now even if the content of sector number one is equal to sector number three

the cipher texts of sector 1 and

sector 3 will be different because they are encrypted under different keys.

So this actually avoids the leakage that we talked about before, although I do want

to point out there is still a little bit of leakage with this mode, for

example if the user happened to change 1 bit in sector 1.

And then that sector gets encrypted into a different cyphodext so this will be

garbled all completely because this is a pseudorandom permutation.

The sector will be even if one bit of the plaint exchanges,

the sector will just be mapped to a completely new random output.

However if the user then undoes the change and reverts back to the original sector,

then the encrypted sector will revert back to its original state.

And the attacker can tell that a change was made and then reverted, so

there is still a little bit of information leakage but that type of information

leakage is really nothing we can do without really sacrificing performance so

we are just going to ignore that and deem that acceptable.

So the next question is now you realize our discs are actually getting pretty big

and there are lots of sectors so this would mean we are generating lots and

lots of keys here.

But of course we don't have to store all these keys,

we can simply generate these keys using a pseudorandom function.

So the way this would work is we would have a master key which we would call K,

and then the sector number which I'm going to denote by T is going to be

encrypted using the master key, and the result of that encryption would be

the particular sector key which I'll denote by k sub t.

Now the reason this is secure is again because the PRF is indistinguishable from

a random function which means that basically if we apply a random function

to the sector numbers one, two, three, four up to L they basically get mapped to

completely random elements in the key space and

as a result we're encrypting every sector using a new random independent.