1
$\begingroup$

I'm trying to understand how/why Shanks' algorithm solves the discrete log problem $y=g^x \bmod p$ faster than a brute force search does. Any explanation would be great.

$\endgroup$
2
$\begingroup$

Shanks' algorithm—also known as baby-step, giant-step, or BSGS, and known well before Shanks (English translation)—does not solve the discrete log problem faster than a brute force search, because it is an example of a generic or brute force search algorithm. Actually it's costlier than other generic algorithms like Pollard's $\rho$, in the standard area*time cost metric that serves as a good proxy for number of joules or number of rubles you would have to spend on the computation.

Fix a group $G$ and an element $g \in G$ of prime order $\ell$. Suppose you can compute the functions $(a, b) \mapsto a \cdot b$, $a \mapsto a^{-1}$, and $(a, b) \mapsto [a = b]$ on elements of $G$; that is, you can compute the group operation and inverse, and you can test elements for equality. If $h = g^x$ for a uniform random exponent $x$, how can we find $x$?

This setting—where you can compute products and test equality but you know nothing else about $G$—is the generic setting; attacks in this setting are sometimes called generic attacks or brute force attacks. If we had specific knowledge about $G$, like we do when $G = (\mathbb Z/p\mathbb Z)^\times$ for prime $p$, we might have better attacks, like index calculus with the NFS. But we are in the generic setting.

Naive approach. One option is to try $x = 0$ and check whether $h$ is $1$, then try $x = 1$ and check whether $g$ is $h$, then try $x = 2$ and check whether $g^2$ gives $h$, then try $x = 3$ and check whether $g^3$ gives $h$, etc. If $x$ is uniformly distributed, the expected number of trials is $\ell/2 = O(\ell)$. To save effort in each trial, rather than computing $g^k$ afresh each time, we can store state $s_k = g^k$ and update it by $s_{k + 1} = s_k \cdot g$ with a single multiplication. This is the naivest approach. Can we do a better brute force attack?

Pairwise grouping. Consider grouping the trials into pairs:

  • Is $h$ either $1$ or $g$?
  • Is $h$ either $g^2$ or $g^3$?
  • Is $h$ either $g^4$ or $g^5$?
  • Is $h$ either $g^6$ or $g^7$?

If we succeed on the $k^{\mathit{th}}$ trial, we need only determine whether $x = 2k$ or $x = 2k + 1$. The expected number of trials is $\ell/4$, plus a little extra work at the end. Of course, each trial costs twice as much as before, so this doesn't win anything yet.

Common criterion. Rather than compare $h$ to $g^{2k}$ and $g^{2k + 1}$, we can compare $h g^{-2k}$ to $g^0 = 1$ and $g^1 = g$, so that each trial performs the same test.

  • Is $h$ either $1$ or $g$?
  • Is $h g^{-2}$ either $1$ or $g$?
  • Is $h g^{-4}$ either $1$ or $g$?
  • Is $h g^{-6}$ either $1$ or $g$?

Once we have found $k$ and $\alpha$ so that $h g^{-2k} = g^{x - 2k} = g^\alpha$ and thus $x - 2 k \equiv \alpha \pmod \ell$, we can solve for $x$ as before. The expected number of trials is still $\ell/4$, but we can precompute $g^{-2}$, and then keep a running state $s_k = h g^{-2k}$ which we can update to $s_{k + 1} = s_k \cdot g^{-2}$ by a single multiplication. The expected number of trials is about half the naive algorithm, and the number of multiplications per trial is the same, so the expected number of multiplications is $\ell/4$, half that for the naive algorithm. Of course, we have to do two equality comparisons for each trial, but an equality comparison is probably cheaper than a multiplication.

Wider grouping. If a table lookup had the same cost as an equality comparison, we could make a table of $m$ different entries by precomputing $1, g, g^2, g^3, \dots, g^{m - 1}$, precomputing $g^{-m}$, and then searching as before:

  • Is $h$ in the table $\{1, g, g^2, \dots, g^{m - 1}\}$?
  • Is $h g^{-m}$ in the table $\{1, g, g^2, \dots, g^{m - 1}\}$?
  • Is $h g^{-2m}$ in the table $\{1, g, g^2, \dots, g^{m - 1}\}$?
  • Is $h g^{-3m}$ in the table $\{1, g, g^2, \dots, g^{m - 1}\}$?

Once we have found $k$ and $\alpha$ so that $h g^{-k m} = g^{x - k m} = g^\alpha$ and thus $x - k m \equiv \alpha \pmod \ell$, then we can solve for $x$ as before. Also as before, we can update the state $s_k = h g^{-km}$ with one multiplication $s_{k + 1} = s_k \cdot g^{-m}$. The expected number of trials is $\ell/(2m)$ and the cost of each trial is (a) one multiplication and (b) one table lookup. Thus the expected number of multiplications and table operations is $O(m + \ell/m)$, which is optimized by $m = \sqrt\ell$.

Caveat. In real computers, storing tables costs energy and table lookups cost more time and energy than equality comparisons. So BSGS's apparent ‘cost’ of $O(\sqrt\ell)$ multiplications, which seems to be an improvement on the naive algorithm's $O(\ell)$, is misleading in practical terms because it uses an unrealistic cost model where storage is free and an equality test costs the same as a table lookup. Pollard's $\rho$ is a generic brute force algorithm that actually improves the cost in realistic cost models to $O(\sqrt\ell)$: it too runs in $O(\sqrt\ell)$ computation time, but it has constant space requirements and no table lookups, and as a bonus it can be parallelized to take advantage of extra die area to speed it up without changing the net cost.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.