Foundations of Cryptography Prof. Dr. Ashish Choudhury (Former) Infosys Foundation Career Development Chair Professor International Institute of Information Technology – Bangalore Lecture – 31 Random Oracle Model – Part I (Refer Slide Time: 00:30) Hello everyone, welcome to this lecture. Just a brief recap. In the last lecture we discussed some of the generic attacks which can be launched on hash functions, namely birthday attacks, and we also discussed some of the applications of hash functions like Block chains, Merkel trees and so on. In this lecture, we will continue our discussion on cryptographic hash function. Basically, we will introduce a very interesting proof model what we call as Random-Oracle model. (Refer Slide Time: 00:58)So, let us start with our discussion on Random-Oracle model which is also called as ROM. So there are several scenarios where we design cryptographic primitives where collisionresistant hash functions are used and those constructions are highly practical in nature and they are highly efficient. Some of the examples of such primitives are key-derivation function, commitment scheme, public-key primitives and so on, but unfortunately it turns out that we cannot prove the security of these cryptographic primitives based on the standard properties of hash function. What I mean by standard properties of hash function is the collision-resistance property, right. So what exactly Random-Oracle model does is it gives you a model in which you can prove the security of the cryptographic primitives which are designed based on hash functions where you cannot give the security proofs just based on the collision-resistance property of the underlying hash function and what we do in this Random-Oracle model is we make a very strong assumption about the underlying hash function. Namely, we make an idealized assumption and exact assumption that we make about the underlying hash function will be discussed soon and what this Random-Oracle model does is it acts as a middle ground for you where you have no security proof in one hand and whereas the other hand you have rigorous security proof just based on the standard cryptography assumptions. So since you cannot give the security proof of the constructions based on the standard properties of the cryptographic hash function.So assuming that we are in the Random-Oracle model serves kind of a middle ground where by making idealized assumptions about your underlying hash function, you can complete the security proof. (Refer Slide Time: 02:47) So let us go into the underlying details of the so-called Random-Oracle model. So what we do in this Random-Oracle model is assume we are designing a cryptographic primitive based on a hash function mapping arbitrary length bit strings to fixed size outputs of l bit strings. So what we do is we assume that the underlying hash functions behave like a random function mapping arbitrary length input to fixed length outputs and imagine we are designing a cryptographic primitive where we are using this underlying hash function modeled as a truly random function. We assume that each participant of the system have oracle access to the hash function. That means no participant in the system including the genuine user as well as the adversary will not be knowing the internal details and the code and the logic of the underlying hash function. So, that is a very strong assumption that we are making about the underlying hash function in this model because in reality when we are designing a cryptographic primitive, we are going to instantiate this hash function by some practical hash function. When we are using a some practical hash function every entity in the system will be knowing the exact code or the logic of the hash function, but when we are giving the proof in the Random-Oracle model, we assume that no entity in the system knows about the exact details of the underlying hash function. Also the calls between the oracle and the participants are private. That means, imagine if I have a cryptography primitive involving say user 1, user 2, and user 3 and each of them needs to use this hash function at say user 1 wants to evaluate the underlying hash function on some input x. Then we assume that in the Random-Oracle model the interaction between the user 1 and the interface or the oracle H is through a private channel between the user 1 and the oracle H. So user 2 and user 3 would not be knowing the exact inputs on which the user 1 is going to evaluate the underlying hash function or the oracle. It is also assumed that the oracle H is maintained as a table consisting of several x, y value and the way this table is maintained is as follows. If some entity queries this oracle on an input x, then what the table does is or the oracle does is it basically checks in the existing table which is a list of several (xi , yi) values whether there exist an xi entry with the value being x. That means basically, the table checks whether the value of the oracle on the input x is already there in the table or not. If it is there already, then the corresponding yi is returned back as the output of the oracle on the input x, whereas if there is no existing entry xi with matching the value x, then what the oracle does? It creates a new entry in the table where it stores the value of the x and against that x it stores a uniformly random y value where the y value is a uniformly random l bit string and that serves as the reference or the function output or the oracle value or the oracle output for the input x for the subsequent calls to the oracle. So by maintaining this oracle as an (x, y) table like this, it is ensured that indeed the oracle satisfies the properties that is required from a truly random function, right. (Refer Slide Time: 06:06)So there are some important properties in the Random-Oracle model and this will be crucial when we will be giving proofs in the Random-Oracle model. So the first property is that if some input x has not been queried to the oracle H, then the value of the oracle on this input x will be a uniformly random l bit value and this holds even if the input x is known to an entity or some part of the x is known to the entity or even if x is not uniformly random value. That means even if x is some input where all the bits of the input except the last bit is known and if the oracle has not been queried on that input x, then the output of the oracle on that input x is going to be a uniformly random l bit value, and I stress that this is different from the pseudo randomness property of the pseudorandom generator. Say if we have a pseudorandom generator G, then pseudo randomness property there requires that output of the pseudorandom generator G on some input x should be almost same as a uniformly random value only if the input x for the pseudorandom generator is a uniformly random value and unknown, whereas in the context of the Random-Oracle model, there are pseudo randomness property that we are requiring is different. Here, here we require that if the oracle is not queried for the input x and even if the x is not a uniformly random value and is known to you, the output value H(x) is going to be a uniformly random value from the co-domain. So that is one of the important properties. (Refer Slide Time: 07:41)The second important property in the Random-Oracle model is extractability property which is going to be a very crucial property later when we will see the proofs of the cryptographic primitives in the Random-Oracle model. So assume we have a cryptography construction of some primitive, say this primitive C involving certain number of entities, it could be a secure communication, protocol, or it could be just any kind of cryptography protocols. For instance, imagine that this cryptography primitive C involves 3 entities and this primitive also requires calls to an underlying hash function and suppose we are giving a reduction based proof that indeed this cryptographic primitive satisfies some property, some security property as per some definition, and say we are giving a reduction based proof and basically when we are giving a reduction based proof to prove that indeed the so-called cryptography primitives satisfy certain security properties as per some given definition in the RandomOracle model then when we are giving the reduction based probe what basically we are going to do is we will assume that say we have an adversary A attacking your cryptographic primitive C, then using that adversary our goal will be to design another adversary say A’ attacking another primitive, right. That is what typically we do in reduction based proof. Now as part of its attack strategy, this adversary A might need to call the underlying hash function, right, because that could be a part of its underlying attack strategy. But since now we are in the Random-Oracle model, this adversary needs to make oracle calls to the function H. So when this adversary A’ which we are designing as part of the reduction, it is invoking this existing adversary A as a subroutine, it will come to know that adversary A or the existing adversary A needs to invoke the oracle H on several x inputs of its choice. So those inputs, the output of the oracle on those inputs that the adversary A want to query for will be now learnt by the adversary A’ as part of the reduction. So, that is what we mean by the extractability property. That means the adversary A’ can now see the x queries which the existing adversary A would like to make to the H Oracle. This does not contradict the property that as mentioned earlier where I said that the calls between every entity and oracle is maintained or is happening through a private channel. In the reduction proof, the adversary A’ is basically invoking the adversary A in its mind. That means when it is invoking the existing adversary A as a subroutine, it will automatically come to know that as part of his attack strategy, what are the x queries or the x values for which the existing adversary A would like to make the H oracle calls, right. So that is not violating the existing property of the Random-Oracle model, but the important point here is that in as part of the reduction, the new adversary that we are trying to construct namely A’, it can extract out the x inputs for which the existing adversary would like to make the oracle calls. So that is one of the important property of the Random-Oracle model and the second property. (Refer Slide Time: 11:02) The third property of the Random-Oracle model which again will be very crucial when we are going to make proofs of the cryptographic primitives in the ROM model is the programmability property, and what exactly I mean by the programmability property as I mentioned that if we are giving a reduction based proved, then the new adversary A’ that we are designing when it invokes the existing adversary A, it will learn the H queries namely the x inputs for which the existing adversary would like to make the calls to the oracle, right. But since we are now doing a reduction here right, there is no H function which is actually available either to the adversary A or to the adversary A’ because now we are not invoking an instance of the primitive C, right. When we are actually instantiating an invocation of the primitive C, the parties will be having access to an oracle H, but now what we are doing here is we are giving a reduction based proof, so there is no instantiation of the primitive C. So, there is no oracle available either to the adversary A’ or the existing adversary A, but since as part of the reduction our adversarial strategy A is to make oracle calls for the oracle H at several x inputs basically our adversary A’ has to simulate the interaction of the existing adversary with H. Basically, the adversary A’ has to set the output of the oracle H at these x inputs which the adversary A is demanding. So, what the adversary A’ can do as part of the reduction it itself can set or it itself can pretend as if its itself has the access to the oracle and what it can do is it can just randomly select some y values from the co-domain of the underlying oracle H and return it back as the output of the oracle query that the adversary A has asked for. So that is what we mean by the programmability property. We call it as a programmability property because in the reduction, the new adversary A’ can program, it can set the output of the oracle at the x inputs for which the adversary A has asked for the response from the oracle. So, this is another important property of the RandomOracle model which we will use when we will get the reduction based proofs for cryptographic primitives in the Random-Oracle model. (Refer Slide Time: 13:21)So now let us compare a proof given or security proof for some cryptography primitive given in the Random-Oracle model versus the security proof given in the standard model. So again imagine that we have some cryptographic primitives say C and it involves say multiple entities and where we require each entity to use some underlying hash function. So in the standard model when we say that we have a security proof in the standard model, we do not abstract the underlying hash function as a Random-Oracle. Instead, we assume that it is a standard hash function and every entity has free access to the underlying hash function. That means, it knows the full code, the full description of the underlying hash function. We do not make the assumption that entities interact with the hash function by oracle, whereas in the Random-Oracle model when we are assuming that if you are designing say another primitive C’ involving hash function. If we say that we are giving a proof in the Random-Oracle model, then what exactly we mean by that is that whenever we are instantiating the primitive C’ at the beginning a new random function H will be instantiated and none of the entity will know what exactly is that particular hash function, right. So, this is a major difference for a security proof given in the RandomOracle model. That means every time we instantiate the primitive C’, it would not be the case that the same Random-Oracle or the same instantiation of the oracle H will be available as it was there in the previous invocation. In every subsequent invocation in every new invocation or an independent invocation of C’, an independent oracle H will be fixed at the beginning and each instance will have access to that oracle via private channels where no entity will know what exactly is the description of the underlying or the instantiated oracle. The security definition in the 2 proofs that we gave here will differ as follows. So, we will give certain definition of some security, so thus basically the security definition in the standard model will be that for all polynomial time adversary party or trying to attack the primitive C, the definition will be that the probability of a certain event should be negligible that will be security definition for the primitive C, right, in the standard model and more or less the same holds even for a security definition given in the Random-Oracle model. Namely, the security definition will be that for all poly-time adversaries trying to attack the primitive C’ in the Random-Oracle model, the probability of certain events should be negligible. What exactly that event is that depends upon the underlying primitive C and underlying primitive C’ that we are trying to construct. For example if the primitive C is a secure encryption process, then basically that event is the distinguishability event. Whereas if the primitive C is a very complicated cryptography primitive, then that event which defines whether the adversary is able to win the game or not might be a complicated event, but irrespective of that, the underlying intuition is that in the standard model security definition means that the probability of adversary attacking or breaking certain or the probability that an adversary ensures that certain particular event occurs with some probability is negligible whereas in the ROM model, the security definition more or less remains the same. The difference is that in the standard model, the probability is taken over the random choice of the parties and not over the underlying hash function because the underlying hash function is going to be a fixed hash function because every time we are going to instantiate the primitive C in the standard model, the same hash function will be used again and again, but when we are considering the probability of that certain event to be negligible in the RandomOracle model then the probability is taken not only over the random queries over the parties but also over the random choice of the oracle H which is instantiated at the beginning of the instantiation of the primitive C’. So, that is another important difference in the security proof in the Random-Oracle model versus a security proof in the standard model. (Refer Slide Time: 17:29)So what this means is that in the Random-Oracle model, security is guaranteed not for every possible Oracle instantiation. It means that the security may not be guaranteed for a particular instantiation of H, but it might be guaranteed for other instantiation of H, whereas in the standard definition when we are giving the proof just based on the collision-resistance property of the underlying hash function, the security proof holds for any instantiation of H which is guaranteed to be collision resistant, but that need not be the case in the RandomOracle model. That means it might be difficult to argue that any concrete instantiation of the oracle H by a specific real-world hash functions which are deterministic in nature will yield a secure scheme, right, and the important point is that even if we give a security proof in the RandomOracle model when we actually deploy that scheme in the real world, the underlying oracle H has to be instantiated by a concrete deterministic hash function and as soon as we instantiate the oracle H by a concrete deterministic hash function every entity in the system, the sender, the receiver, the honest party and adversary also will have access to the code of the underlying instantiation of the H. That means adversary cannot be restricted to just oracle access to H, right. So these are the important properties of the Random-Oracle model. (Refer Slide Time: 18:48)Now, let us quickly see an example to understand how exactly things work in the RandomOracle model. So imagine we have a hash function which takes inputs of size lin bits and gives you output of size lout bits and using this hash function suppose I design a function G which takes an input of size lin bits and gives you an output of size lout bits and basically what this function G does is it just evaluates the hash function on the input x. Now, I claim that if we are in the Random-Oracle model and if we interpret this underlying hash function as Random-Oracle which is instantiated at the beginning of each instantiation of the function G, then this function G can be viewed as a pseudorandom generator and to prove that indeed the function G that we have constructed here is a pseudorandom generator in the Random-Oracle model, we have to modify the indistinguishability game, the standard indistinguishability game which we use to define the security of pseudorandom generator to incorporate the Random-Oracle model. The change that is going to happen here is that if you recall in the standard indistinguishability game for PRG, the challenge for the adversary is to distinguish a pseudorandom sample from a truly random sample, but now since we are going to give a proof in the Random-Oracle model, we also need to model the oracle access to the underlying hash function of the Random-Oracle which the distinguisher might have access to. So, let us see the modified indistinguishability game for the PRG in the Random-Oracle model. Imagine there is an adversary A sitting between the sender and the receiver, and since we are now in the Random-Oracle model, what the adversary is going to do is, adversary will be now making polynomial number of oracle queries to this H and adversary would not be knowing what exactly is the underlying oracle H. So, until and unless adversary does not query this oracle H on the exact value , which is pre-shared between the sender and the receiver, the value of , which sender and receiver are outputting here will be uniformly random from the viewpoint of the adversary. Now, what is the probability that adversary indeed queried for H of , given that it has made number of queries to the oracle? Well, if my probability distribution or if the data which has been pre-shared between the sender and receiver has big -bits of min-entropy, then what the adversary can hope for is that every time it can ask the value of this H oracle on the most favorable data that it feels that the sender and the receiver might have picked as per this probability distribution So, the probability that in each single query, it has actually queried for the exact , is 12, because that has come from the definition of -bits of min-entropy and since the adversary has done number of queries, with maximum probability 2, adversary A might have queried for the input H of from the oracle H. And if we assume that big is sufficiently large and is any how polynomially bounded in the security parameter, this is some negligible function in the security parameter. So, since adversary has not queried for H of , except with negligible probability, from the viewpoint of the adversary, the resultant key is going to be a uniformly random ℓ-bit string and that ensures that now sender and receiver can safely use the derived key for any cryptography primitive as the key. Say for instance if they want to use the key as the key for AES, they can safely use it. So, now, you can see that how this highly efficient key-derivation function based on hash function can be proved secure if we go in the Random-Oracle model. But if we just go into standard model and use the standard properties of the hash functions, namely collision-resistance, we cannot prove that the so called key derivation function is indeed a secure key derivation function. So that brings me to the end of this lecture. Just to summarize in this lecture, we have continued our discussion on the Random-Oracle model. We have seen that we have certain arguments in the favor of Random-Oracle model, we have certain arguments against Random-Oracle model and so on. So that brings me to the end of this lecture. Just to summarize in this lecture, we have introduced a Random-Oracle model. This basically is used to give the security proof of cryptographic primitives based on some hash functions where we cannot complete a security proof of that primitive just by using the standard properties of the hash functions namely the collision-resistance property and we have also seen a demonstration of the Random-Oracle model, namely we have seen that if we take a hash function and model it as a RandomOracle, then we can use it to construct a pseudorandom generator. Thank you.
Log in to save your progress and obtain a certificate in Alison’s free Cryptography: Authentication Codes and Hash Functions online course
Sign up to save your progress and obtain a certificate in Alison’s free Cryptography: Authentication Codes and Hash Functions online course
Please enter you email address and we will mail you a link to reset your password.