17.2. More Applications of Groups

So, let us start with the discrete logarithm definition in the context of cyclic groups. So, let G be a cyclic group and that abstract operation is o and suppose the order of the cyclic group is q that means, you have q number of elements and for simplicity and without loss of generality, I will follow that multiplicative interpretation, while giving the definition of discrete logarithm, but the definition can be easily generalized even when the underlying operation is interpreted in the additive sense.

A discrete logarithm is a mathematical concept used within cyclic groups, which basically tells you how many times you need to multiply a generator (g) to obtain a particular element (y) of the group. Here, G is a cyclic group which means it can be generated by a single element (g). If the group has q elements, then for any element y in G, there is a unique number x (the discrete logarithm) such that g raised to the power x gives you y (g^x = y). This can also be thought of similarly to how natural logarithms work with regular numbers, where log_a(b) tells you what power you must raise a to obtain b.

Think of it like a recipe: the generator (g) is like the base ingredient you start with, and the discrete logarithm (x) is the number of times you need to use that ingredient to yield a specific dish (y). For instance, if 'g' is flour, and you need 'y' as a cake, the discrete logarithm tells you how many cups of flour make up the recipe for that cake.

And interestingly, like the natural logarithms, your discrete logarithm also obeys the rules that are there in the context of natural logarithms. For instance, we know that log of 1 to the base of any a is 0 because a to the power 0 is defined to be 1 in for natural logarithms. In the context of discrete logarithms, we say that the discrete log of the identity element of the group to the base of g will be 0.

Just like natural logarithms, discrete logarithms have their own set of properties. One key property is that the discrete logarithm of the identity element (which behaves like the number 1) is 0, because any number raised to the power of 0 gives 1. So, in a cyclic group with a generator g, if you compute the discrete log of the identity element, it results in zero. Another property is that the discrete log of the product of two elements is the sum of their discrete logarithms, modulo q, which helps in simplifying calculations within the group.

Imagine a scoreboard where achieving a certain score (identity element) is like the base case of having zero points; you need to do nothing to achieve it. If you had additional points, say in a game, you could express your current score as the sum of how many points each individual action contributed to the score, similar to how we combine discrete logarithms.

So, now an interesting problem is that how easy or how difficult it is to compute the discrete logarithm. So, imagine we are given an abstract cyclic group of order q and this notation means that, the number of bits that I need to represent my q is n bits.

Computing the discrete logarithm is challenging, especially when the order of the cyclic group (q) is large. If q has a significant number of bits, this computation becomes more complicated. The discrete logarithm problem involves finding an exponent x such that g raised to the power x equals y. A naive method would involve checking every possible value of x in the range from 0 to q-1, which is computationally expensive and inefficient for large q, as this process can take an exponential amount of time.

It's akin to searching for a specific book in a massive library without an index. Imagine having to check each book one by one in a library of thousands of volumes—it can take forever! Similarly, trying to find the discrete logarithm without smart techniques is akin to that exhaustive search.

Let us focus on the running time of this algorithm. In the worst case, you may end up performing iteration over all candidate values of x. So, I can say in the worst case, the running time is order of q. But q is not a polynomial quantity in n, it is actually an exponentially large value in the number of bits that I need to represent my value q.

Using a brute force algorithm to solve the discrete logarithm problem means you try every possible power (x) until you find the one that satisfies g^x = y. However, in worse scenarios, the number of iterations needed can grow exponentially with the size of q, making it computationally infeasible for large groups. Therefore, even though brute force guarantees a solution, it is not an efficient approach due to its running time not being polynomial and leading to impractical execution times.

Think of it like trying to unlock a combination lock by trying every possible combination. If your lock has 1000 combinations, you might eventually find the correct one, but it could take a long time if you have to check each one sequentially.

So now, the next question is does there exist a better algorithm? And the answer is both yes, as well as no. Yes because as we will see soon, there are indeed certain cyclic groups where I can efficiently find out the discrete logarithm of any randomly chosen y, without doing the brute force.

While brute force methods are inefficient, researchers have identified specific types of cyclic groups where algorithms can quickly compute the discrete logarithm without the need to check every possibility. These groups have certain mathematical properties that allow for optimized calculations, making log computation faster and more feasible. However, for other groups, especially those without such properties, brute force remains one of the few viable options.

Imagine you have a special type of key for a lock that can be easily manipulated or transformed based on the lock’s unique properties. In such cases, finding the combination might be straightforward, but for a standard lock without these unique features, you'd still have to try every combination one by one.

So, now let us see some applications of the discrete log problem in the context of cryptography. So, let me tell you something about cryptography.

Discrete logarithm problems form the basis of many cryptographic protocols, particularly in public-key cryptography. The difficulty of computing discrete logarithms secures the communication between parties. Cryptographic systems like Diffie-Hellman key exchange utilize the discrete logarithm problem to create secure keys without needing to share the secret key openly. Ensuring that even if an observer knows the public information, they cannot decipher the secret communications ensures the integrity and confidentiality of messages.

Think of it as sending a locked box through the mail. You can send the box (message) locked with a special key (the algorithm), but only you and the intended recipient (e.g., Sita and Ram) have the corresponding key to unlock it. Anyone intercepting the box will see it, but without the key, they can’t access the contents.

--