There are many variants of the computational Diffie-Hellman problem that are necessary to provide security of many cryptographic schemes. Two of them are the square Diffie-Hellman problem and the square root Diffie-Hellman problem. Dongyoung Roh and Sang Geun Hahn proved that these two problems are polynomial-time equivalent under a certain condition [17]. In this paper, we generalize this result. We introduce the $l$-th power Diffie-Hellman problem and the $l$-th root Diffie-Hellman problem and show that these two problems are polynomial-time equivalent for $l=O(\log p)$ under a condition similar to that of [17], where $p$ is the order of the underlying group.
여러 암호학적 스킴에 안전성을 제공해 주는 계산적 디피-헬만 문제에는 여러 종류가 있다. 그 중 두 가지가 제곱 디피-헬만 문제와 제곱근 디피-헬만 문제이다. 노동영, 한상근은 이 두 문제가 특정 조건 하에서 다항식 시간 동치임을 증명하였다 [17]. 이 논문에서는 이 결과를 일반화하였다. $l$-제곱 디피-헬만 문제와 l-제곱근 디피-헬만 문제를 소개하고, 기저 군의 오더를 $p$라 할 때 이 두 문제가 $l=O(\log p)$에 대해 특정 조건 하에서 다항식 시간 동치임을 증명하였다.
