Lower bounds for q-WDH Problem and q-SCDH Problem on generic algorithms

Abstract

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.