And assuming that the key agreement has been achieved, the second problem that is addressed by the cryptography, the second core problem, I should stress here, it is not the case that secure communication is the only problem, the second core problem addressed by cryptography is secure communication. So, the setting here is the following; we will assume that Sita and Ram have already executed the key agreement protocol over the internet, and they have agreed upon a common key.

And now using this common key, we would require Sita and Ram to come, we would require some algorithms which are publicly known, according to which Sita can convert or encrypt her message into some garbled text and communicate to Ram. Ram should be able to convert back those scrambled text back to the original contents using the same key.

By secure communication here I mean that, if there is a third party or Ravana, who knows the public description of your algorithm but does not know the value of the key then even after observing the communication happening between Sita and Ram, the third party should not be able to come up with the original messages.

So, it turns out that there are two kinds of, two classes of cryptographic algorithms which we use. The first category is that of private key or symmetric key encryption. In the symmetric key encryption, the setting is the following: It will be ensured that a common key is already shared between Sita and Ram by some mechanism, say, by running a key agreement protocol and no one else apart from Sita and Ram knows the value of that key.

Now, if that is the case assuming this setup has been done, the way symmetric encryption works is as follows. So, imagine Sita has some message, it could be an email, it could be just a hi message, it could be anything. She has some message which is abstracted as a binary string, we call her message as plain text. We want to design an algorithm which we call as an encryption algorithm which takes a message m and the key k both of which are binary strings. And it should produce another binary string which we call a ciphertext.

The reason it is called symmetric key encryption is because of the symmetry, namely, the same key is used both for encrypting the message as well as for decrypting the message.

So, the analogy could be that, assume Sita and Ram have already exchanged a key for a physical lock. If Sita has a message, she can take a box, keep her message inside, close the box with the lock using the key she has, then send it to Ram. As long as someone does not have the key, they cannot open the box.

But how at the first place they can do that? Because everything will be now happening over a public channel. It is not the case that Sita and Ram knew beforehand in advance.

So, it was a folklore belief that it is not possible to agree upon a common key by interacting over a public channel. But the Turing Award winner, Diffie and Hellman, proved this belief to be incorrect by coming up with their seminal key exchange protocol.

So, the main idea used in their key exchange protocol is the following. They observed that there are plenty of tasks in this universe which are asymmetric, they are asymmetric in the sense, they are very easy to compute in one direction but extremely difficult to reverse back the effect of that action.

To begin with, both Sita and Ram will be starting with some common publicly known color. And now, what they will be doing is the following. They will prepare independently some secret mixtures. So, Sita will prepare her secret mixture independently and Ram will be preparing his secret mixture independently, by adding a secret color, individually and then they will publicly exchange their mixtures.

And now of course, he is seeing the public mixtures being exchanged. Now, what is the goal? The goal for Sita and Ram is to come up or agree upon a common mixture which should be known only to them. So, whatever Ram’s mixture that Sita has received, she takes that and adds whatever components she has added to prepare her secret mixture.

What about a third person, an attacker, who has monitored the communication? Will he be able to compute the final mixture? Well, for the adversary or for the third person to compute, he should know one of the secret components added by Sita or Ram. Assuming that separation of mixtures is difficult, an outsider cannot discern the secret ingredients.

If any of these values is learned by the attacker, he can easily compute the common mixture. But for learning these values, he faces the hardest task of solving discrete logs, which underpins the security of this protocol.

If we instantiate this protocol with my group being ℤ for a large prime number, then, using the current best computing speeds, it will take years to solve a random instance of discrete log, ensuring the effectiveness of this protocol.

To summarize, in this lecture, we introduced the problem of discrete log and saw that in some groups, solving discrete log might be very easy; in some groups, it is conjectured that solving a random instance of discrete log is extremely difficult. Using such groups allows the design of algorithms for key agreement.