This paper studies the concept and current state of the generic algorithm. Moreover, we present some generic algorithm on the reductions among the discrete logarithm related problems. Shoup proved the lower bound of the discrete logarithm problem, computational Diffie-Hellman problem and decisional Diffie-Hellman problem for generic groups. Maurer and Wolf extended Shoup’s results to the reductions of the discrete logarithm problem to the Diffie-Hellman problem. Our main result is the lower bounds on generic reductions of the $q$-WDH problem to the $(q+1)$-WDH problem. It is $\mathcal{O}(\frac{\sqrt{\epsilon p}}{q})$ where $\epsilon>0$ is a constant probability that solves the $q$-WDH problem and $p$ is the largest prime factor of group order. We also prove that the lower bounds on generic reductions of the $q$-SDH problem to the $(q+1)$-SDH problem is $\mathcal{O}(\frac{\sqrt{\epsilon p}}{q})$.
이산로그 문제와 그로부터 파생된 여러 가지 문제들을 기반으로 많은 암호 시스템들이 개발됐다. 이러한 암호 시스템의 안전성을 보장하기 위해서 이산로그와 그와 관련된 문제들의 계산 복잡도에 대한 연구가 이뤄졌다. 이러한 문제들을 푸는 알고리즘이 많이 알려져 있는데, 그것들은 기저를 이루는 그룹의 특정한 성질을 이용하는 것과 이용하지 않는 것으로 나누어진다. 물론 기저를 이루는 그룹의 특정한 성질을 이용하지 않는 알고리즘이 더 널리 적용된다. 이러한 알고리즘을 generic algorithm이라고 하는데, Shoup이 이산로그 문제와 Diffie-Hellman 문제에 대해서 generic algorithm의 하계를 보였다. 이산로그 문제와 그로부터 파생된 여러 가지 문제들 그 자체뿐만 아니라 문제들 사이의 reduction에 관해서는 아직 많은 부분이 확실히 증명되지 않았다. 문제들 사이의 reduction에서도 마찬가지로 기저를 이루는 그룹의 특정한 성질을 이용하는 알고리즘과 이용하지 않는 알고리즘이 있는데, Maurer가 Soup의 generic algorithm model을 이용해 이산로그 문제의 Diffie-Hellman 문제로의 reduction에 관한 결과를 제시했다. 이 논문에서는 generic algorithm model을 이용해 일반적인 모든 군에서 $q$-WDH 문제를 $(q+1)$-WDH문제로 Reduction 하는 것이 어렵다는 것을 보인다. 마찬가지로 $q$-SDH 문제를 $(q+1)$-SDH문제로 Reduction 하는 것이 어렵다는 것을 같은 방법으로 보인다.
