A Group Action on ℤp˟ and the Generalized DLP with Auxiliary Inputs

Jung Hee Cheon, Taechan Kim, Yong Soo Song

Abstract

The Discrete Logarithm Problem with Auxiliary Inputs (DLPwAI) is an important cryptographic hard problem to compute α ∈ Zp for given g, g α , ··· ,g α 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 α for given g, g α e1 , ··· ,g α ed , and propose an efficient algorithm when K := {e1, ··· ,e d} is a multiplicative subgroup of Z ×−1. Although the previous algorithms can only compute α when p ± 1 has a small divi- sor d, our algorithm resolves the problem when neither p +1 orp − 1h as an appropriate small divisor. Our method exploits a group action of K on Z × to partition Z × efficiently.
BibTeX
@inproceedings{cheon2013group,
  author = {Jung Hee Cheon and Taechan Kim and Yong Soo Song},
  title = {{A Group Action on ℤp˟ and the Generalized DLP with Auxiliary Inputs}},
  booktitle = {Selected Areas in Cryptography},
  year = {2013},
  doi = {10.1007/978-3-662-43414-7\_6},
}

Loading related content...

Figure