Baby step – Giant Step Algorithm

This is another blog post about a topic that we at the LogN team meet while doing research in the area of Zero-Knowledge. This time, the point of interest is the Baby step – Giant step algorithm.

Intro: Elliptic Curves and DLP

Elliptic curve E(F) over a field F have structure of additive group, more specific abelian group. Details of that structure demand whole another blog, interested readers is referred to references at the end of the blog.

The problem that lies in the basis of elliptic curve cryptography is:

Given two points, say P and Q in subgroup G of elliptic curve group E(Fq) over finite field Fq, find integer k such that P = [k]Q (notation widely accepted for additon on elliptic curve).

The problem cited above is called the elliptic curve discrete logarithm problem (ECDLP) and there is no known polynomial-time algorithm for solving it that can run on a classical computer. It is ”elliptic” because we are doing calculations on an elliptic curve, ”discrete” because coordinates of points are integers from a finite field, and ”logarithm” because it is analogous to classical mathematical logarithm.

The discrete logarithm problem(DLP) is also known in other cryptosystems such as the Digital Signature Algorithm (DSA), the Diffie-Hellman key exchange (DH), and the ElGamal algorithm.

There is a reason why they share the name, they represent similar problems. The difference between ECDLP and DLP is that in ECPLD we work with an additive group of the elliptic curve while in DLP one works with a multiplicative group. The DLP problem can be stated as:

Given y and g from group and integer p, find x such that y = gx (mod p).

In this blog we’ll present how one can solve DLP for prime p, similar ideas then can be applied to ECDLP. We choose this path for clarity of presentation, to avoid dealing with elliptic curves.

What makes elliptic curves useful in cryptography is that, as of today, the discrete logarithm problem for elliptic curves seems to be ”harder” if compared to other similar problems used in cryptography (intuitively, the reason is the complexity of elliptic curves). This implies that we need fewer bits to achieve the same level of security as with other cryptosystems.

Algorithm

We’ll now describe the algorithm used to solve DLP, which is, due to Daniel Shanks, called Baby step – Giant step. This algorithm can be applied to any finite cyclic abelian group. Depending on the use case some modifications are possible.

Asume we have public cyclic group G = ⟨g⟩ of prime order p. Given yG, we are asked to find value x ∈ Zp such that y = gx (mod p).

The idea behind the algorithm is often encountered idea of divide and conquare. We first calculate k = [√p]+1. Then we write:

x = x0+xk,

where 0 ≤ x0, x1p. To continue, we calculate baby steps:

gi = gi, 0 ≤ i < k.

The values gi are then stored in array X. To compute and store these values requires O(√p) time and space. We then proceed to Giant steps:

yj = y°gjk, 0 ≤ j < k.

After calculating each yj, we try to find that value in array X. If such match is found, say X[i] = yj, we have a solution to our DLP and that solution is:

x = i + j°k (mod p).

We can analyze last assertion a bit. Match X[i] = yj is equivalent to:

gi = y°g−jk

gi+j°k = y (mod p).

From the last equation, we read a solution to our discrete logarithm problem, x = i + j °k (mod p). Notice that the Giant step requires at most O(√p) time. Hence, the overall time and space complexity of the Baby step – Giant step algorithm is O(√p). This means that if we want our problem to be 2128 difficult, we need to take prime of order 2256.

Example

As an illustration, let’s take finite field F509 and take a closer look at its multiplicative subgroup G of order 127 generated by element g = 17. Further on, integer y = 438 is given and we want to find x such that:

438 = 17x (mod 509),

i.e. our task is to solve DLP. Following presented algorithm, we first calculate ceiling k = [√509]+1 = 23. Then, we proceed to Baby steps:

gi = 17i, 0 ≤ i < k.

Values gi are stored in array X which is given in table below in format i : 17i (mod 509).

Table 1. Array X in format i : 17i (mod 509).

Next step is Giant step. We calculate

yj = 438 ° g−k°j, 0 ≤ j < k,

and after each calculation try to find same value in table above. In this example, calculations gives us:
y0 = 438, which is not value from table;
y1 = 199, which also is not found in table;
y2 = 238 is in table. We memorize index of y, that is j = 2. Value 238 is calculated in Baby step for i = 13, so solution to our DLP is x = 13+2 °23 = 59. You can check that 1759 = 438 (mod 509) indeed.

Optimization can be made if one knows that g is in some subgroup of Fp. As we know here that g is in subgroup G of order 127, order of that subgroup can be used for calculating ceiling k = [√127]+1 = 12 instead of order 509 of whole group which yields k = [√509]+1 = 23. This optimization has its own cost, we have to determine the order of g.

ZKHack Challenge No.1 – step by step

CHECK IT OUT!

Conclusion

There are a lot of applications of the Baby step – Giant step algorithm, and some modifications. One limitation of algorithm is that it has O(√p) space complexity, beside O(√p) time complexity. It’s a big drawback and the reason why DLP is hard for today’s computers.

One optimization in that direction is Pollard’s Rho algorithm. Another generalization is the Pohlig-Hellman algorithm which is used when integer 2/3 p in DLP is not prime. This algorithm reduces the DLP from a group of composite order to subgroups of prime order, then solves DLP in each subgroup.

Chinese Remainder Theorem is used to reconstruct the solution to the original problem. One of the important conclusions from the Pohlig-Hellman algorithm is that DLP in group G is as hard as it is DLP in its largest subgroup of prime order (which dominates in time and space complexity). This idea lies in known Pohlig Hellman small subgroup attacks.

Code

Small Python script for our example (calculations in our example are tested in SageMath too):

Resoruces

LinkedIn Twitter Facebook

Comments (0)

Your thoughts
Name
*Your email address will not be published.

eighteen + 20 =

Interested in working with us?

Let’s find the right solution for your blockchain ideas.