Foundations of Cryptography Prof. Dr. Ashish Choudhury(Former) Infosys Foundation Career Development Chair ProfessorIndian Institute of Technology-BangaloreLecture-18Theoretical Constructions of Block CiphersHello everyone, welcome to lecture 17. In this lecture we will see theoretical constructions of block ciphers. Specifically the roadmap for this lecture is as follows.(Refer Slide Time: 00:37)So, till last lecture we have seen that if we have a pseudo random function, then we can design candidate CPA secure schemes using most of operations of pseudo random functions. But now the question is how do we actually go about designing the pseudo random function. And it turns out that there are 2 ways of designing pseudo random functions. The first phase, the first class of the constructions are the provably secure constructions, which we are going to discuss here. And they are considered to be theoretical constructions because that is not the way we instantiate pseudo random functions in the real-world protocols. In the later lectures, we will see the practical constructions namely the constructions which we use in real world to instantiate pseudo random function. However, even though we do not use the so called theoretical instantiations of pseudo random functions, they are very fundamental, they are of fundamental importance in cryptography because mathematically here we show that the constructions that we are going to discuss they can be proved to be secure based on the assumption that one way function exists.That means we have now mathematical guarantees that the constructions that we are going to see in this lecture they are secure, whereas the so-called practical instantiations which we are going to say in the subsequent lectures, for those constructions we do not have any provable security guarantees that means there is no mathematical proof that indeed those construction satisfies the definitions of pseudo random function, pseudo random permutations and so on.It is only a belief or an assumption that ever since their discovery, no attacks or no shortcomings have been reported in those constructions. And that is why we believe that those constructions emulate the behavior of a pseudo random function, pseudo random permutations and so on. So now coming back to this lecture, the roadmap for this lecture is as follows: we will see how to construct provably secure pseudo random functions given provably secure pseudo random generators. Then we will see the constructions of provably secure pseudo random permutations from provably secure pseudo random function. And this construction is also called as Luby?Rackoff construction attributed to the name of their inventors. And then finally, we will see how to construct provably secure strong pseudo random permutations given provably secure pseudo random permutation.(Refer Slide Time: 02:59)So, let us do the first thing here. Namely, we will see how if you are given a provably secure pseudo random generator, we will see how to construct provably secure pseudo random permutation. And for the purpose of demonstration, I am assuming that I have a length doubling pseudo random generator . And this you can construct in a provably secure way from one-way function using the Goldreich-Levin construction and assuming that hard-core predicate exist.So, remember in one of our earlier lectures, we had seen provably secure constructions of pseudo random generator, where we first expand the output or the input of the pseudo random generator by 1 bit using hard-core predicate and then we do serial composition of that pseudo random generator polynomial number of times to expand the length of the pseudo random generator by any polynomial amount.So, I assume that I have such a pseudo random generator, namely a length doubling pseudo random generator and my goal is basically to construct PRF: . The construction is called a tree construction. And the reason it is called a tree construction is that basically the way we define the keyed function Fk is that we construct a complete binary tree of depth consisting of 2nleaf nodeswhere each leaf node is going to consist of pseudo random string of length 2n bits determined by the value of the underlying key k. Now, the reason we are going to construct a complete binary tree of depth n is that we are going to have 2nleaves and each leaf node is basically a value of the function Fk. And this matches with our semantic of the keyed function Fk that we are interested to construct because the block size of my underlying keyed function which I want to construct is n bits. That means, my function Fk(i) namely the range of this i: 0 ≤ i ≤ 2n - 1. So there are 2ncandidate inputs for this function. That is why I am interested to design a tree consisting of 2nnodes. And ith value or the value of the keyed function Fk on the input i will be basically the pseudo random string which Iam going to store at the ith leaf node in this tree.So, the entire thing boils down to how exactly this tree is going to be defined as a function of my underlying keyed k. So, for the purpose of demonstration, I assume that I have pseudo random generator . And using that I have to design a keyed pseudo random function, . The construction is as follows: so this is your complete binary tree of 8 nodes. So this is your 0th leaf. This is your first leaf and this like this, this is your 7th leaf. And this will denote the strings that we are going to store in each of these respective leaf nodes will denote the value of the function F which we are going to define at their respective inputs. So now let us see what exactly will be the bit strings which are going to be stored in each of this internal nodes and the leaf nodes.So to begin with at the root of the tree, we are going to store the value k0k1 which is a bit string of length 6 bits, and which is generated by actually invoking the pseudo random generator on the key k. So, remember k is basically the key of the pseudo random function which I am interested to design, but now that key I am using as the seed for the pseudo random generator. And since my pseudo random generator expands the seed and gives me an output which is twice the size of the input, I will obtain a pseudo random output which I can parse as 2 blocks of 3 bits, 3 bits each. Now in my left-hand side note, which is that with the left child of this root, I basically stored the output of the pseudo random generator on the input k0. So remember, the string k0k1 is a string of length 3 bits. So you have 3 bits here, you have 3 bits here, the first 3 bits part I am denoting as k0, and I call the function G on that input to again obtain a new pseudo random string of length 6bits, which again, I can divide into 2 parts.And the right child of my root basically stores the value of the output of the pseudo random generator on the string k1, which will now give me another pseudo random string of lengths 6bits which I can parse as 2 chunks of 3 bits, 3 bits each. And then I repeat this process at the first layer of this tree, that means this node will now have the outcome of the pseudo random generator on the 3 bits k00 as the input.And this note will have the output of the pseudo random generator on the seed k01. And again, I obtain an output of 6 bits and so on. So that is the way the internal notes are filled. And similarly I filled the leaf notes also using the same logic to. How exactly I am going to output Fk(i)? So imagine, this whole tree is basically the definition of Fk. Now, I have to define what exactly will be the output of this tree on my input i.So remember, the keyed function F takes 2 inputs, the key input and the actual block input. So with respect to the key input I have defined a tree to be like this. Now I have to define how I take the output of this tree for the input i. So imagine for instance, I want to define or compute the value of this so called function Fk at the input 3. So 3 in binary can be written as 011. And basically, the idea is now I have to just pass this tree based on the binary representation of 3.So, I pass the first bit here which is 0, if it is 0, the rule is I go to the left of my current node, so, I start exploring from the root first bit is 0 I go to the left note, the next bit in the binary representation of 3 is 1. So, from my current note, I go to the right and the last bit in the binary representation of 3s are 1. So, that means from my current note, I go to the right and this will be the value of my function Fk at the input 3.That is the way I am going to define my function Fk. So, if you see on a very high level basically the way function Fk is defined it is nothing but polynomial number of sequential compositions of the truly random generator. I am basically composing the pseudo random generator G polynomial number of times depending upon the binary representation of my input i. In this case the binary representation was 011.So, I am basically invoking the function G three times in sequence one after the other where the outcome of the previous invocation of G is serving as the input for the next invocation in a specific way. Depending upon the binary representation of my input i, that is the way you can internally interpret the execution or the construction of this keyed function Fk.(Refer Slide Time: 10:49)Now, you might be wondering that whether this construction is efficient or not, because the size of the tree is exponentially large here. It consists of 2n number of nodes and where n is the security parameter. So that means if I am defining the function Fk like this, then one might feel that both sender and the receiver have to maintain this tree because once they know the value of the k they have to construct the tree like that.Because they do not know well in advance what is the value of the i that they are going to use it could be end up with any of the leaf nodes. So, had they have the whole tree with them in advance, but storing the whole tree will require them exponential amount of computation. So, intuitively, this construction might look like to be an inefficient construction, but it turns out that the entire tree not be computed and stored to compute the value of discrete function on the input i.Because depending upon the requirement, that means depending upon the value of i, I can compute the actual part that I need to follow in this tree by just invoking my underlying pseudo random generator n number of times. For instance, if I want to compute the value of the function Fk(i = 3), what I basically need is just 3 invocations of the PRG. That is all. I do not need the remaining invocations of the PRG.In the same way suppose later I am interested in computing the value of say Fk(4) therefore, in the binary representation is 100, then I do not need the whole tree. I need only this node, namely this invocations of the PRG, followed by this invocation of the PRG, followed by this invocation of the PRG. That means each value of Fk(i) can be just computed by executing polynomial number of instances of the underlying pseudo random generator. That is why this construction is computationally efficient. It does not demand exponential amount of computation. Now, the big question is this tree construction, or this way of defining the keyed function Fk is indeed going to give me a secure PRG. The answer is yes. Because intuitively what is Fk(i), what is the way I have computed Fk(i). Fk(i) you can interpret as a polynomial number of sequential compositions of PRG.Remember, when we were discussing pseudo random generator earlier, we had provedrigorously that polynomial number of sequential composition of PRG also gives you a pseudo random generator namely that output will be pseudo random and it will be indistinguishable from the outcome of a corresponding truly random generator. So, in that sense, this way of defining the function Fk based on a complete binary tree is indeed going to define a pseudo random function. But now, if I want to formalize this intuition into a rigorous proof, then there are a lot of subtleties which are involved here.(Refer Slide Time: 13:52)So the actual proof is indeed suttle and it requires lot of advanced technicalities. So, due to the interest of time and since the proof is really out of scope of this course, I will avoid the full formal details of the proof. But if you are really interested to see the complete proof, you can see the proof available in the book by Claude Shannon but let me discuss the overall proof idea.So, as I said the value of the Fk(i) is nothing but polynomial number of invocations of the pseudo random generator. So, my goal is basically to show that, if an adversary interacts with the keyedfunction Fk by asking polynomial number of queries where it does not know the value of k, it knows the structure of the tree, but it does not know the value of the k and hence, it does not know what are the pseudo random streams which are stored in the individual nodes.So, imagine if I have an adversary which is interacting with Fk(i) or a function Fk polynomial number of times, my goal is to show that it should not be able to distinguish the behavior of the tree construction from the behavior of a truly random function, but I cannot directly reduce that indistinguishability to the security of the underlying security of the pseudo random generator, because there are polynomial number of invocations of the pseudo random generator which are involved. So, what basically we required here is the hybrid argument.(Refer Slide Time: 15:19)So, let us see the security of the tree construction basically, we have an overview of the proof idea here. And for the demonstration of the proof idea, I take the case where I am constructing a pseudo random function, this is designed using a pseudo random generator .So, as per the tree construction that we have discussed just now, this is how the function Fk will look like and now, what I am going to do is I am going to compare this tree based construction of the function Fk with an alternate construction, where all the instances of the pseudo random generator G are going to be replaced by a truly random generator G’.So, what we are basically trying to construct here is we are trying to construct an unkeyed truly random function which takes an input of size 3 bits and it gives you an output of 6 bits. And on a very high level, the construction is exactly the same as the tree construction except that at each node all the invocations of your function G are replaced by G’. So, at root node we just call the function G’.And since the function G’ is a true random generator, it does not take any input. Just gives you some random 6 bit output that will be filled in this root. Then when we go to the left node again,we invoke the function G’, which will give you another 6 bit, truly random string. And like that, you can see that each node we are basically just invoking by function G’.And as a result, each of these nodes in this tree, which is constructed on the right-hand side part will have 2 random values of length 6 bits. So, that is how we have constructed the function f. So, now construction wise difference between the 2 functions that we have constructed is that if we want to the left-hand side k, it defines your function Fk. And if I want to compute the value of this function at some input, i say for instance, if I want to find the value of this function, on your left-hand side on the input is equal to say all 0s.Then basically I have to follow the path 000 and the value of my Fk(i) will be the value stored here. And we say other hand, if I want to compute the value of the function f that I have constructed in the right hand side on the input all 0s then again I have to follow as the I have to traverse along this tree as per the binary representation of my input i and wherever I stopped the leaf node, the value that is stored there, that will be considered as the value of the function f on the input i.So, in terms of the way I am computing and obtaining the output of the function, it remains the same in both the functions. What differs in the 2 functions is that the left-hand side tree, all the invocations are for pseudo random generator and the right-hand side tree all the invocations are for true random number generator. Now informally, the proof the idea behind the security of the tree construction that we have given is that if the underlying function G is a secure PRG, thenwhat we are going to show is in the proof that no polynomial time distinguisher should be able to distinguish apart the value of the function, Fk on the input i from the value of the function f on the input i.That means, it does not matter whether he has interacted with the tree construction on the left hand side polynomial number of time, or whether he has interacted with the tree on the right hand side polynomial number of times, from the viewpoint of the adversary, the interaction should be almost identical except with negligible probability. If indeed my function G is a secure PRG. So that is what is basically the overall idea of the proof.(Refer Slide Time: 19:39)That is what I have to show. And the idea behind a proof here is we basically define n + 1 complete binary tree, each of depth n, where each node is going to store 2n bit strings, but in a different way. So, let us start with the tree T0, which is actually a tree of depth in complete binary tree of depth n where each of the nodes basically consist of a uniformly random 1 n-bit string.And this is nothing but the way a truly random function f will behave as per the tree constructionand my ith tree i will be as follows. In my ith tree Ti, the first n - i levels, all the nodes in those n -i levels will consist of true l-bit uniformly random strings, whereas all the remaining levels will consist of pseudo random strings by applying the key mechanism or the key construction to the node at the previous level.If I go to the i = 1th key the way it differs from the ith key is that it will have one layer less of pseudo random strings and one layer more of pseudo random strings compared to the previous string. And we also know that how we can construct efficient CPA secure encryption scheme from PRFs by using modes of operation. Later in this course, we are going to see that how we can in fact construct more powerful symmetric encryption process namely authenticated encryption and CCA secure encryption just using pseudo random functions.So it turns out that everything just depends upon the existence of one way function that means if you want provably secure constructions of provably secure CPA secure encryption scheme,provably secure CCA scheme, provably secure authenticated encryption scheme, then it issuffice to just have one way function. That means it is enough you have just one-way function you can get everything for free.And later on in this course, when we will discuss public key cryptography, we will see that how exactly we can go about and construct one way functions based on specific number theoretic hardness assumptions. So, everything boils down to the existence of one-way functions. So, that brings me to the end of this lecture. Just to summarize in this lecture, we had seen very high-level overview of how we give provably secure constructions of pseudo random function, pseudo random permutation and strong pseudo random competition. Thank you!