Lower bounds on generic reductions among discrete logarithm related problems

Abstract

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})$.