A Group Action on Z(p)(x) and the Generalized DLP with Auxiliary Inputs

Abstract

The Discrete Logarithm Problem with Auxiliary Inputs (DLPwAI) is an important cryptographic hard problem to compute alpha is an element of Z(p) for given g, g(alpha),..., g(alpha d) where g is a generator of a group of order p. In this paper, we introduce a generalized version of this problem, so called the generalized DLPwAI (GDLPwAI) problem which is asked to compute a for given g, g(alpha e1), ..., g(alpha ed), and propose an efficient algorithm when K := {e(1), ..., e(d)} is a multiplicative subgroup of Z(p-1)(x) . Although the previous algorithms can only compute a when p +/- 1 has a small divisor d, our algorithm resolves the problem when neither p + 1 or p - 1 has an appropriate small divisor. Our method exploits a group action of K on Z(p)(x) to partition Z(p)(x) efficiently.