Baby-step giant-step and kangaroos
Pollard's rho is the algorithm parameters are sized against, but it is not the only square-root method. Baby-step giant-step is deterministic and simple, and pays for it in memory. Pollard's kangaroos solve a different problem, a logarithm known to lie in a short interval, in time that depends on the interval rather than the group.
- Problem
- Given P and Q = kP, find k; for kangaroos, with k known to lie in an interval of width W
- BSGS cost
- At most 2⌈√n⌉ group operations and ⌈√n⌉ stored points
- Kangaroo cost
- About 2√W group operations with a few stored points; parallelises linearly
- Measured here
- BSGS 1.49√n on average; kangaroos 2.42√W on average
- Matters for
- Short or structured exponents, partially leaked keys, and small-message decryption in exponential ElGamal
Baby steps and giant steps
Shanks's idea, from 1971, is to write the unknown k as k = im + j with m = ⌈√n⌉ and 0 ≤ i, j < m. Then Q − imP = jP, and the two sides can be computed separately:
- Baby steps. Compute 0, P, 2P, …, (m−1)P and store them in a hash table keyed by the point, with j as the value.
- Giant steps. Compute Q, Q − mP, Q − 2mP, … and look each one up in the table.
- Match. When Q − imP is in the table as jP, the answer is k = im + j.
Nothing is random. The algorithm finishes in at most 2m group operations, and the table holds m points. That table is the whole problem at cryptographic sizes: for a 256-bit curve m is 2128, and no computer stores 2128 points. Rho does the same work, up to a constant, with almost no memory, which is why it and not BSGS is the baseline for key sizes.
On the curve from the rho worked example, y2 = x3 + 3x + 6 over F10,007, with a group of prime order n = 10,039, the table holds m = 101 points. Over 200 random targets, BSGS used 150 group operations on average, and never more than 199 against the bound of 202. That is 1.49√n: m baby steps, and on average m/2 giant steps. Each result was checked by multiplying P by the answer.
The trade can be moved. Storing more baby steps means fewer giant steps, and when many logarithms are needed in the same group the table can be built once and reused, which makes each further logarithm cheaper. With little memory and many targets, the parallel collision search of van Oorschot and Wiener is the better choice.
Kangaroos: a logarithm in an interval
Sometimes the attacker knows more than the group. The exponent may be known to lie between 0 and W, for example because it was generated too short, or because a side channel leaked its top bits. BSGS adapts to an interval directly, with √W memory. Pollard's lambda method, from 1978 and better known as the kangaroo method, does it in about 2√W time with almost none.
Two kangaroos jump through the group. The tame kangaroo starts at a known multiple of P, the top of the interval, WP. The wild one starts at Q = kP. Each jump adds sP to the current point, where the jump length s is chosen by a fixed function of the point itself, so a kangaroo's path depends only on where it is. Each kangaroo records how far it has travelled. Because the paths are deterministic, once the wild kangaroo lands anywhere the tame one has already been, it follows the tame one's footprints from then on. Setting the two positions equal gives W + dtame = k + dwild, so k = W + dtame − dwild.
The jump lengths are powers of two whose mean is about √W/2. That is small enough that the wild kangaroo, following behind, cannot jump over the tame one's whole trail, and large enough that it catches up quickly. For an interval of width W = 1,000 in the same group, that meant 7 jump lengths, 1 to 27−1, with mean 18.1.
Over 200 secrets drawn from [0, 1,000), the two kangaroos together used 76 group operations on average, with median 78 and maximum 144. That is 2.42√W, close to the 2√W that the analysis predicts, and it did not depend on the group order of 10,039. Every answer was checked by scalar multiplication.
Van Oorschot and Wiener showed how to run many kangaroos in parallel with distinguished points, for a linear speedup. Pollard's 2000 paper analyses several variants. Galbraith, Pollard and Ruprai later lowered the constant below 2 by using more kangaroos and exploiting the group's cheap negation.
Where these matter
- Short exponents. A secret key or nonce drawn from fewer bits than the group size falls to kangaroos in time about 2b/2 for b bits, whatever the group order. Using a 128-bit exponent in a group of 256-bit order leaves 64-bit security, not 128.
- Partial leaks. If a side channel reveals some bits of a key, the rest lies in an interval or a union of intervals, and the kangaroo cost is set by what remains unknown.
- Exponential ElGamal. Schemes that encrypt m as mP, for homomorphic addition, have to solve a discrete logarithm to decrypt, and rely on m being small. BSGS with a precomputed table is the usual decryption method.
- Composite orders. Inside Pohlig–Hellman, each prime-order piece is solved with BSGS or rho, so the cost is set by the largest prime factor of the group order.
None of this changes the security of a properly generated key in a prime-order group. The exponent is uniform over the whole group, the interval is the group, and every square-root method costs about √n, which is the bound Shoup proved no generic algorithm can beat.
Primary sources
- J. M. Pollard, "Monte Carlo methods for index computation (mod p)", Mathematics of Computation 32 (1978)
- P. C. van Oorschot and M. J. Wiener, "Parallel collision search with cryptanalytic applications", Journal of Cryptology 12 (1999)
- J. M. Pollard, "Kangaroos, Monopoly and discrete logarithms", Journal of Cryptology 13 (2000)
- S. D. Galbraith, J. M. Pollard and R. S. Ruprai, "Computing discrete logarithms in an interval", Mathematics of Computation 82 (2013)