introduction

Today, I thought it would be fun to click 5 random links starting from the Wikipedia page on Markov chains and try to learn about or just comprehend what the topic ended up being. In the spirit of Markov, to do this, I generated 4 random numbers from 1 to the number of link elements on each page and was delighted to end up on a page titled Pollard’s kangaroo algorithm. Pollard’s kangaroo algorithm is a way to solve the discrete logarithm problem (DLP) which is given as follows:

Find \(x \in Z_n\) such that \(\alpha^x = \beta\) where \(G\) is a finite cyclic group of order \(n\) which is generated by the element \(\alpha\).

initial look at kangaroo algorithm

Looking at the steps to the algorithm was puzzling. For each step, I noted down some questions about it.

1. Choose set of integers in which to check for a solution
2. Define a pseudorandom function mapping elements of a group S, to the group of integers from step 1. S should be chosen so that it has an average of rougly the square root of the range of integers to check. *What is S, how do we choose it, why should it have the average property??
3. choose an integer N and compute first sequence of group elements. 
x_0 = alpha^b
x_{i+1} = x_i * alpha^(f(xi)) * how do we choose N, why are we taking alpha^b, what even is alpha and beta in this again?

As you can see, I wasn’t following too well at this point. While it sort of made sense that we are computing powers of alpha, why this pseudorandom generation function of a seemingly arbitrary set? Well, let’s just continue on and see if it makes more sense…

4. d = sum from i=0 to N-1 of f(x_i). This means x_N = x_0 * alpha^d = alpha^(b+d) * why is this relevant? What is the importance of d?

Still not sure about these steps, but we’ll turn to the second half of the algorithm.

5. A second sequence is computed, with y_0 = beta. Each element is y_{i+1} = y_i * alpha^(f(y_i)) *hmm, seems to be similar to set 1, why these steps though?
6. d is ocmputed in the same manner as the sum from i=0 to n-1 of f(y_i) such that y_i = beta*alpha^(d_i).

Now, for the final step

The algorithm terminates either if there is
1. Collision: if y_j = x_N for some j, then x = b+d-d_j and the DLP is solved
2. Exceeding bound: if d > b-a + d, algorithm failed. Change S or f

I was stumped. The steps at this point honestly made no sense and it was easy to keep losing track of which variables meant what.

circling back

Nearly always I find the hardest question to answer is not how something works but why it works [1]. However, the why is hard to answer without the how so the initial legwork is not for nothing. So how and why do these steps help to solve the DLP?

Let’s take an example and explain what each step is actually doing.

Example: Let us have a group \(G\) of order \(n\) generated by \(\alpha\). We want to find the \(x\) such that \(\alpha ^ x = \beta \mod n\).

  • Choosing a set \(S\) and defining a map \(f\)

Let’s say we want to search for a solution in the range of \([a,b] = [0,100]\)

Let \(S = {1,2,4,8,16,32,64}\). This way, the average of the set is roughly \(10 \approx \sqrt{b-a}\). We choose this set so that the leap cover the interval efficiently. This was the first “aha” moment. The set S defines the “jump sizes” of moving around the interval from \([a,b]\) in checking for solutions!

Finally, for this first step, let’s define a function \(f\) which will map numbers from \(G\) to \(S\). The pseudorandomness helps avoid predictable patterns that could miss the logarithm.

image

  • The tame kangaroo: computing the first sequence \({x_i}\)

Let’s now use this information to compute a sequence of length \(N\). We will start with \(x_0 = \alpha^b \alpha^{100}\). The pseudorandom function \(f\) then determines the size of each jump. The sequence is generated as follows:

\(x_1 = x_0 \cdot \alpha^{f(x_0)}\)

\(x_2 = x_1 \cdot \alpha^{f(x_1)} = \alpha^b \cdot \alpha^{f(x0) + f(x1)}\)

…

\(x_N = \alpha^b \cdot \alpha^d\) where \(d = \sum_0^{N-1} f(x_i)\)

Here, \(d\) can be thought of as the total “jumping distance” in this sequence. Essentially, we’re exponentially jumping through the group in a random way starting from the highest number.

  • The wild kangaroo: computing the second sequence \({y_i}\)

Now, we repeat the process above but start from a different place: \(y_0 = \beta\)

This time, instead of just keeping track of the total distance, we’ll keep track of the cumulative sum of jumping distances at each step \(d_i\).

  • Collision: solution to the DLP

When \(y_j = x_n\) for some \(j\), this means a collision between the “two kangaroos hopping around the group” has been found. Since \(x_N = \alpha^{b+d}\) and \(y_j = \beta \cdot \alpha^{d_j}\), we can equate these two and dividing by the \(\alpha\) term in both sides we have that \(x = b+d-d_j\) and the DLP has been solved.

[1] Exceptions to this include lay ups in basketball and complicated board games that my brother enjoys

building further intuition

The key idea here is that we are sampling two different paths of exponentiation in the group. The way that the paths are constructed means that if there is a collision, it tells us something about the relationship between \(\alpha\) and \(\beta\) through exponentiation. Given the data collected through the movement, we then can use it to reconstruct how to get to a solution where \(\alpha^x = \beta\).

Through the explanation of this algorithm, Pollard kept referring to the tame and wild kangaroos. While I find kangaroos highly intriguing creatures, I ignored his Aussie analogy when first reading about the algorithm. However, thinking about two kangaroos bouncing around the group, each collecting information about it and then meeting at a convergence point and sharing their findings to come up with a solution helped me visualize how this algorithm could work. It’s a very friendly thing.

Kruskal Count

A related idea that relies on the same core idea of path convergence from different starting places within a group is called the “Kruskal Count”. The classic example goes as follows: imagine you deal out a deck of cards at a table. Select a random card and jump forward according to it’s value. Repeat this procedure N times and then place a dollar there. Then, let a friend choose 10 different starting cards and repeat the random walk procedure. 80% of the time, the person will land on the dollar. At each step, your friend has a chance to reach a card you had visited at which point the paths will converge.

In Pollard’s algorithm, the same theory is applied. We can think of the “deck” as a cyclic group (which works if you consider going back to the start of the deck once you reach the end – just like going back to 0 once you reach N of a group mod N), and the step size is whatever the pseudorandom function mapping from G to S gives you!

applications in cryptography

Many cryptographic systems including Diffe-Hellman key exchange, ECC, and DSA are based off the understanding that solving the DLP is computationally infeasable for large groups with brute force methods. So could some optimized bouncy kangaroos pose a problem for these encryption schemes?

The time complexity of the algorithm is \(O(\sqrt{b-a})\) compared to the brute force solution which is of time \(O(b-a)\). However, for very large groups, even using the kangaroo algorithm is very expensive. I was curious why groups with a prime order were chosen and how this made solving the DLP harder. There are many reasons why prime numbers are chosen for cryptography, but here I believe are the ones most salient to this discussion:

  • Uniform distribution: The powers of a generator in a prime group are uniformly distributed. This means that the results of exponentiation do not clump around certain values
  • Lack of subgroups: composite number groups can contain subgroups where the DLP can be easier to solve/break down wheras since primes cannot be factored, they can’t be split into sub-problems.

Thank you for joining in this mini marsupial themed adventure. Cheers and until next time, have a great time exploring the world of ideas! 🦘