Speaker Jung Hee Cheon
Affiliation Seoul National University
Host Kristin Lauter
Date recorded 29 June 2010
The DLP with auxiliary inputs is to find α when gαi (i=0,1,2,…,d) as well as g, gα 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 √ 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.
©2010 Microsoft Corporation. All rights reserved.