 Notes Study Reminders Support
Text Version

### Set your study reminders

We will email you at these times to remind you to study.
• Monday

Tuesday

Wednesday

Thursday

Friday

Saturday

Sunday

Foundations of CryptographyProf. Dr. Ashish Choudhury(Former) Infosys Foundation Career Development Chair ProfessorIndian Institute of Technology-BengaluruLecture-04Perfect SecurityHello everyone, welcome to lecture 4.(Refer Slide Time: 00:28) Plan for this lecture is as follows: we will discuss perfect secrecy, which is the first formal notion of security, which is also the strongest notion of secrecy. We also will discuss various equivalent definitions of perfect secrecy.(Refer Slide Time: 00:45)So, the definition of perfect security was given by Claude Shannon in his classical work in 1948 and Shannon is often considered as the father of information theory and this notion of security is also called as unconditional security and information theoretic security. The attack model that is considered in the definition of perfect security is the ciphertext only attack model, where we assume that we have a sender and a receiver who have agreed upon a random key value k.We assume that sender has encrypted a single message m using a publicly known encryption process under that key k, and the ciphertext has been intercepted by the adversary. The interesting part of this attack model is that we assume here that the adversary is computationally unbounded. That means we make no assumption whatsoever about his computing power. We assume that he can do any kind of computation with brute force or any other computation. So that is the interesting aspect of this security model. Informally, perfect security says that irrespective of any prior information that the attacker has about the underlying plain text, seeing the cipher text provides no additional information to him about the underlying plain text. That means seeing the ciphertext is absolutely useless for the attacker. Whatever it could infer about the message from the ciphertext, same it could have already inferred before any ciphertext would have been communicated.So here we have 2 entities, we have the prior information and we have the term no additional information. We have to now learn a little bit of math to understand how to formalize these 2notions namely that of prior information and that have no additional information.(Refer Slide Time: 02:36)So, imagine we are given a publicly known cipher namely a triplet of algorithms key generation algorithm, encryption algorithm and a decryption algorithm. Then any attacker has the following information about the encryption process. Namely, he knows 3 spaces, namely the message space, the key space and the cipher text space, where the message space is the set of all legitimate messages which could be encrypted by the encryption process. Keys space denotes all possible keys which could be output by the key generation algorithm. And the ciphertext denotes all possible ciphertext, which could be generated by the encryption algorithm. From the viewpoint of the attacker, any encryption scheme induces 3 probability distribution, one probability distribution over the message space, one probability distribution over the key space and one probability distribution over the ciphertext space. So now let us go over this probability distributions one by one. The first probability distribution is over the key space and this is induced by the key generation algorithm. So remember, as per the Kerckhoffs’ principle, we assume that steps of the key generation algorithm, encryption algorithm and decryption algorithm are publicly known to the attacker. We also discussed that key generational algorithm has to be a randomized algorithm. That means, every time we run the key generation algorithm it is going to output a possible candidate key from the key space with certain probability. So that is what we mean by the probability distribution over the key space induced by the key generation algorithm. Also, we discussed in one of the earlier lectures that in most of the cases, the key generation algorithm is going to output a uniformly random key from the key space. Namely, if the key space size is cardinality of key space, then any candidate key could be generated with probability one over the key space. So that is the uniform distribution over the key space, which adversary will already have if he knows the steps of key generation algorithm. But it is not necessary thatyour key generation algorithm always outputs uniformly random keys from the key space. So that would be inducing another kind of probability distribution.Whatever is the case since the steps of the key generation algorithms are publicly known. We know that from the viewpoint of the attacker, there is a probability distribution over different values of keys, which could occur with different probabilities.That is precisely the probability distribution over the plain text space that attacker has. We can also mathematically capture what exactly we mean by no additional information. Formally, an encryption process namely a collection of algorithms key generation, Enc and Dec over a plain text space M is called perfectly secure if for every probability distribution over the plain text space and key space, and for every plain text m belonging to the plain text space, according to that probability distribution, and for every ciphertext c belonging to the ciphertext space, Pr [M = ? | C = ?] = Pr [M = ?] holds. So let ustry to understand what exactly the LHS and RHS of this equality stands for. If you consider the RHS part of this equality, namely Pr [M = ?], m could be communicated by the sender. That is a prior information about the underlying plain text before any communication has happened from the sender to receiver, before any key generation algorithm has been used, and the message has been encrypted. That is the apriori information about the underlying plaintext.Whereas the LHS part of this equality Pr [M = ? | C = ?] that supposed posteriori probability that the message m is encrypted in c. That means, given that adversary has seen or intercepted a cipher text c, what is the probability that the plain text m is encrypted in this cipher text c. So, intuitively, when we say that these 2 probabilities are equal, it means that whatever the adversary knew about the underlying plain text before any cipher text was communicated with same probability adversary knows that a plain text could be m and in the given cipher text c.That means observing the ciphertext c does not change attacker’s knowledge about the distribution of the plaintext. Whatever the attacker’s knowledge was before seeing the ciphertext, the same knowledge it has, even after seeing the ciphertext. Moreover, it holds even if adversary is computationally unbounded. That is the importance of this definition. This definition does not put any kind of restriction on the computational power of the adversary. Even if adversary knows the steps of the algorithm, even if it knows what could be the candidate keys even if it is allowed to do brute force, its view or its knowledge about the underlying plain text or the distribution of the plain text should not change before and after seeing the ciphertext.If that holds, then we say that our underlying encryption process is perfectly secure. Notice that in this definition, I have highlighted few things namely, I have said that the condition should hold for every probability distribution over the plain text space.That means it does not matter whether the distribution over a plain text space is a uniform distribution or a bias distribution, the condition should hold for any possible probability distribution over the message space. In the same way, the condition or equality should hold for any kind of probability distribution over the key space whether it is a uniformly generated key, whether the key generation algorithm output uniformly generate random keys or bias keys still the condition should hold.Moreover, once we fixed up probability distribution of the plain text space and the key space, the condition should hold for every plaintext belonging to the message space and every candidate ciphertext belonging to the ciphertext space.(Refer Slide Time: 20:45)So now, what we will do is we will see some alternate equivalent definitions for perfect security. This is the original definition of perfect security as given by Shannon and the interpretation of equality of these 2 probabilities is that the probability of knowing a plaintext remains the same before and after seeing the cipher text. That is the interpretation of the original definition of perfect security as given by Shannon.Now let us see the first alternate definition. The first alternative definition says that we will say an encryption process or an encryption scheme to be perfectly secure if for every probability distribution over the plaintext space and key space and for every pair of message m0, m1 which occurs with non-zero probability with respect to that probability distribution and every cipher text c the following equality should hold : Pr[C = ? | M = ?0] = Pr [C = ? | M = ?1].The equality says that Pr[C = ? | M = ?0] is same as Pr [C = ? | M = ?1]. The interpretation of this equality is that the probability distribution of the ciphertext is independent of what exactly is your underlying plain text. That means if the adversary sees the ciphertext c over the channel, then it does not matter whether M = ?0 or M = ?1 with equal probability from the viewpoint of the attacker, the ciphertext c should be a candidate encryption of m0 as well as a candidate encryption of m1.There should not be any bias in the probability. But whether it is an encryption of m0 or whether it is an encryption of m1, that means the ciphertext distribution should be independent of the underlying plaintext.(Refer Slide Time: 22:32)So now what we are going to do next is we are going to prove that both these 2 definitions are equivalent. Namely, we will show that if there is an encryption process which satisfies the original condition of Shannon's perfect security, then the same encryption process has to satisfy the alternate definition and vice versa. Let us first prove the equivalence of the definition assuming that we have an encryption process which satisfies the condition of alternate definition.Namely, we assume that we have an encryption process where for every probability distribution, Pr[C = ? | M = ?0] = Pr [C = ? | M = ?1] = ?, say delta, for all pair of messages m0, m1 in the plain text space, and for all ciphertext c belonging to the cipher text space. Given this, we will prove that the original condition of the Shannon’s perfect security is also true for the encryption process.Pr [M = ? | C = ?] = Pr [M = ?]. So what we are going to do is assume we have an arbitrary plain text and arbitrary cipher text character. Now let us try to compute Pr [M = ? | C = ?]. So what I am going to do here is I am going to apply the Bayes theorem here.By applying the Bayes theorem, Now let us try to compute Pr [C = ?]? The probability that your ciphertext is c is going to be this summation. This summation state that you take all possible messages from the plain text space and find out what is the probability that the message is that candidate plain text namely m’ and given that the message is m’, what is the probability that m’ is encrypted in c.That will give you the probability distribution over the cipher text c. Because what have to basically do is imagine you have the plain text space you take each of the candidate plaintext that is precisely the first term in this summation. And once you have fixed that candidate plaintext you just compute what is the probability that that candidate plaintext will take you to the ciphertext c, that is this second term.And if you multiply all this, if these 2 probabilities and take the summation over all candidate plain text, that will give you the probability distribution of ciphertext being c. Now, as per our hypothesis of the condition, we know that the conditional probability that ciphertext is c given the plain text is m’ is same for all m’ namely, Pr [C = ? | M = ?’] = ?, because that is what is the assumption that we are making.We are making the assumption that our encryption process satisfies the alternate condition. So for every m’, I can replace the second term in the summation by ?. As a result, I get this simplified form of the summationWe have computed the value of probability of C = c, that is ?. Now, let us try to compute Pr [C = ? | M = ?], that is the numerator part of this RHS expression. And again, as per our hypothesis of this theorem, or this lemma, we already know that Pr[C = ?] = ?. And that is irrespective of what is my m, it could be m0, it could be m1 it could be m2 for any candidate m from the plaintext base, Pr[C = ?] = ?. So, that means the numerator part of this RHS expression is also ?. Hence, I can say that my original LHS namely, Pr [M = ? | C = ?] nothing but this equality.And in the numerator as well as in denominator, I have the ? so I can cancel it out. And hence, I obtain that this conditional probability is nothing but Pr [M = ?], which is precisely what exactly we wanted to prove. That means we have proved that if the encryption process satisfies the condition of the alternate definition, then it also has to satisfy the condition of original Shannon's definition. So, now let us do the proof in the reverse direction.(Refer Slide Time: 27:54)Namely, we assume that we have an encryption process which satisfies the condition of the original Shannon's definition. That is the Pr [M = ? | C = ?] = Pr [M = ?] ∀ ? ℳ, ? ?. Given this will prove that the distribution of the cipher text is independent of the underlying plaintext. Namely, it does not matter whether the plain text is m0 or whether the plain text is m1with equal probability, it could lead to the cipher text c, and this holds for every pair of messages m0, m1 in from the plain text space and every cipher text c from the cipher text space. Let us first try to compute Pr [C = ? | M = ?0]. For this we are going to use the fact that as per the given condition, since the encryption scheme satisfies the original Shannon’s condition, we know that Pr [C = ? | M = ?0] = Pr [M = ?0]. So now what I am going to do is I am going to expand my LHS part here using the Bayes theorem, where I am just changing the numerator and the denominator of the conditional probability. And by applying the Bayes theorem, I get this equality.= Pr[M = ?0] Now, what I can do is I can cancel out this common term from both the LHS and RHS. Hence I obtain that Pr [C = ? | M = ?0] = Pr[C = ?]. By applying the same logic, I can conclude that Pr [C = ? | M = ?1] = Pr[C = ?].As a result, both Pr [C = ? | M = ?0] and Pr [C = ? | M = ?1] are same namely, it is Pr[C = ?]. That means, we have proved that if the original Shannon's condition is satisfied, then the encryption process also has to satisfy the condition for the alternate definition. That means, both these definitions are equivalent to each other.So, if you are given an encryption process and if you are asked to prove whether it is perfectly secure or not, then you can either prove it as per the original Shannon's condition or you can prove it as per the first alternate definition.(Refer Slide Time: 30:30)Now, let us see another equivalent definition of perfect security. Before going into this definition, let us first try to understand the underlying intuition that we want to capture through this definition. So, the goal of the perfect security is the following: imagine a scenario where a key for the encryption process has been agreed upon between the sender and the receiver. Suppose the adversary knows that ? {?0, ?1} and that too with equal probability.Suppose indeed sender is going to encrypt message m0 or m1 with equal probability. And it encrypts one of these messages randomly using the key k as per the encryption process,computes the cipher text c and sent it over the channel. Say, the attacker intercepts the cipher text c, and the attacker has unbounded computing power. Intuitively perfect secrecy demands that the adversary’s knowledge about the underlying plain text should remain the same even after seeing the ciphertext c.So what was this information about the plain text before any cipher text was communicated in this particular case: with probability half from the viewpoint of the attacker, the plain text could be m0, and with probability half the plain text would be m1. Now perfect secrecy demands that even after seeing the cipher text c and even after knowing the steps of the encryption process, and even if the adversary has unbounded computing power, the advantage that adversity gets after seeing the cipher text and learning the underlying plain text should be 0.That means, even after seeing the cipher text c, the probability that the underlying plain text would be m0 or m1 should be half. Adversary can do nothing better than guessing the underlying plain text. That is the underlying intuition that we are now going to formalize.(Refer Slide Time: 32:21)And this intuition is formalized by a challenge response game, which we call this experiment. And we are going to see that in the rest of this course, every security definition is going to be formalized by this kind of challenge response experiment or a game which model something which we want, which can happen in reality. The experiment is as follows: we assume that we are given a publicly known cipher  = (Gen, Enc, Dec), ℳ, and the game is played between 2entities.The first entity here is an adversary or an algorithm for the attacker which we denote by this algorithm A and the algorithm or the adversary is computationally unbounded. This models the fact that we are trying to capture the notion of perfect secrecy where the adversary is computationally unbound. The second entity here is the hypothetical verifier which is going to model the sender.Now, the nomenclature that we are going to follow while naming this kind of experiments is as follows: this particular experiment is denoted by ?????(?, Π)???. Now let us try to decode each of the individual parts of this complicated name. So, the name PrivK denotes here that we are trying to model an experiment for a symmetric encryption process or a private key encryption process.That is why the name PrivK, later when we will try to model the security requirement for public key primitives. This privK will be replaced by PubK. The name of the string eav denotes here we are considering an adversary where the adversary is only allowed to eavesdrop or just listen the cipher text because we are in the cipher text only attack model. The name A here denotes the name of the algorithm here and  denotes the name of the encryption process with respect to which this game is going to be played. That is the nomenclature we are going to follow to denote this particular experiment. Now, what are the rules of this game? This experiment is going to be a randomized experiment. The first step here is that adversary selects a pair of messages from the plain text space, say m0and m1 with the restriction that their size has to be same. An adversary can choose any pair of messages. There is absolutely no restriction we put on which pair of messages that it can submit to the verifier. The only restriction is that their length have to be same, so adversary can deterministically pick up a pair of message, it could randomly pick a pair of message, it can use any strategy to pick the pair of message that it wants to send to the verifier. Now, once the pair of messages are communicated to the verifier, what the verifier is going to do is the following: it is going to run the key generation algorithm which will output a uniformly random key or a key as per the steps of the key generation algorithm for the verifier.And the verifier is going to randomly pick one of these two messages for encryption. The index of the message which is going to pick for encryption is denoted by b, which is picked uniformly randomly. That means, with probability half, it might be picking the message m0 for encryption, or with probability half it might be picking the message m1 for encryption. Once it has decided the index of the message, it encrypts that message mb using the key k which is known only to the verifier and the ciphertext is given to the adversary.And now the goal of the adversary is to find out the index of the message which has been encrypted in c, that means the adversary has to find out whether the c is an encryption of m0 or whether it is an encryption of m1. After analyzing the cipher text c as per whatever strategy adversary wants to follow, it gives them prediction. Namely, it outputs a bit, which is either 0 or 1 corresponding to the index, which it feels that that particular message has been encrypted in the cipher text c.That means b’ denotes the index, which according to the adversary is the index of the message which is encrypted in the ciphertext c. That is the experiment. As you can see, this is a randomized experiment, because adversary could pick any pair of messages as per its randomness. In the same way the verifier is going to pick any random message out of this pair for encryption, and the key could be any random key as per the key generation algorithm.Now the output of the experiment is decided as follows. We say that output of the experiment is 1 or which is interpreted as adversary has won the game, if it has correctly predicted what exactly is the message which is encrypted in the ciphertext c. That means if it correctly output b’equal to b then we say that the adversary has won this experiment or the adversary’sexperiment’s output is 1.On the other hand, if the adversary incorrectly identifies what is encrypted in that cipher text c that means it outputs b’ which is different from b, then we say that output of the experiment is 0, which is interpreted as adversary has lost the game. We also saw the game-baseddefinition, which models perfect indistinguishability. I hope you enjoyed this lecture. Thank you!