Contents

Baby-step giant-step

Many of the most commonly used cryptography systems are based on the assumption that the discrete log is extremely difficult to compute; the more difficult it is, the more security it provides a data transfer. One way to increase the difficulty of the discrete log problem is to base the cryptosystem on a larger group.

Theory[edit]

The algorithm is based on a space–time tradeoff. It is a fairly simple modification of trial multiplication, the naive method of finding discrete logarithms.

Given a cyclic group ${\displaystyle G}$ of order ${\displaystyle n}$, a generator ${\displaystyle \alpha }$ of the group and a group element ${\displaystyle \beta }$, the problem is to find an integer ${\displaystyle x}$ such that

${\displaystyle \alpha ^{x}=\beta \,.}$

The baby-step giant-step algorithm is based on rewriting ${\displaystyle x}$:

${\displaystyle x=im+j}$

${\displaystyle m=\left\lceil {\sqrt {n}}\right\rceil }$

${\displaystyle 0\leq i<m}$

${\displaystyle 0\leq j<m}$

Therefore, we have:

${\displaystyle \alpha ^{x}=\beta \,}$

${\displaystyle \alpha ^{im+j}=\beta \,}$

${\displaystyle \alpha ^{j}=\beta \left(\alpha ^{-m}\right)^{i}\,}$

The algorithm precomputes ${\displaystyle \alpha ^{j}}$ for several values of ${\displaystyle j}$. Then it fixes an ${\displaystyle m}$ and tries values of ${\displaystyle i}$ in the right-hand side of the congruence above, in the manner of trial multiplication. It tests to see if the congruence is satisfied for any value of ${\displaystyle j}$, using the precomputed values of ${\displaystyle \alpha ^{j}}$.

The algorithm[edit]

Input: A cyclic group G of order n, having a generator α and an element β.

Output: A value x satisfying ${\displaystyle \alpha ^{x}=\beta }$.

1. m ← Ceiling(√n)
2. For all j where 0 ≤ j < m:
   1. Compute α^j and store the pair (j, α^j) in a table. (See § In practice)
3. Compute α^−m.
4. γ ← β. (set γ = β)
5. For all i where 0 ≤ i < m:
   1. Check to see if γ is the second component (α^j) of any pair in the table.
   2. If so, return im + j.
   3. If not, γ ← γ • α^−m.

In practice[edit]

The best way to speed up the baby-step giant-step algorithm is to use an efficient table lookup scheme. The best in this case is a hash table. The hashing is done on the second component, and to perform the check in step 1 of the main loop, γ is hashed and the resulting memory address checked. Since hash tables can retrieve and add elements in ${\displaystyle O($1)} time (constant time), this does not slow down the overall baby-step giant-step algorithm.

The space complexity of the algorithm is ${\displaystyle O({\sqrt {n}})}$, while the time complexity of the algorithm is ${\displaystyle O({\sqrt {n}})}$. This running time is better than the ${\displaystyle O($n)} running time of the naive brute force calculation.

The Baby-step giant-step algorithm could be used by an eavesdropper to derive the private key generated in the Diffie Hellman key exchange, when the modulus is a prime number that is not too large. If the modulus is not prime, the Pohlig–Hellman algorithm has a smaller algorithmic complexity, and potentially solves the same problem.^[2]

Notes[edit]

• The baby-step giant-step algorithm is a generic algorithm. It works for every finite cyclic group.
• It is not necessary to know the exact order of the group G in advance. The algorithm still works if n is merely an upper bound on the group order.
• Usually the baby-step giant-step algorithm is used for groups whose order is prime. If the order of the group is composite then the Pohlig–Hellman algorithm is more efficient.
• The algorithm requires O(m) memory. It is possible to use less memory by choosing a smaller m in the first step of the algorithm. Doing so increases the running time, which then is O(n/m). Alternatively one can use Pollard's rho algorithm for logarithms, which has about the same running time as the baby-step giant-step algorithm, but only a small memory requirement.
• While this algorithm is credited to Daniel Shanks, who published the 1971 paper in which it first appears, a 1994 paper by Nechaev^[3] states that it was known to Gelfond in 1962.
• There exist optimized versions of the original algorithm, such as using the collision-free truncated lookup tables of ^[4] or negation maps and Montgomery's simultaneous modular inversion as proposed in.^[5]

Further reading[edit]

• H. Cohen, A course in computational algebraic number theory, Springer, 1996.
• D. Shanks, Class number, a theory of factorization and genera. In Proc. Symp. Pure Math. 20, pages 415—440. AMS, Providence, R.I., 1971.
• A. Stein and E. Teske, Optimized baby step-giant step methods, Journal of the Ramanujan Mathematical Society 20 (2005), no. 1, 1–32.
• A. V. Sutherland, Order computations in generic groups, PhD thesis, M.I.T., 2007.
• D. C. Terr, A modification of Shanks’ baby-step giant-step algorithm, Mathematics of Computation 69 (2000), 767–773. doi:10.1090/S0025-5718-99-01141-2

References[edit]

External links[edit]

• Baby step-Giant step – example C source code