Baby-step giant-step
Encyclopedia
In group theory
, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle
algorithm
computing the discrete logarithm
. The discrete log problem is of fundamental importance to the area of public key cryptography. 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.
. It is a fairly simple modification of trial multiplication, the naive method of finding discrete logarithms.
Given a cyclic group
of order 
, a generator
of the group and a group element 
, the problem is to find an integer 
such that
The baby-step giant-step algorithm is based on rewriting
as 
, with 
and 
and 
. Therefore, we have:
The algorithm precomputes
for several values of 
. Then it fixes an 
and tries values of 
in the left-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 
, using the precomputed values of 
.
Output: A value x satisfying
.
. 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 O
(1) time (constant time), this does not slow down the overall baby-step giant-step algorithm.
The running time of the algorithm and the space complexity is O
(
), much better than the O
(n) running time of the naive brute force calculation.
Group theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle
Meet-in-the-middle attack
The meet-in-the-middle attack is a cryptographic attack which, like the birthday attack, makes use of a space-time tradeoff. While the birthday attack attempts to find two values in the domain of a function that map to the same value in its range, the meet-in-the-middle attack attempts to find a...
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
computing the discrete logarithm
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
. The discrete log problem is of fundamental importance to the area of public key cryptography. 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
The algorithm is based on a space-time tradeoffSpace-time tradeoff
In computer science, a space–time or time–memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution...
. It is a fairly simple modification of trial multiplication, the naive method of finding discrete logarithms.
Given a cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
of order , a generatorGenerating set of a group
In abstract algebra, a generating set of a group is a subset that is not contained in any proper subgroup of the group. Equivalently, a generating set of a group is a subset such that every element of the group can be expressed as the combination of finitely many elements of the subset and their...
of the group and a group element , the problem is to find an integer such that
The baby-step giant-step algorithm is based on rewriting
as , with and and . Therefore, we have:The algorithm precomputes
for several values of . Then it fixes an and tries values of in the left-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 , using the precomputed values of .The algorithm
Input: A cyclic group G of order n, having a generator α and an element β.Output: A value x satisfying
.- m ← Ceiling(√n)
- For all j where 0 ≤ j < m:
- Compute αj and store the pair (j, αj) in a table. (See section "In practice")
- Compute α−m.
- γ ← β. (set γ = β)
- For i = 0 to (m − 1):
- Check to see if γ is the second component (αj) of any pair in the table.
- If so, return im + j.
- If not, γ ← γ • α−m.
In practice
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 tableHash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
. 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 O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(1) time (constant time), this does not slow down the overall baby-step giant-step algorithm.
The running time of the algorithm and the space complexity is O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(
), much better than the OBig O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n) running time of the naive brute force calculation.