Loading

Module 1: Public-key Cryptosystem

Notes
Study Reminders
Support
Text Version

Hybrid Public-Key Cryptosystem

Set your study reminders

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

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Foundations of Cryptography Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bangalore Lecture – 47 Hybrid Public Key Cryptosystem Welcome to this lecture. The plan for this lecture is as follows. (Refer Slide Time: 00:36) In this lecture, we will introduce Hybrid public-key encryption scheme and we will introduce KEM/DEM paradigm, and we will see an instantiation of CDH-based KEM in the Randomoracle model and DDH-based instantiation of KEM in the standard model. (Refer Slide Time: 00:49)So, let’s start with the motivation of Hybrid Public-Key Ciphers and before doing that, let us compare the public-key encryption scheme with a secret-key encryption scheme. Imagine, we are given a public-key encryption scheme, Πpub , and we are given a symmetric encryption scheme, Πpriv , then if we consider the public-key encryption scheme, the key agreement is not at all a challenge. That is what the whole motivation for the birth the public encryption process. If I am a receiver, it is suffice for me just to announce my public-key in the public domain. Anyone who wants to encrypt a message and send it to me, it can pick my public key, encrypt the message and send it to me. On the other hand, we had seen that key agreement is the biggest challenge in the symmetric key domain. Until and unless the common key is established between the sender and the receiver, we cannot use any of the symmetric key primitives. If we consider the public-key encryption scheme, the downside there is the message space has to be a finite group or a finite algebraic structure, which most cases is the group, which is kind of a restriction because, in practice, the message space should be a set of bit string. On the other hand, the message space in the symmetric keyword are binary strings. We do not require any sophisticated algebraic structure from the underlying message space for the overall security of my symmetric key encryption schemes. If we consider public-key encryption schemes, they are computationally very heavy because we have to perform modular exponentiations for instance in RSA function and in El Gamal encryption scheme. Performing modular exponentiations is very computationally expensive and heavy compared to the encryption process, decryption process that we use in symmetric key encryption scheme, which are superfast and performs operations which are of XOR operations. In the same way, the public-key encryption scheme, the cipher text expansion is huge, for instance, if you see the El Gamal encryption scheme, the plain text that you want can encrypt is a single group element, but the cipher text consists of two groups elements and padded RSA, the amount of message, which you end up encrypting is very short compared to the amount of randomness that you are actually padding. On the other hand, in the symmetric key world, cipher text expansion can be as minimal as possible using any of the so called secure modes of operation of block ciphers. So, now we can see have both pros as well as cons of public-key encryption scheme, symmetric encryption schemes, and what we can do is, we can think of somehow combining these two processes in a generic fashion and obtain a hybrid kind of encryption process where in the hybrid encryption process, which we call as EncHyb. The sender picks a random key for the symmetric key encryption scheme and encrypts it using the public-key encryption process, namely it encrypts the random key k, which it has selected and encrypts it using the public key of the receiver and once the plain text is available with the sender, the actual encryption of the plain text happens using a symmetric key encryption process using the random key, which has been picked by the sender. If we do this, what is happening here is basically the entire efficiency of the hybrid encryption process becomes almost that of the symmetric key encryption process because the actual message which we are encrypting gets encrypted using a symmetric key encryption process. The extra pay load that we are paying here is to encrypt the symmetric key which is used for encrypting the actual plain text using a public key encryption process. However in principle syntactically this whole hybrid process is still will be considered as an instantiation of public key encryption process because the key for the symmetric key encryption which the sender is using is getting encrypted by a public key encryption process. So, that is what is the overall motivation for designing Hybrid Public-Key Ciphers. (Refer Slide Time: 5:01)To make my point more clear, let us consider an instantiation of Hybrid El Gamal public-key Cipher. So, let me recall the syntax of Hybrid El Gamal public-key cipher, say Seetha wants to say to set up for her public parameter, her public key and secret key, so the public description, which is available to everyone is the description of the cyclic group, the generator, and the size of the group. To do the key setup, what Seetha does is, you can imagine that she does her part of DiffieHellman key exchange protocol once for all for every potential Ram. For every potential sender who wants to encrypt a message and send to Seetha. So, she picks her random α from the set Zq namely 0 to q-1, and that is a secret key and a public key, which is gα , which is available in the public domain, and this if you can imagine as Seetha’s contribution for the overall Diffie-Hellman key, which she wants to establish with every any potential sender in this world. Now imagine there is a sender, which has a plain text m, which it wants to encrypt and now this plain text is a bit string, it need not be an element of group. So, unlike the El Gamal encryption process where the actual plain text, which sender could encrypt and send to Seetha should be an element of group, now the plain text is a bit string. Now, to encrypt this plain text m, what the sender does is, it picks a random element from the group which are noted by and it encrypts this message using the El Gamal encryption process. So, it computes the cipher text c1, c2 where c1 can be interpreted as sender’s contribution for the Diffie-Hellman key exchange protocol, namely gβ , where β is a randomly picked, and c2 is the actual encryption of this random using the common Diffie-Hellman key gαβ . Now, that is not the encryption of the message, so till now what sender has done basically the c1, c2, that sender has sent to Seetha is an encryption of the random , but the goal of sender is to encrypt the plain text m, so what we do here is we assume that apart from the description of the cyclic group, generator, group order and so on, we assume that we have a description of a key derivation function H publicly available and assume that the key derivation function maps the elements from the group g to the key space of the symmetric key encryption scheme, that sender is now going to use. So now, what sender is going to do is, sender knows that by sending c1, c2, to Seetha. Sender knows that Seetha also will end up getting the common key gαβ and assuming the DDH assumption is true in the underlying group, this key g αβ is going to be a random element from the group from the view point of a computationally bounded adversary. So what sender can now do is, it can derive a bit string key for the symmetric encryption process by applying a key derivation function to this random element and that key is used to now encrypt the plain text m, which is a bit string and that is a actual encryption of the plain text m, which sender wants to encrypt. The decryption at Seetha’s end happens as follows. So for decryption, Seetha also needs to recover the same , which sender has used to derive the symmetric key k and can be obtained by decrypting c1, c2 as per the syntax of El Gamal encryption scheme and once is recovered by Seetha, what Seetha can do, she can also apply the same publicly available key derivation function on and once is recovered, she can decrypt the c component of the cipher text as per the decryption algorithm of the symmetric key encryption process and recover m. So, that is how you can interpret a hybrid version of El Gamal public-key cipher. So pictorially what is happening is here that as I said earlier c1, c2 is the public key encryption of the symmetric key, whereas the c component here is the actual private key encryption of the plain text. However, if you pause here for a moment, the above idea of encrypting the random group element by sender and deriving a key from it is an overkill. So, what is happening here is sender is using a random group element , encrypting it as a whole using El Gamal encryption process, and then deriving that a symmetric key. So that is an overkill here. A close observation tells you that it is suffice for the sender to just send gβ . It need not have to send c2. It is suffice for the sender to just send gβ. Because the sender knows that if it sends gβ , which can be reviewed as if it sender is sending his part of the Diffie-Hellman key exchange protocol message, then it knows that by sending gβ , both Seetha and Ram will end up agreeing to g αβ and assuming DDH assumption is true in the underlying group, we know that g αβ will be random in the view point of the adversary.Hence the key k can be derived from the g αβ instead of deriving the key from the random element , because if we do this instead of using the approach that we have seen till now, we do a saving here. We need not have to pick the random element and we do not need to encrypt , hence we do not need to send c2, and overall size of the cipher text will get significantly reduced and that will also lead to saving in the bandwidth as well, because if we do not need send the c2 that means we do not need to send an extra group element to encrypt the message. (Refer Slide Time: 11:22) Even though we have seen an instantiation of Hybrid El Gamal cipher here, it turns out that this approach is an overkill. So what we are going to do now, as we are now motivated by the discussion here that, it suffices for the sender here to just send gβ and derive a key from gβ , what we are going to do is we are now going to derive a new primitive, which we call as Key-Encapsulation mechanism or KEM and then we will see that how we can get more efficient Hybrid encryption using this KEM. So, to make my point clear the naïve way of Hybrid encryption that we have seen now is just in the context of Hybrid El Gamal is as follows. So, at the encryption end what we were doing is the sender was picking a random key for the symmetric key and it was getting encrypted by the public key of the receiver to derive the cipher text c, which can be considered as an encryption of the symmetric key. And actual encryption of the message was done using the key k and this was kind of a twostage approach, where we were first choosing our random symmetric key and then using it for the public key encryption process. More efficient approach will be done using a primitive, which we are going to define it soon which we call as key encapsulation mechanism where both these two things are done in a single shot in a single stage. And the advantage here is that not only it is conceptually simpler, but in many cases it is more efficient and to understand that how exactly KEM is going to be efficient compared to this two stage approach, you can see what we have seen just now in the context of Hybrid El Gamal. The naïve way of implementing El Gamal the sender was picking a random deriving the key and was whole encrypted using the El Gamal encryption process. But later we argued that the sender need not have to do that. It can carry out Hybrid Encryption even by just sending gβ to the receiver. Now, it suffice for the underlying key derivation function to be a special type of function, which distributes the group element almost evenly among the elements of the key space of the symmetric key encryption process. What I mean by that is, if I consider if this is my group g, and if this is my set K, and the number of elements, which map to a candidate element from this key space, the number of group elements which map to this one candidate element from this key space should almost be the same. There should not be any bias in the distribution or in the mapping by which this function H is mapping the elements of the group to the elements of the key space of my symmetric key encryption process. If I assume that my underlying key derivation function has that kind of smoothing effect, then it is suffice for me to just remain in the standard model and claim the security of this key encapsulation mechanism, just based on the DDH assumption. Now, you can see the importance of assumptions that we are making throughout this course. Same construction here can be proved secure in with weaker hardness assumptions, namely CDH assumption. But with a more powerful properties from the underlying hash function, namely assuming it is acting as a Random-oracle whereas if you do not want to model your underlying hash function as a Random-oracle, you want to model it as a special type of smooth distributing function, then you need to have a more powerful hardness assumption in your underlying group, namely you need to have the DDH problem difficult to be solved in your underlying group. So, that brings me to the end of this lecture. Just to summarize in this lecture, we have introduced Hybrid encryption process and we have discussed the CPA-security of Hybrid encryption process. We also saw a generic construction of how to combine a CPA-secure or a COA-secure key encapsulation mechanism along with any COA-secure symmetric key