Modulo Errors

The discrete logarithm problem is the vital part of elliptic curve cryptography, but can be defined (to varying cryptographic strength) for any cyclic group:

Discrete Logarithm Problem (DLP)
Let G be a cyclic group, with operation ⊕. Let [n] represent (n-1)-fold application of ⊕ i.e., [2]g=g⊕g, [3]g=g⊕g⊕g etc.

Given g,h from G, the discrete logarithm problem is to find t such that [t]g=h.

The baby-step, giant step (BSGS) algorithm is a generic algorithm for solving the DLP- that is to say, it makes no appeal to properties of the group involved, merely calculating abstractly with ⊕. There is a theoretical upper bound to the effectiveness of generic algorithms, and BSGS approaches are of that order of magnitude.

The simplest demonstration of BSGS (the original by Shanks) assumes that g generates G, with both of known order n: recall that the group order is simply the number of elements it contains, whereas the order of an element g is the least n such that [n]g=id_G, should such a value exist. The order n of an element always divides the order of the group N, with equality when g generates G. Between the two there is also the exponent, the least value e such that [e]g=id_G for all g in G; for cyclic groups this is N, but for products of cyclic groups (the structure of groups of rational points) it is the lowest common multiple of their respective orders, and thus, although a divisor of N, may be significantly smaller than it.

So, if we can find an order m rational point on a curve, we know that the cardinality of the group of rational points is zero modulo m. By testing random points and taking the lowest common multiple of their order we can usually find the exponent e of the group. With luck, but not always, this will be large enough that when combined with bounds on the cardinality the latter is established exactly (as with modular information in the SEA algorithm).

But it is no good attempting to do so using an algorithm that requires the order of the point! There are BSGS algorithms for the DLP which can handle unknown order, for a given g we can apply these to solve for h=id_G in the cyclic group generated by g. Provided the algorithm gives the minimal t such that [t]g=h=id_G in G=<g>, then t is the order of g.

One such algorithm, by Terr, is given in Cohen and Frey’s Handbook of Elliptic and Hyperelliptic curve cryptography (my current bible!) It relies on the following observation:

Let T_n be the nth triangular number: that is, defined by the recursion T₁=0, T_n+1=T_n+n.

Then any non-negative integer t, there are unique integers j and k with t=T_j+1-k with 0≤k<j.

To see how, notice that there is a unique j such that t lies in the interval (T_j , … , T_j+1]=(T_j+1-j , … , T_j+1-0] and that this interval has width j so there is an appropriate choice of k.

We then suppose that t satisfies [t]g=h. Then we have [T_j+1]g=h⊕[k]g. So, instead of testing each [t] in turn until we hit equality, for a given j we need only test the ‘giant step’ [T_j+1]g against the set of ‘baby steps’ β={β_i}={h⊕[0]g,…,h⊕[i]g,…,h⊕[j-1]g. If that j yields no matches, we move to j’=j+1: by keeping track of [j]g at each iteration, the new T_j’+1 and the extra h⊕[j’-1]g are found by a single group operation each. Hence this is attractive from both storage and time complexity perspectives: we need only record the baby steps β, [j]g and a single giant step at any given iteration j, whilst the time complexity is of order t^1/2.

Terr’s BSGS variant for the DLP
Finds t such that [t]g=h for g generating G of unknown order, h from G.

Initialise β={β₀=h}, γ=δ=id_G, j=0. ((For each iteration, we have γ=[T_j+1]g and δ=[j]g)
Then loop over j as follows:

• Increment j by 1, then update:
• Set δ=δ⊕g=[j-1]g⊕g=[j]g.
• Set γ=γ⊕δ=[T_j]g+[j]g=[T_j+1]g.
• If j≥2 then
  • For s from 0 to j, if γ=β_s then return T_j+1-s
• Add β_j=β_j-1⊕g to β

I’ve implemented this generic DLP algorithm and an order-finding version (which requires you to catch g=id_G) as Maple procedures for arbitrary groups- details on that will be in the next post! BSGS-based approaches become impractical at finite field sizes well within the grasp of SEA for counting on elliptic curves; but are of interest in the higher genus case which lacks an Elkies procedure.

This entry was posted on Monday, April 2nd, 2007 at 4:53 pm and is filed under Algebraic Geometry, Algorithms, Cryptology, Group Theory, Number Theory, PhD.