A NEW APPROACH TO THE DISCRETE LOGARITHM PROBLEM WITH AUXILIARY INPUTS
Taechan Kim and Jung Hee Cheon
Abstract
The discrete logarithm problem with auxiliary inputs is to
solve~ for given elements
of a cyclic group of prime order~.
The best-known algorithm, proposed by Cheon in 2006,
solves in the case of
with running time of
group exponentiations~( or depending on the sign).
There have been several attempts to generalize this algorithm
in the case of for ,
but it has been shown, by Kim, Cheon and Lee, that
they cannot have better complexity than the usual square root algorithms.
We propose a new algorithm to solve the DLPwAI.
The complexity of the algorithm is determined by
a chosen polynomial of degree .
We show that the proposed algorithm has a running time of
group exponentiations,
where~ is the number of absolutely irreducible factors of .
We note that it is always smaller than .
To obtain a better complexity of the algorithm,
we investigate an upper bound of and
try to find polynomials that achieve the upper bound.
We can find such polynomials in the case of .
In this case, the algorithm has a running time of
group operations
which corresponds with the lower bound in the generic group model.
On the contrary, we show that no polynomial exists that achieves the
upper bound in the case of .
As an independent interest, we present an analysis of a non-uniform
birthday problem.
Precisely, we show that a collision occurs with a high probability after
samplings of balls,
where the probability of assigning balls to the bin is arbitrary.