Foundations of Cryptography Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science - Bangalore Lecture - 44 El Gamal Public Key Encryption Scheme (Refer Slide Time: 00:33) Hello everyone. Welcome to this lecture. Just to recap, in the last lecture, we have seen the syntax of public-key encryption scheme. So the roadmap for this lecture is as follows. In this lecture, we will see a candidate public-key encryption scheme, namely El Gamal public-key crypto system and we will prove formally its CPA security and we will end the lecture with some of the implementation issues, which we face while implementing El Gamal encryption scheme in practice. (Refer Slide Time: 00:56)So let us try to understand the intuition of El Gamal encryption scheme. So for that, recall the Diffie–Hellman key-exchange protocol. And for simplicity, assume we are considering a multiplicative cyclic group. So the public parameters are the description of a cyclic group, a generator and the size of the group, which is . And in the Diffie–Hellman key-exchange protocol, say Sita and Ram, they want to agree upon a key, each of them pick up their own contribution for the overall key. So Sita picks her contribution , and she sends to Ram. And independently, Ram picks his contribution and sends . And overall key that is agreed between the sender and receiver is . And we had formally proved the security of the Diffie–Hellman key exchange protocol. So now, consider the following encryption process. So sender and receiver first runs an instance of the Diffie–Hellman key-exchange protocol to obtain a shared key, denoted by , which is a group element. And we know that if the DDH assumption holds in the underlying group, that means if the DDH problem is difficult to solve in the underlying group, then the agreed key is indistinguishable from any random element of the group. Now imagine, Ram has a message, say plain text , which is a group element, which it wants to encrypt and send it to Sita. So what Ram can do is, from the view point of Ram, Ram knows that by running the Diffie–Hellman key exchange protocol, Sita is also going to have the same key And Ram also knows that if there is an eavesdropper, who has eavesdropped the communication between Sita and Ram, then from the view point of that adversary, the key , which is available with Ram, is kind of indistinguishable from any random element from the group. So what Ram can do is, to encrypt the plain text , it can use the key to mask its plain task and since we are performing operations in the group, to mask the plain text, what Ram can do is, it can perform the group operation on the message and the key and the result is denoted by , which is also sent with the message, which Ram would have sent as part of the Diffie–Hellman key exchange protocol. Now once Sita receives the messages from Ram, she is now receiving two elements from the group. The first element is Ram’s contribution as part of the Diffie–Hellman key exchange protocol, which Sita uses to generate the key as per the steps of the Diffie–Hellman key exchange protocol. As once it has received the key , to decrypt the cipher text, what Sita has to do is, she has to just cancel out the effect of key or she has to unmask the key . And to unmask the key , what she can do is, she can just perform the group operation on the cipher text and the multiplicative inverse of the element . So since the element is known to Sita and she knows the group description, she can compute the multiplicative inverse in polynomial time, which I denote by −1 . And if she performs the group operation on the cipher text and −1 , the effect of cancels out. And Sita ends up getting the plain text . Now, I claim here that the cipher text , which is the result of the group operation on the plain text and the key , is going to be independent of the underlying plain text . I will prove this very soon, but for the moment assume that this claim is true. If indeed this claim is true, then this whole protocol, this whole process of encryption and decryption indeed looks like a candidate encryption scheme. Because if the distribution of the cipher text is independent of the key , then even after seeing the cipher text , adversary will be unable to figure out what exactly is encrypted in , whether it is an encryption of 0 , 1 , 2 , it cannot figure out. So that is the overall intuition of the El Gamal encryption scheme. (Refer Slide Time: 05:09)So I have written the blueprint of the encryption scheme that I had discussed in the last slide. Now the question is that how we can visualize the entire process that we have discussed just now as an instantiation of public-key encryption scheme? Because remember as per the syntax of public-key encryption scheme, we need to have a key-generation algorithm, which would output a public-key, secrete-key pair, we should have an encryption algorithm and we should have a decryption algorithm. So pictorially, we know that now we have a blueprint of an encryption process, but now we have to put everything into the syntax of public-key encryption process. And this process of visualization of above encryption process as an instance of public-key encryption scheme was identified by Taher El Gamal. And that is why this encryption process that we are going to discuss now is called as El Gamal encryption scheme. So you might be wondering that how exactly it is different from this Diffie–Hellman key-exchange protocol? Well, we are not doing anything apart from Diffie–Hellman key exchange protocol. So this part of the communication, which I have highlighted is exactly Diffie–Hellman key exchange protocol. But on top of that, we are doing some additional communication from the sender’s side, which allows the receiver to decrypt the cipher text and recover back the plain text. So what we are going to do is, the entire encryption process that we have discussed till now visually, we can imagine it as an instance of public key encryption scheme as follows. So we can imagine that the receiver’s message here, namely Sita’s message as part of the Diffie–Hellman key-exchange protocol is her public key.And we can visualize that as if, that is her contribution for the Diffie–Hellman key-exchange protocol with every potential sender, once for all. That means, the key-generayion algorithm that Sita can run here is as follows. As part of secret key, she can randomly pick an index in the range 0 to and she can make her public key to be . And it will be ensured that it is an authenticated copy. That means, indeed this is generated by so called Sita. How exactly it is ensured, we will see or solve that problem later on. But for the moment assume that Sita has generated a secret key like that and she has computed public key to be and made it available in the public domain. Then, we can imagine as if this is her contribution or her part of the message for the Diffie–Hellman key-exchange protocol with every possible Ram, who would like to do a secure communication with Sita. Now, assume we have a so called Ram or a sender who wants to encrypt a plain text, say , using the public key. So what Ram is going to do is, Ram is going to pick a random in the range 0 to and now he is now going to compute two group elements. The first group element is 1 , which is nothing but . And a second group element 2 is basically the group operation being performed on the plain text and the key , where the key is , which is obtained by raising the public key to the index . So the two messages or the two elements which Ram is sending, can be visualized as follows. The first message, you can interpret as if it is Ram’s contributions or sender’s contribution for the Diffie–Hellman key-exchange protocol, because if indeed Ram would have participated in an instance of the Diffie–Hellman key-exchange protocol, then 1 is the message, which Ram would have sent to Sita in response to the message , which Sita has already sent and went offline. The second message 2 or the second group element 2 , you can imagine as if it is masking of the plain text with the resultant Diffie–Hellman key, which Sita and Ram would have agreed upon using and as the protocol transcript. So now if we imagine this encryption process by parsing the messages from Sita and Ram like this, then it automatically fits into the framework of our public-key encryption process. To do the decryption, what Sita has to do is, from the first group element, which Ram has sent, using that and the public key that Sita has sent already to the so called Ram, Sita can perform her steps of the Diffie–Hellman key-exchange protocol and agree upon or retain the same key , which Ram has used for masking the message. And once it recovers the key , to decrypt the cipher text, it takes the second component of the cipher text, namely 2 and it performs the group operation on 2 and the multiplicative inverse of −1 to recover back the plain text. My claim here is that in this entire process, the distribution of the second component of the overall cipher text, namely 2 is independent of the underlying plain text. So we will soon prove this fact, but now if we imagine this whole thing, like the way I have said, now you can see that we have now an instance of a public-key encryption scheme. (Refer Slide Time: 10:31) So now let us put the exact formal details of the El Gamal encryption process. So the plain-text space and the public-key space are both going to be the group. And the secret-key space is going to be ℤ, namely it is going to be the set {0,… , . And overall cipher text will consist of two group elements. So it is going to be a pair of elements from the underlying group. The keygeneration algorithm outputs a public key and a secret key as follows. The secret key is a random in the range 0 to and a public key . So that you can imagine as if Sita is doing her part of the Diffie–Hellman key exchange protocol with every potential receiver once for all. The encryption algorithm, which Ram or any sender is going to follow for encrypting a plain text is as follows. The sender is going to pick a random in the range 0 to 1. And compute , that is going to be the first component of the cipher text. And the actual encryption of the message is the group operation performed on the plain text and the public key raised to the power . So pictorially, you can imagine that first component of the cipher text is nothing but sender’s contribution for the Diffie–Hellman key, which sender and receiver are going to agree upon. And the second component of the cipher text is the masking of the plain text with the Diffie–Hellman key. Now the decryption operation is, you receive a cipher text consisting of two group elements. So you first compute a Diffie–Hellman common key, which is going to be established between the sender and the receiver, by raising the group element 1 to the secrete key, so that you also obtain , find a multiplicative inverse of it. And then perform the group operation with the second component of the cipher text, so that effect of vanishes and you end up with the plain text. So that is the formal syntax of the El Gamal encryption scheme. Now we want to prove formally that this El Gamal encryption scheme is indeed COA secure. As we have discussed in the last lecture, in the public key world, COA security, single message CPA security and multi message CPA security are all equivalent. So it suffice to just prove the COA security of this encryption process. So as I am claiming over the last few slides, the distribution of the cipher text component 2 , namely the group operation on with the Diffie–Hellman key, is going to be independent of the underlying plain text. That means, from the view point of a computationally bounded adversary, if it sees 2, then from its view point,2 could be the result of applying the group operation on any and any . And if that is the case, that means, if this claim is indeed true, then it automatically implies COA security. Intuitively this is because for each instance of the encryption algorithm in this El Gamal encryption scheme, the sender is going to pick a randomly. It is not the case that it will pick the same every time. And ifis picked independently for each instance of the encryption, then it automatically means that the Diffie–Hellman key , which is used for masking the message is also going to be independent for each instance. Because the overall Diffie–Hellman key is . So even if thecomponent in the resultant Diffie–Hellman key, which sender and receiver are using to do the encryption and decryption is same, it is the which is triggering the randomness here and since is independently picked here, for each instance of the encryption, the overall Diffie–Hellman key , which is used in each instance is independent.And now assuming that this claim is true, that means the distribution of 2 is independent of the underlying plain text, we get the COA security. (Refer Slide Time: 14:34) So now let us formalize this intuition by a rigorous proof. And before going into the proof, let us do a warm up here and consider a variation of El Gamal encryption scheme. Mainly we are going to consider a perfectly-secure variant of the El Gamal encryption scheme. I stress here that it is not the way we are going to implement the El Gamal encryption scheme and it is not the way we actually use the El Gamal encryption scheme. This variation of the El Gamal encryption scheme in the private key setting is just to make the proof simpler. So the modified El Gamal encryption scheme in the private key setting, I am denoting as Π̃. It has its own key generation algorithm, encryption algorithm and decryption algorithm. The public parameters are the cyclic group, group description and a uniformly random group element , where is not known. So we can imagine as if it is some kind of set up, which has been done by a trusted third party and is not known to anyone. Now since this is a symmetric key encryption process, the key generation algorithm is going to output a uniformly random key and the key is an element of the group. To encrypt a message in this variant of El Gamal encryption process, we compute two group elements, namely 1 and 2 . Where 1 is some , where is randomly chosen from the set ℤ. And cipher text component 2 is basically the masking of the message with the key . Since it is a symmetric key encryption scheme, we are going to use the same key for decryption as well. And to recover the plain text, we basically take the second component of the cipher text and perform the group operation with respect to the multiplicative inverse of the key. Notice that in this variation of the El Gamal encryption process, the first component of the cipher text, namely 1 and the publicly known , they are not at all used for the encryption process and for the decryption process. But I am just retaining them, to ensure that the overall syntax of the cipher text that we are getting here looks like the same as we are going to obtain in the real instantiation of the El Gamal encryption scheme. Now I claim here that private key variant of the El Gamal encryption process is perfectly secure if my underlying plain text is the group . And this is because this private key variant of the El Gamal encryption scheme is exactly similar to the one-time pad scheme over the group . The only difference is that in the one-time pad scheme, we perform the XOR of the key with the plain text. But since we are in the group setting, we are going just replacing that XOR operation by the group operation. More formally, assume that we have an arbitrary cipher text, say (1, 2) and say we consider a pair of arbitrary plain text, namely 0 and 1 , which are group elements, because here my plain text space is the underlying group. I am going to show that indeed this encryption process satisfies the definition of perfect secrecy. Namely consider the probability that this arbitrary cipher text(1, 2) is an encryption of the plain text 0 . And in the same way, consider the probability that this arbitrary cipher text (1, 2) is an encryption of 1 . It turns out that this arbitrary cipher text (1, 2) is an encryption of 0, only if key-generation algorithm would have produced a key, which is the result of group operation performed on 2 and the multiplicative inverse of 0 . But since the key-generation algorithm outputs uniformly random elements from the group as the key, it turns out that the key generation algorithm indeed outputs a key, which is same as 2 group operation 0−1 is 1 over the group size. Now by running exactly the same argument, we can claim that the probability that the plain text 1 is encrypted in the cipher text (1, 2) is exactly the same, that my key generation algorithm outputs a key, which is same as the group operation performed on 2 and 1−1.And the probability that my key is this, is 1 over the size of the group. That means, for any adversary, even if it is computationally unbounded, if it participates in perfectly-secure indistinguishability experiment in the symmetric key setting or the COA experiment, then the probability that it can distinguish apart whether it is seeing an encryption of the group element 0 or whether it is seeing an encryption of the group element 1 , is exactly half. That means, you cannot distinguish apart; with equal probability it is an encryption of 0 as well as encryption of 1 . And that is why this modified or symmetric-key variant of the El Gamal encryption process is perfectly secure. (Refer Slide Time: 19:38) Now let us turn to the COA security of the actual El Gamal encryption scheme that we have designed in the public key setting. So before going further, let us again remember what we have proved just now. So we have considered a variant of El Gamal encryption scheme in the symmetric key setting and here is the encryption algorithm. The encryption algorithm produces two group elements (1, 2), where 1 is some random and 2 is the masking of the message. And apart from that, adversary also have a public information, namely , where is not known to the adversary. So if I consider the view of the adversary, the adversary’s view basically consists of three probability distributions, namely he has an element , where is randomly chosen from ℤ.It knows the value of , where is randomly chosen from ℤ. And it knows the masking of the message with the plain text, where the key is chosen randomly from the underlying group. And we have proved that this encryption process is perfectly secure. On the other hand, the actual El Gamal public key encryption scheme, that we have designed, there also the cipher text consists of two group elements. And second component of the cipher text is the masking of the message with the Diffie–Hellman key, namely . So if I consider the adversary’s view in this real instantiation or the actual instantiation of the El Gamal encryption scheme in the public key setting, then its view is as follows. It knows the value of , where is unknown and uniformly random from the set ℤ. It knows the value of , where is uniformly random from the set ℤ. And it knows the masking of the message with the Diffie–Hellman key, where the Diffie–Hellman key is nothing but , and it belongs to the underlying group. Now if you see here closely, what exactly is differing here, if I consider the views of the two adversary here? The distribution of in both the worlds or for the adversaries are perfectly the same. They are exactly indistinguishable. Here also alpha is random, here also alpha is random, not known to the adversary and adversary knows the value of . In the same way, the distribution of in both the worlds are exactly identical. What is differing here, is the nature of 2 that adversary sees in the symmetric key variant of El Gamal scheme and the distribution of 2 , which adversary sees in the actual El Gamal encryption scheme. In the symmetric key world, the masking is with a uniformly random group element , whereas in the public key El Gamal, the masking of the plain text is with the pseudo-random key , which is a Diffie–Hellman key . And if I assume that the DDH assumption holds in my underlying group, then we know that as per the Diffie–Hellman assumption, Diffie–Hellman triplet and a nonDiffie–Hellman triplet, they are computationally indistinguishable from the view point of any computationally bounded adversary. That means, if my is uniformly random, that means if I am in this case, then in that case is some , where is totally random, not related to and . Whereas if I consider cipher text 2 as per the public key Diffie–Hellman pulic-key El Gamal encryption scheme, then my key is nothing but .So if my adversary cannot distinguish between a DH triplet and a non-DH triplet, then I can say that the distribution of the cipher text component 2 , which adversary sees in both the worlds are also computationally indistinguishable and that will automatically prove that our El Gamal encryption process is COA secure. (Refer Slide Time: 23:45) So that is the formal statement which we are going to prove now. We are going to prove that if the DDH assumption holds in my underlying group, then the El Gamal encryption process is indeed COA secured. And we formally establish this fact by giving a reduction. So assume, you have a poly time adversary who can attack your El Gamal public key encryption scheme. Using that attack, we are going to design a DDH solver, a poly time DDH solver who can distinguish apart a Diffie–Hellman triplet from a non-Diffie–Hellman triplet. So it participates in an instance of the DDH experiment. The DDH experiment prepares a challenge for the DDH solver by giving him (, where and are random group elements. And third component of the triplet is either , or it is a uniformly random element , depending upon whether the challenger has or . And the task of the DDH solver is to find whether it is a DH triplet or a non-DH triplet.To solve that, the DDH solver invokes our attacker, who can attack the El Gamal encryption scheme and participates in an instance of the COA game and it sets up the public key to be . Now as per the rules of the COA game, the COA attacker will submit a pair of challenge plain texts from the underlying group and this DDH solver is going to randomly choose one of those two messages and it prepares the challenge cipher text as follows. The second component of the triplet, which is given as the challenge to this DDH solver, is set to be the first component of the cipher text and the actual encryption of the message is set as , masked with the third component of the triplet, which is thrown as a challenge to the DDH solver. So now before proceeding further, let us try to understand what is happening in this overall reduction. If you see here that if this triplet is a non-DDH triplet, that means in this case in some , where is not related to and , then the distribution of the cipher text (1, 2), which is given to this attacker against the El Gamal scheme, has exactly the same distribution if this attacker would have participated in the COA game against the symmetric-key variant of the El Gamal encryption scheme. Because that is how this challenge cipher text would look like for the attacker in that experiment. Whereas, if the triplet that is given to this DDH solver is a DH triplet, then the distribution of (1, 2) that this adversary is seeing is exactly the same distribution as if this adversary would have seen by participating in an instance of COA game against the El Gamal encryption process. So we will come back to that fact again. So now this adversary has to identify whether it has seen an encryption of 0 or 1 . So it submits its output . And response from the DDH solver is that, it says that it is seeing a DH triplet, if and only if the adversary EG has correctly identified whether it is 0 or whether it is 1 , which is encrypted in the challenge cipher text (1, 2). So now let us analyse the advantage, namely with how much probability this DDH solver is going to solve a random instance of the DDH problem. So I claim that if , that means this triplet is a non-DDH triplet. Then the probability that my DDH solver outputs incorrectly, namely it outputs ′ = 1, is exactly the same with which this COA attacker would have won the COA game against the symmetric-key variant of the El Gamal encryption scheme. And we have already proved that it is 1⁄2 . This is because if we are in the setting where , then as I have already proved that the cipher text, which our adversary EG is seeing, has exactly the same distribution as it would have seen by participating in an instance of COA game against the modified El Gamal encryption scheme. On the other hand, I claim that if my case is , then the probability that my DDH solver outputs ′ = 1 is exactly the same that my adversary EG wins the COA game against the El Gamal encryption scheme. And this follows from the fact that if we are in the case where , then that means the triplet that is given is a DDH triplet or Diffie–Hellman triplet, which means that the distribution of the cipher text, whichever adversary is seen is exactly the same as distribution of the cipher text that this adversary would have seen by participating in an instance of COA game against the El Gamal encryption scheme. So in summary, what we are concluding now is that, if you see the distinguishing advantage of our DDH solver, then it is exactly 1⁄2 minus the probability with which our adversary could have won the COA game against the El Gamal encryption scheme. But since I am assuming that DDH assumption holds in the underlying group, then I know that the distinguishing advantage of any DDH solver is upper bounded by some negligible probability. So I do not know the plain text , but I know the public key and I have an El Gamal encryption of that unknown plain text , which consists of two group elements, which I am denoting by and . And as per the syntax of the El Gamal encryption process, will have this property, so 1 is the underlying randomness used by the sender. And in the same way, imagine that I have an El Gamal encryption or cipher text of an unknown message , again consisting of two group elements. Now suppose I multiply the first component of both the cipher texts. And independently I multiply the second component of both the cipher texts. And this will produce two group elements, which will mathematically have the following property. The first group element will be nothing but to the power randomness used in the first cipher text plus the randomness used in the second cipher text. And the second component will be the product of the two plain texts, multiplied by to the power public-key times the summation of the two randomness. And if you look closely, this is nothing but you can imagine as if this is an El Gamal cipher text for the plain text , under the randomness 1 + 2 . And that is why I say that my El Gamal encryption process is multiplicative homomorphic. The reason it is multiplicative homomorphic is that if I multiply two El Gamal cipher texts, then even without knowing the underlying plain texts (I stress I do not know the underlying plain texts and underlying randomness 1 and 2 , which are used individually), I end up getting an El Gamal cipher text of a related plain text, namely , under some unknown randomness, namely 1 + 2 . So this is kind of a very interesting property of El Gamal encryption process. And later on
Log in to save your progress and obtain a certificate in Alison’s free Cryptography: Public-key Cryptosystem online course
Sign up to save your progress and obtain a certificate in Alison’s free Cryptography: Public-key Cryptosystem online course
Please enter you email address and we will mail you a link to reset your password.