Generalized Algorithm for DLP with Auxiliary Inputs

Speaker  Jung Hee Cheon

Affiliation  Seoul National University

Host  Kristin Lauter

Duration  01:17:46

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.
> Generalized Algorithm for DLP with Auxiliary Inputs