52 Things: Number 34: Describe the Baby-Step/Giant-Step method for breaking DLPs

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this blog, we discuss the Baby-Step/Giant-Step attack against DLPs. 

Baby-Step/Giant-Step is an algorithm developed by Daniel Shanks that solves Discrete Logarithm Problem (DLP), of which its hardness founded many of our mordern security protocols.

First, let's just briefly recall DLP.

Given a cyclic group $G$ of order $n$, a generator $g$ and an element of the group $h$, the DLP is to find $x$, such that 
\begin{equation}
h=g^x
\end{equation}

Now let's come back to Baby-Step/Giant-Step.

Since $n$ is the group order, so we have $0 \leq x \leq n$. Therefore we can write $x$ as
\begin{equation}
x = i\lceil \sqrt{n} \rceil + j
\end{equation}
where $ 0 \leq i,j \leq \sqrt{n}$.

So the DLP equation can be rewritten as
\begin{eqnarray}
h = g^{i\lceil \sqrt{n} \rceil + j}\\
h(g^{-j}) = g^{i\lceil \sqrt{n} \rceil}
\end{eqnarray}
The problem is transformed into finding a pair of $(i,j)$ that satisfies the new equation.

One way to do this is to precompute a table of $\{g^{i\lceil \sqrt{n} \rceil}\}$ over $0 \leq i \leq \sqrt{n}$ and $g^{-1}$. For any given $h$, we iterate $j$ for $h(g^{-1})^j$ until we find a match in our precomputed table, which essentially means
\begin{equation}

g^{i\lceil \sqrt{n} \rceil} = h(g^{-1})^j = h(g^{-j})
\end{equation}

Once a match is found, we can simply reconstruct $x$ using
\begin{equation}
x = i\lceil \sqrt{n} \rceil + j
\end{equation}

The algorithem has both time and space complexity of $O(\sqrt{n})$. Fortunate for us, this is just not good enough to tear our cryptographic life apart.