In this lecture we'll see our first concrete example of a public key encryption scheme, and we'll explore a public key encryption whose security relies on, but is not equivalent to, the discrete logarithm problem. We'll begin by recalling the Diffie-Hellman key exchange protocol. So recall that that protocol began by having one party run a group generation algorithm to obtain a description of a cyclic group, capital G, whose order we'll denote by q, along with the generator, g, of that group. That party will also then choose a uniform exponent x and compute the value h1 equal to g to the x. And they'll send the parameters they just chose along with the element h1 as the first message of the protocol. The other party will choose a uniform exponent, y, and compute the value h2 equal to g to the y. And they'll send that back as their second message. At this point, that party will be able to compute a key k, equal to h1 to the y. Now, let's not stop there. Let's assume now that this party also wants to send some message to the other party, and the natural way to do that is to use the key k that they've just derived to encrypt that message. We're going to do encryption here in a way that might look a little bit odd, but which turns out to be secure because it's equivalent to what goes on in the one time padding encryption scheme that we saw way back in week one. That is, what we're going to do is we're going to take our message, m, which we'll assume to be in the group g. And we'll simply multiply k and m together and send the result as the next message in the protocol. Now, again, this may look unusual, but if we treat k as a uniform group element, which is what it's going to look like from the point of view of an attacker, eavesdropping on this protocol. Then multiplying the message m by a uniform group element gives us an element c2 which is itself a uniform group element, and therefore contains no information about m. This was really just an intuitive argument, but the point I'm making here is simply that this form of encryption using k is indeed secure, as long as you use k in this way only once. Now at the other end, the initial party can also compute the shared key k, they do it by computing h2 to their secret exponent, x and at that point, they can recover the message m by taking the component c2, the final message from the other party, and simply dividing by k. If we look at it just a little bit differently, we have an encryption scheme. And this is called the El Gamal encryption scheme. That is, we can view the first portion of the algorithm that the party ran as the key generation algorithm. That is, they ran some algorithm that gave them a pair of public and private keys. With the public key being their initial message to the other party, that is the parameters along with h1, and the private key being their secret exponent x. The algorithm being run by the other party simply becomes the encryption algorithm. So to encrypt a message m, what they do is pick a secret exponent, y, compute the value h2, compute the value k, and then compute the value, k times m. And then both h2 and k times m to the other party. You'll see that those two messages can be simply grouped together. And they become the cypher text. And finally, the other, the other party can run a decryption algorithm, which I've boxed here, to recover the message m. If we want to view it more formally, just in terms of something more like pseudo code, we have the following scheme. Key generation runs the group generation algorithm to obtain parameters G, q and g. We then choose a uniform exponent x, and the public key consists of the parameters and the value g to the x, that was simply h1 from the previous slide. And the matching private key is the exponent x. To encrypt a message, m, given a public key of the form G q g h. What we do is we simply choose a uniform value y, and let the ciphertext be equal to g to the y, h to the y times m, so g to the y here corresponds to the value h2 on the previous slide, h to the y times m is simply packaging together derivation of the key, along with multiplication by the message m. To decrypt a ciphertext consisting of two components, c1 and c2, all you do is output c2 divided by c1 to the x, where x corresponds to the secret key. And it's easy to check, as we did on the previous slide, essentially that this will always give the correct message in return. What can we say about security of this scheme? Well, the theorem is that if the decisional Diffie-Hellman assumption is hard relative to the group generational algorithm G then the El Gamal encryption scheme is CPA-secure. And really although you could prove it directly it follows almost directly from the security of the Diffie-Hellman key exchange protocol. Again, because the key that's effectively shared by the two parties is uniform from the point of view of an attacker, eavesdropping on the first message of the protocol, that is the public key, and the second message of the protocol, that is the first component of the ciphertext. Then when we use that key, or when the parties use that key to hide their message by multiplication, that will hide all information about the message m. One thing I just want to note here is that as we talked about in the case of key exchange itself the discrete logarithm assumption itself is not enough for public key encryption. Instead we need some stronger assumption like the computational Diffie–Hellman or decisional Diffie–Hellman assumption. Now in practice, just as in the case for Diffie-Hellman key exchange, it's common for the parameters G, q, and g to be standardized, fixed, and shared. So there's no need then to generate these parameters on your own at the time of key generation. And instead, key generation would simply consist of choosing a uniform exponent x. And letting your public key be equal to g to the x. The other thing I want to point out is that we were implicitly assuming throughout the prior slides that the message m was a group element. In practice, that's rather inconvenient. Your message m might be an arbitrary bit string, but your group might have some special representation. And any arbitrary message might simply not correspond to some valid group element. There's a very simple solution to that, and the solution is that rather than treating the message as a group element, and multiplying it by the derived key k, which is itself a group element, what we'll do instead is to derive a key. And use that key to encrypt the message using a private key encryption scheme. That is, what we'll do is let the ciphertext be equal to g to the y and then the encryption, using a private key encryption scheme, Enc prime, of the message m, using the key k where the key k is derived as a hash of the shared value H to the y. And if you think about it, this is essentially hybrid encryption. What we're doing is using some variant of the algorithm encryption scheme to share this derived key k, and then, we're using k along with a private key encryption scheme to encrypt our message. So note here that m not only doesn't need to be a group element but can be arbitrarily long and we get the efficiency, at least asymptotically, of private key encryption. Even though this is itself a valid public key encryption scheme. What about security against chosen ciphertext attacks? Let's go back to the original El Gamal encryption scheme for simplicity, where we simply treat the message m as a group element. And encrypt by, by letting the second component of the ciphertext be equal to K times m. It's not hard to see that that encryption scheme is not secure against chosen-ciphertext attacks. And this follows from the fact that it's malleable. Let's see why. Given a ciphertext c1, c2 that's the encryption of some unknown message m. What we can do is we can simply transform it to the ciphertext c1, c2 prime, where c2 prime is equal to alpha time c2, where alpha is some arbitrary constant in the group. Now because the ciphertext c1, c2 that we started with is of the form g1 to the y, h1 to the y times m, y and m are unknown here to the attacker. But we still know that the ciphertext does indeed have that form. We know that we can therefore write c1 c2 prime as g to the y, h to the y times alpha m. I've simply rearranged and moved alpha inside. And what that means is that we've started with the encryption c1, c2 of some unknown message m. And we were able to successfully transform it to an encryption of alpha m. That's exactly a malleability attack. Let's see how the attack could actually be useful in practice. So we'll assume here that the group we're working with is a subgroup of Zp star, which just means that we can treat the group G that integers rather are in this group G, because we have the integers from one to p minus 1 being inside Zp star. And therefore we know that we can treat the elements of G as integers as well. Well imagine a scenario where we have an auction taking place. And here I've shown two bidders and an auctioneer. And the way we're going to do the auction is the auctioneer is going to publish their public key. And then each bidder is going to encrypt their bid for some item. Well, the first bidder will send some ciphertext c1, c2, corresponding to their unknown bid. But now look what the second bidder can do. What they can do is they can apply the attack from the previous slide and they can send the ciphertext c1 and twice c2. Look at the effect that that has at the auctioneer. When the auctioneer decrypts the first cipher text they'll obtain some bid m and when they decrypt the second cipher text they'll recover the bid twice m. What that means that the second bidder was able not only to always out bid the first bidder but to do it always do by bidding exactly twice as much. And you can see why this would be undesirable when running an auction. We can obtain chosen ciphertext security for the agronomic encryption scheme. If we're a little bit careful in how we instantiate it when using key derivation. So if we use key derivation coupled with a CCA secure private key encryption scheme Enc prime. That is, we let the cipher text now be g to the t and Enc prime using key k of our message m. Then this scheme can be proved to be CCA secure under appropriate assumptions that actually are stronger than the decision of the Diffie-Hellman assumption, but are still reasonable and are still believed to hold. If we are willing to model our hash function H as a random oracle. Now, we haven't talked in a lot of detail about the random oracle model, but suffice it to say that this means that we treat H as a random mapping from its input, ie, group elements, to the set of keys that it outputs. And in fact this approach has been used to construct the standardized encryption schemes DHIES and ECIES. Where, one of those is based on subgroups of Zp star, and the other one is based on elliptic curve groups. So the point is that if you want to use El Gamel encryption, or a variant El Gamel encryption scheme in a setting which chosen ciphertext security is important, you do have options available. And I'll mention also that there's been some other work in the cryptographic literature on developing schemes that can be based directly on the decisional Diffie-Hellman assumption, and that don't require the assumption that the hash is a random oracle, but yet can be proven CCA-secure as well. But those seem to have gotten less traction so far in practice. That completes our discussion of the discrete logarithm-based public-key encryption schemes. And in the next lecture, we'll turn into a consideration of RSA-based public-key encryption.