Discrete Logarithm Problem is well known as a hard problem. Shoup proved the lower bounds of DL problem and related problems with respect to generic algorithms. In this paper, we will describe the lower bounds of some other variations of DL problem, like $\It{q}$-weak Diffie-Hellman Problem and $\It{q}$-Square Computational Diffie-Hellman Problem by Shoup`s sense. Any generic algorithm which solve $\It{q}$-weak Diffie-Hellman Problem requires $\Omega(\sqrt{\epsilonp/q})$ generic group operations where $\epsilon \gt 0$ is a constant probability that solves the $\It{q}$-WDH problem in generic groups of order $\It{p}$. And the lower bound on the complexity of the $\It{q}$-Square Computational Diffie-Hellman Problem is $\Omega(\radic{\epsilonp/q})$ where $\epsilon \gt 0$ is a constant probability that solves the $\It{q}$-SCDH problem in generic groups and $\It{p}$ is the largest prime dividing the order of the group.
이산 로그 문제를 시작으로 Diffie-Hellman 문제와 같은 파생된 여러 문제들이 나왔다. Shoup은 이산 로그 문제와 DH 문제, 그리고 Decisional DH 문제를 generic 알고리즘에 대해서 하계를 제시했다. 그래서 위와 같은 문제를 푸는 임의의 generic 알고리즘은 적어도 $\Omega(\sqrt{p})$ 의 연산 과정을 거쳐야 풀 수 있다는 것을 증명했다. 여기서 p는 이산 로그 문제와 DH 문제에 대해서는 군의 위수를 나누는 가장 큰 소수이고, Decisional DH 문제에서는 군의 위수를 나누는 가장 작은 소수이다. 이와 유사하게 Boneh 와 Boyen은 $\It{q}$-SDH 문제를 $\epsilon$이 적이 $\It{q}$-SDH 문제를 풀 상수 확률이고, $\q \gt 0(3\sqrt{p})$ 를 만족하는 generic 군의 위수가 $\It{p}$일 때, $\Omega(\sqrt{\frac{\epsilonp}{q})$의 generic 알고리즘 연산을 통해 풀 수 있다는 것을 증명했다. 이 논문에서는 $\It{q}$-WDH 문제와 $\It{q}$-SCDH 문제 역시 풀기 위해 $\Omega(\sqrt{\frac{\epsilonp}{q})$의 generic 알고리즘 연산이 필요하다는 것을 보였다. 따라서 q-WDH 문제와 q-SCDH 문제들을 기반으로 한 암호 스킴들이 generic 알고리즘에 대해 안전할 것이라는 얘기를 할 수 있다.
