In this segment, I want to tell you about another form of encryption, called format

preserving encryption. This is again something that comes up in practice quite

often, especially when it comes to encrypting credit card numbers. And, so,

let's see how it works. Remember that a typical credit card number is sixteen

digits, broken into four blocks of four digits each. You've probably heard before

that the first six digits are what's called the BIN number, which represent the

issuer ID. For example, all credit cards issued by VISA always start with the digit

four; all credit cards issued by MasterCard start with digits 51 to 55, and

so on and so forth. The next nine digits are actually the account number that is

specific to the, to the particular customer and the last digit is a check sum

that's computed from the previous fifteen digits. So there are about 20,000 BIN

numbers and so if you do the calculation it turns out there are about 2 to the 42

possible credit card numbers which corresponds to about 42 bits of

information that you need to encode if you want to represent a credit card number

compactly. Now the problem is this. Suppose we wanted to encrypt credit card

numbers, so that when the user swipes the credit card number at the point of sale

terminal, namely at the, you know, the merchant's cash register. The cash

register, this is called a point of sale terminal, goes ahead and encrypts the

credit card number using a key k and it's encrypted all the way until it goes

to the acquiring bank or maybe even beyond that, maybe even all the way when it goes

to Visa. Now, the problem is that these credit card numbers actually pass through

many, many, many processing points. All of them expect to get basically something

that looks like a credit card number as a result. So if we simply wanted to encrypt

something at the end point, at one end point, and decrypt it at the other end

point, it's actually not that easy because if all we did was encrypt it using AES,

even if we just used deterministic AES, the output of the encrypted credit card

number would be 128 bit block. Sixteen bytes that would be, that would need to be

sent from one system to the next, until it reaches its destination. But each one of

these processors, then, would have to be changed, because they're all expecting to

get credit card numbers. And so the question is, can we encrypt at the cash

register, such that the resulting encryption itself looks like a credit card

number. And as a result, none of these intermediate systems would have to be

changed. Only the endpoints would have to be changed. And in doing so we would

actually obtain end-to-end encryption without actually having to change a lot of

software along the way. So the question then is, again, can we have this mechanism

called format preserving encryption, where encrypting a credit card itself produces

something that looks like a credit card? So that's our goal. The encrypted credit

card number should look like a regular valid credit card number. So this is the

goal of format preserving encryption. More abstractly what it is we're trying to do,

is basically build a pseudo random permutation on the set zero to S minus one

for any given S. So for the set of credit card numbers, S would be roughly, you

know, two to the 42. In fact, it's gonna be, not exactly two to the 42. It's gonna

be some funny numbers that's around two to the 42. And our goal is to build a PRP

that acts exactly on the interval, zero to S minus one. And what we're given as input

is some PRF, say, something like AES, that acts on much larger blocks, say, acts on

sixteen byte blocks. So we're trying to, in some sense, shrink the domain of the

PRF to make it fit the data that we're given. And the question is basically how

to do that. Well, once we have such a construction we can easily use it to

encrypt credit card numbers. What we would do is we would take the, a given credit

card number. We would encode it such that now it's represented as a number between

zero and the total number of credit card numbers. Then we would apply our PRP so we

would encrypt this credit card number, you know, using construction number two from

the deterministic encryption segment. And then we would map the final number back to

be a regular, to look like val--, regular, valid credit card number and then send

this along the way. So this is, this is again non expanding encryption. The

best we can do, as we said before is to encrypt using a PRP except again the

technical challenge is we need a PRP that acts on this particular funny looking set

from zero to S-1 for this prespecified value of S. So my goal is to show you how

to construct this and once we see how to do it, you will also know how to encrypt

credit card number so that the resulting cipher text is itself a credit card

number. So the construction works in two steps. The first thing we do is we shrink

our PRF from the set {0,1} to the n, say {0,1} to the 128 in the case of AES,

to {0,1} to the t where t is the closest power of two to the value S.