Generalized Algorithm for DLP with Auxiliary Inputs

Опубликовано 17 августа 2016, 21:32

The DLP with auxiliary inputs is to find $\alpha$ when $g^{\alpha^i}$ (i=0,1,2,\dots,d)$ as well as $g, g^{\alpha}$ are given. Recently, numerous cryptosystems are designed on a weaker variant of this problem. One example is the strong Diffie-Hellman problem. It has been shown that the complexity of this problem is lower than the original DLP by upto $\sqrt d$ group operations when $p-1$ or $p+1$ has an appropriate divisor. In this talk, we present a generalization of this algorithm, which can be applied even when $p-1$ and $p+1$ are almost prime. We also discuss how many parameters are susceptible to this attack.