Generalized Algorithm for DLP with Auxiliary Inputs

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.

Speaker Details

Jung Hee Cheon received the B.S. and Ph.D. degrees in Mathematics from KAIST in 1991, and 1997, respectively. He is a professor of Mathematical Sciences at the Seoul National University (SNU). Before joining to SNU, he was in ETRI, Brown university, and ICU. He is on the editorial board of Journal of KIISC and CSI. He received the best paper award in Asiacrypt 2008. His research interests include computational number theory, cryptography, and information security.

Date:
Speakers:
Jung Hee Cheon
Affiliation:
Seoul National University
    • Portrait of Jeff Running

      Jeff Running